Linked Lists

[WingedPanther]

Now let's look at what we can actually do with pointers. The ability to dynamically allocate memory is all well and good, but so what? We'll look at one of the most basic concepts that relies on pointers: a linked list. A linked list is simply a collection of structures called nodes, along with a pointer to the first and last node. A node includes the data of interest, and one or more pointers to other nodes. For our example, we'll simply use a single pointer to the next node in the list. A linked list will look something like this:

  head                                                    tail
    |                                                       |
    |                                                       |
   \|/                                                     \|/
+------------+    +------------+    +------------+    +------------+    
| data, next-+--> | data, next-+--> | data, next-+--> | data, next-+--> NULL
+------------+    +------------+    +------------+    +------------+

In addition, you need to be able to append a node (at the end), and delete a node (any node). We'll also provide the ability to detect if an element exists and to print the list. This means we'll need methods append(data), delete(data), exists(data), and print(). I will slowly build up stringlist.h, explaining the logic as I go. If you paste the following code snippets together, you will get the complete stringlist.h:

#include <string>
#include <iostream>

class stringlist 
{
  struct node 
  {
    std::string data;
    node* next;
  };
  node* head;
  node* tail;
public:
  bool append(std::string);
  bool clear(std::string);
  bool exists(std::string);
  void print();
  stringlist();
};

This is the declaration of our stringlist and methods. We need to include <string> for our data, and <iostream> to print the list. By declaring the node structure inside the class, we guarantee that nothing outside will be able to inspect our internal data. Technically, we could replace the linked-list structure with an array if we wanted, and it would not affect anything else. Notice that a node simply contains data and a pointer to the "next" node. The rest of our data consists of a pointer to the head of the list (beginning) and tail of the list (end). We could (and probably should) add a count variable to keep track of how many elements we have.

We also declare our functions. We are returning bool on append and clear so the calling application can determine whether the process was successful (append couldn't grab the memory or clear couldn't find the data to delete). stringlist is our constructor. Notice that we could adjust this to be a template using most any class/struct instead of std::string. As you will see, there are very few requirements on the supported operators to use this linked list.

stringlist::stringlist()
{
  head=NULL;
  tail=NULL;
}

The constructor only needs to do one thing: make sure our internal pointers are set to NULL! If not, the logic in the following methods will not work correctly, and our programs will have highly unpredictable results. Remember to always initialize your pointers! Since we have no data, NULL is the value we need. The result is that our initial list looks like this:

  head      tail
    |         |
    |         |
   \|/       \|/
  NULL      NULL

We will look at the append() method next. I am breaking it into pieces since it does a lot:

bool stringlist::append(std::string newdata)
{
  if (head){
    tail->next = new node;
    if (tail->next != NULL)
    {
      tail=tail->next;
      tail->data = newdata;
      return true;
    }
    else
      return false;
  }

Pointers are an integral type, and NULL evaluates to false, so we can simply check to see if head points to something. If it does, then all we need to do is append a new node to the tail. Before assigning the data, we should see if getting the new node was successful. That's why I check to see if tail->next is not NULL. Once that is done, we can point tail to the new last element and set the data.

  else
  {
    head=new node;
    if (head != NULL)
    {
      tail=head;
      head->data = newdata;
      return true;
    }
    else
      return false;
  }
}

On the other hand, if there are no elements, we have to create a new element and point both the head and tail to it. Notice that if a node exists, we have guaranteed that tail points to the last one. We only assign head a value when creating the first node.

bool stringlist::clear(std::string deldata)
{
  node* temp1=head;
  node* temp2=NULL;
  bool result=false;
  while (temp1 != NULL)
  {

clear() is the most complicated function we will look at. We will use two temporary pointers as well as tracking whether we deleted a node. This function will clear out ALL matches. As you will get used to seeing, we check to see if temp1 is NULL as our boundary condition, and do not assume there are any nodes to delete.

    if (temp1->data == deldata)
    {
      if (temp1==head)
        head=temp1->next;
      if (temp1==tail)
        tail=temp2;
      if (temp2!=NULL)
        temp2->next=temp1->next;
      delete temp1;
      if (temp2==NULL)
        temp1=head;
      else
        temp1=temp2->next;
      result=true;
    }

Our first step is to check if we've found a node that we need to delete. If we have, things get complicated. Our first priority is to make sure our head and tail pointers don't get screwed up. They must always point to valid data! If the first node is about to be deleted, we must advance the head pointer. If the last node is about to be deleted, we must move back the tail pointer (to temp2). If our match has a predecessor node (at temp2), we must also update its next pointer to skip the node we're about to remove.

Once the node has had all pointers shifted away from it, we can delete it. Now we have to determine if we were at the head (no predecessor) or not. If we were at the head of the list, temp1 is assigned to the new head. Otherwise, we assign temp1 to the element that was next on the list. Finally, we note that we found a node to delete.

    else // temp1->data != deldata
    {
      temp2=temp1;
      temp1=temp1->next;
    }
  }
  return result;
}

