Linked list primer

List nodes

Basically, a non-null list consists of several nodes arranged in a particular linear order, just like an array. Unlike an array, though, each node consists of, in its simplest form, a data structure that has both a data element and a pointer.

The data item holds the node's data element (like the x-coordinate), and the pointer (often called the next pointer) points to, or holds the address of, the next node in the list. Sometimes, as shown in the diagram, the data item is itself a pointer, but I'll stick with the example case of the data being integers. To make a list of arrays of floats, for example, just change the type of the data element in the linked list nodes.

There is one convention I'd like to clear up before continuing, and that is the null pointer convention. Pointers can either point to something by holding some useful data value, or they can point to nothing by holding a special value, often called NULL or NUL or just plain 0. Different folks have different ways of representing null pointers in diagrams. (Usually, it's a slash, or ground, or something else null-looking.)

I prefer the electrical ground symbol (three parallel lines) ; therefore, that is the notation that I will use here. Before going any further, draw a few list nodes just to get a feel for using your pencil or crayons or whatever you've got near your computer.

The list structure

Here's the conceptual diagram of a small linked list that holds integers as data :

Notice three things about the list :

• The pointer at the end of the list is null.
• Each node's next pointer (except for the last node) points to another unique node in the list, making the list a linear graph.
• The first node of the list is pointed to by a pointer named top. (It could also be called start, go, fred, or xcoords ...) What is the type of the top pointer (e.g. is it a pointer to float or a char, or something else) ?

Thus a linked list is a linear data structure that is a lot like an array. The tricky part is that linked lists are a little bit more complex to implement than arrays. I'll give a small start, and then I will provide some programming ideas to help the linked list concept along.

Extending data retrieval

Now that you know how to do things to each item in the list sequentially, it might seem like a logical next step to use this same process to do nothing to each element in the list sequentially until you find a particular element that you need. This is just the way that one goes about, for example, finding an element in the list or counting only specific elements in the list. Of course, there are many other tasks that you might do to elements in a list that fall into this category, but searching is one of the most common.

So here's an example of how you might traverse the list iteratively (in C) to find a specific element. The function returns NULL if the number we're looking for isn't in the list.

IntList *
find(int needle, IntList *haystack)
{
  IntList *t;

  for(t = haystack; t; t = t->next)
    if (t->data == needle) return t;

  return NULL;
}

Another example of how you might use this functionality would be to extract only those elements from a list that satisfy certain criteria, building up a list of such elements that you find. You might want to find all the prime numbers in a given list of integers, for example. Here's some code in C++ that uses recursion to do that.

IntList *
primesFromListRecursive(IntList *start, IntList *filtered)
{
  if (! start) return filtered;
  if (isPrime(start->data)) {
    IntList *newF = new IntList(start->data, filtered);
    return primesFromListRecursive(start->next, newF);
  } else {
    return primesFromListRecursive(start->next, filtered);
  }
}

Basics to cover in linked list programming

Whenever you are dealing with linked lists, it's important to address three types of elements in the list :

• the beginning
• the end
• a general element that's between the middle and the end

Sounds pretty easy, and the above three cases are enough to keep yourself out of hot water when programming a linked list. If you've covered the case of the beginning of the list, covered the case of the end of the list, and covered an arbitrary case in the middle of the list, you're set !

Deleting

So how does this apply to deleting ? Well, let's take a look at the list from above and think of how to delete the beginning, the end, and the middle of the list.

The beginning is pretty easy : we would need to keep a temp pointer to the beginning (so we don't lose track of it), reroute the top pointer to the value of the first element's next pointer, and then set the first element's next pointer to NULL. Then we'll be safe to delete that node without destroying the rest of the list, and thanks to the rerouted top pointer, we know where the new start of the list will be.

The end is even easier, once you see how the beginning works : once we find the end of the list, we keep a temp pointer to that element, set the previous node's next pointer to NULL (because it will become the end of the list), and delete the last node.

Finally, deleting a node from the middle : this is a little more complex, but it uses the same process as before. We again need to keep a temp pointer to the node we're trying to get rid of. Then, like the case for the beginning of the list, we reroute the pointer that points to the current node to the value of the current node's next pointer. After we set the current node's next to NULL, we'll be set to delete the node.

That covers our three cases. Now the question is how to unify the three into one compact function ... it becomes more clear when you notice that in all three cases, we take the pointer that points to the node we want to delete and then reroute it to the node after the current node. There are two somewhat special cases: in the beginning of the list, the previous pointer is the pointer that keeps track of the start of the list, and for the end of the list, the node after the one we want to delete is effectively NULL. So here is one way to delete a node from a linked list, iteratively in C :

IntList *
delete(IntList *l, integer value)
{
  IntList *ret = l, *cur = l, *prev = l;

  /* advance the current node pointer, trailing behind
     the previous node pointer, until we find the end
     of the list or the value we want. */
  while (cur && (cur->data != value)) {
    prev = cur;
    cur = cur->next;
  }

  /* if we found a node with the value, delete it. */
  if (cur && (cur->data == value)) {
    if (cur == prev) ret = cur->next;
    else prev->next = cur->next;

    cur->next = NULL; free(cur);
  }

  return ret;
}

There are some things to keep in mind about this particular implementation. First, it's not pretty. Next, this function deletes the first node it encounters in the list that has a data value of value. There are ways to delete nodes based on a pointer to a particular node. (Say, for instance, you found a pointer to the node using a search function, then passed the pointer to the delete function.) In addition, this function deletes a maximum of one node from the list. There are ways to delete all nodes with a specified data element.