Linked Lists

Another fairly straightforward storage structure is the linked list. A linked list is in fact a set of data elements that are chained together by pointers. Each element contains a pointer to the next element in the list, or a NULL pointer in case there are no further elements in the list. Figure 11.1 shows a linked list.

How you link list elements together is of course entirely up to you. One type of linked list that is often used is the double linked list, in which elements contain pointers to the next list element as well as to the previous element. The advantage of this is that you can navigate through the list in both directions given a pointer to any of the elements. Figure 11.2 shows a double linked list.

A skip list is another list of linked elements which contains additional information that allows you to skip some elements while traversing. Think, for instance, of a list of alphabetically ordered names. Instead of using only a single pointer to the next element, you could create a skip list by adding to each element a pointer to the first element of the next letter in the alphabet:

struct SkiplistNode
{
    char             * name;
    SkiplistNode     * nextName;
    SkiplistNode     * nextLetter;
};

Exactly when and what you skip will differ per skip list implementation. Figure 11.3 shows a skip list containing alphabetically ordered names. Each list element points to its successor. In addition to this, each first element of a particular letter points to the first element of the following letter. This makes it possible, for instance, to quickly find all names beginning with a certain letter by first skipping to the correct letter and then traversing elements from there on.

Skip lists do not have to be limited to one additional pointer per element, of course. You could decide to add another pointer to some elements to point to letters in a different alphabet, for example.

The advantage of lists compared to arrays is that you can more easily add elements to and remove them from a list than an array (given that the array may at some time become full).

The file 11Source01.cpp that can be found on the Web site compares the performance of linked lists against that of other data structures. There is a section at the end of this chapter that presents the timing results of these tests.

Inserting

Inserting an element in a linked list consists of updating the next/previous pointers of the element to insert, the element to insert before, and the element to insert after. Special care has to be taken when inserting into an empty list and when inserting before the first element or after the last element. Nevertheless, the actual inserting action is not dependent on the length of the list and is therefore an O(1) operation. When, however, the place to insert an element still has to be found, some searching needs to be done beforehand. For this, see the section "Searching."

Deleting

Deleting an element from a linked list consists of updating the next/previous pointers of the element before the deleted element, the element after the deleted element, and perhaps (when the element is not destroyed but simply removed from the list), also the deleted element itself. Special care has to be taken when deleting the last element from a list, deleting an element at the back of the list, and deleting the first element of a list. Deleting is also an O(1) operation. When, however, the element to delete still has to be found, some searching needs to be done beforehand. For this, see the following section, "Searching."

Searching

Searching through a linked list is not that exciting. In the case of a single linked list, you have no choice but to take a pointer to an element, and from that point check each element one by one, moving to the next element on a mismatch. This is an O(n) operation because in a worst-case scenario you start at the beginning of the linked list and end up checking each element till you reach the end. When a linked list is sorted and you have more than one element pointer to start from, you can jump into the list at a more optimal point. You determine which pointer points to the element furthest in the list—but not past the key you are searching on—and start with that element. Basically what you have done here is create a sort of skip list using element pointers. Worst-case operation is now dependent on the number of search points and how well they are placed. With a double linked list and a pointer to the middle list element, searching is reduced to an O(n/2) operation on a sorted list when you can determine with certainty in which direction to start searching.

Traversing

Traversing a linked list is a matter of following the next pointers of the elements. In a double linked list, two directions of traversing are possible. In a skip list, fast traversing the list is possible because parts of the list that are not interesting at the moment can be skipped while traversing.

Sorting

Although the dynamic use of linked lists is less complex than that of arrays, the opposite is true for sorting. Sorting is especially problematic with single linked lists. This is because access to the elements is no longer random but has to be done through other elements. Sorting directly on the linked elements is therefore far from efficient. The sorting functions of the previous chapter can be used for linked lists when either a) the linked list is a class that overloads the operators [], =, <=, ==, and so on, or b) the sorting functions are updated to use member functions of the list class in order to access and manipulate elements. Listing 11.2 shows the different kinds of element access for sorting via operator overloading or class method adoption.

Code Listing 11.2. Element Access for Sorting

~
// Element access example for arrays
//   or linked lists with operator overloading.
if ( data[i] < data[i+1]
{
  temp      = data[i+1];
  data[i+1] = data[i];
  data[i]   = temp;
}
~
~
// Element access example for linked lists using list methods for access.
if ( list1.GetElem(i)->key < list1.GetElem(i+1)->key)

{
  list1. SwapElems(i, i+1);
}
~

Though the example that uses list methods for access may look shorter and thus more efficient, you should not forget that each call to a list function is in itself an O(n) operation! And it makes no difference whether the function called is an operator or some other method (GetElem() versus []). To refrain from having to search the list each time you need to access an element, you could create an array containing a pointer to each list element. This is the only way to speed up access. During sorting you access the list elements through the array of pointers for element evaluation, and then you sort the pointers based on that element evaluation. Only when the pointers are sorted do you traverse the linked list one last time to set the elements in the right order. However, this means you change the footprint of the data storage during sorting. Having said all this, if sorting directly on list elements is necessary, an insertion sort or merge sort is probably advisable. See Chapter 10.