Otherwise (if we didn't find a node to delete), we simply advance both pointers and check again. We return whether anything was deleted when we've stepped through the entire list. Because we are potentially deleting multiple elements, we should make our append() and clear() methods responsible for keeping track of the number of elements, if we care about that.

bool stringlist::exists(std::string finddata)
{
  node* temp=head;
  bool found=false;
  while (temp != NULL && !found)
  {
    if (temp->data == finddata)
      found=true;
    else
      temp=temp->next;
  }
  return found;
}

exists() is a fairly simple method. I create a temporary pointer and a bool to keep track of whether we've found the data. We step through the list ("temp != NULL") until we find a match ("!found"). Upon finding a match, we update found, otherwise we update our pointer to the next node. For a large list, checking !found can save us a lot of time. This could be further optimized by using return statements instead of using found.

void stringlist::print()
{
  node* temp=head;
  while (temp != NULL)
  {
    std::cout<<temp->data<<"\n";
    temp=temp->next;
  }
}

print() is a fairly simple method. We create a temporary pointer and step through the list, printing each element on its own line. Notice that I do not assume there is an element. I have used "temp != NULL" in my condition, but could as easily have simply used "temp". My option is less efficient, but I think it is slightly clearer.


A simple test program might look like this, then:
testlist.cpp:

#include <string>
#include <iostream>
#include "stringlist.h"
using std::string;
using std::cout;

int main()
{
  int count = 0;
  stringlist mylist;
  if (mylist.append("something")) count++;
  if (mylist.append("else")) count++;
  if (mylist.append("yet")) count++;
  cout<<"Added "<<count<<" items\n";
  mylist.print();
  if (mylist.exists("mess"))
    cout<<"\"mess\" is in the list\n";
  else
    cout<<"\"mess\" is not in the list\n";
  if (mylist.exists("yet"))
    cout<<"\"yet\" is in the list\n";
  else
    cout<<"\"yet\" is not in the list\n";
  if (mylist.clear("mess")) count--;  //this does nothing!  returns false
  cout<< count<<"\n";
  if (mylist.clear("yet")) count--;  //this removes all instances of "yet", count should probably be handled internally
  cout<< count<<"\n";
  if (mylist.exists("yet"))
    cout<<"\"yet\" is in the list\n";
  else
    cout<<"\"yet\" is not in the list\n";
  if (mylist.clear("else")) count--;
  cout<< count<<"\n";
  if (mylist.clear("something")) count--;
  cout<<count<<"\n";
  mylist.print();  //everything removed, this does nothing!
  //cout<<mylist.head<<"\n";
  //cout<<mylist.tail<<"\n";
  return 0;
}

Notice that if we had added "yet" twice, count would not be accurate after we call clear("yet").

The output of this program is:

Added 3 items
something
else
yet
"mess" is not in the list
"yet" is in the list
3
2
"yet" is not in the list
1
0

[MeTh0Dz]

I've usually heard that it is better practice to define structures and such outside of your class, perhaps in the namespace if you are using one.

[Aereshaa]

Nice tutorial. +rep.

[WingedPanther]

I've usually heard that it is better practice to define structures and such outside of your class, perhaps in the namespace if you are using one.

I defined it inside the class so that I could easily make a template version of the linked list (replacing std::string with <class T>).

As I noted in the tutorial, there were areas open for further improvement. My main goal was to help people understand how to add nodes, remove nodes, etc. I'm planning to use this tutorial as the basis of a series of tutorials on ADTs.

[Jordan]

Very nice tutorial/read! +rep

[whitey6993]

Great tutorial. Looking forward to tutorials on ADTs. +rep