Linked Lists

Linked Lists

A linked list is a data structure in which we store each item of data in its own small piece of memory. The pieces are called nodes and are linked together using pointers (or the equivalent), so that each node contains a pointer to a successor node.

We have a pointer, often called "Head", to the beginning of the list.

There are various operations we might like to have for a linked list. a few of them might be:

Create a new empty list.
Insert a node into the list.
Remove a node from the list.
Search the list for a node containing a specific value.
Compare two lists.
Dispose of a list.

Singly-linked List

In a singly-linked list, each node contains one item of data and one pointer. The pointer in the last node has the value "Null" (or the address 0).

          Head = Null               /*  An empty list.        */

          Head -> 13 -> Null        /*  A list of one item.   */

          Head -> 13 -> 42 -> Null  /*  A list of two items.  */

In some cases, we want to maintain our singly-linked list in some kind of order based on the data. In that case, we have to search through the list to find the proper location. For instance, if we have

          Head -> 13 -> 42 -> 76 -> 101 -> Null

and we want to insert the value 53, it needs to be inserted between 42 and 76, and to do so, we will need a pointer to the node containing 42.

Likewise, to delete a specific node from a singly-linked list, we need a pointer to the node preceding the node to be deleted.

There are variations on the idea: We may also have a pointer called Tail which points to the last node on the list. (This makes it easy to attach a new node at the end, which otherwise requires some work.)

We may have the end of the list marked by a sentinel value in a node instead of using a pointer with value Null.

A natural way to build a linked list is to use dynamic memory allocation, getting hold of memory for one node at a time as needed. The advantage is that we use no more memory than we need, and the disadvantage is the time needed to allocate and deallocate nodes.

One strategy is to allocate a large number of nodes to begin with, each initialized to some default value, and keep a separate list of these available nodes. When we need one for our main list, we detach it from the list of available nodes, much faster than using dynamic memory allocation each and every time. Likewise, when we remove a node from our list, we put it back on the list of available nodes. That is, to some extent, we can manage our own memory allocation.

Instead of using dynamic memory, we can implement a linked list using an array of nodes. Instead of a pointer, each node contains an integer = the subscript of the next node. Of course, the array probably contains many more nodes than we are using at any given time, so we can maintain a list of available nodes. This should work fairly fast. It may be a good choice if we are certain we will never need more than some specific number of nodes.

Circular Linked List

In a circular linked list, the list forms a circle. We still have a Head pointer, but when we traverse the list and find the "last" node, its pointer points back to the first node.

An obvious danger here is that might go around and around indefinitely, but we can check: is the current pointer equal to the Head pointer? Also, sometimes it may be desirable to go around and around indefinitely.

Doubly-Linked List

In a doubly-linked list, each node contains two pointers, one forward to the next node and one back to the preceding node. The first node's back pointer is Null, and the last node's forward pointer is Null.

     Head -> 13 -> 42 -> Null  
     Null <-    <-    <- Tail

We will keep two extra pointers, Head and Tail, pointing to the first and last nodes.

The advantage of a doubly-linked list is that we can traverse it in either direction, and we can easily add nodes at either end. If we are keeping our list in order, we can insert a node where it belongs more easily than we could with a singly-linked list. Likewise, we can delete a node more easily than with a singly-linked list.

The disadvantage of a doubly-linked list is that there is more overhead work to do, maintaining the linkage in both directions.

What would this look like in C++ ?

We normally implement a linked list using two classes or a struct and a class. Here is an example:

     struct Node
      {
       int Data;
       Node * Next;
      }; 

     class LList
      {
       private:
        Node * Head;
       public:
        //many things
      };

We could make Node a class instead and made some or all parts of it private. In that case, we would then want the List class to be a friend of the Node class.

We could also have a "Tail" pointer, or a counter for the length of the list.

We might want to have a counter for the number of Nodes in the LList.

If we want this to be a doubly-linked list, then the struct Node would contain another Node * variable called something like "Back", and LList would definitely contain a Tail pointer as well as Head.

What kinds of methods could we have in class LList? We need to have a constructor, a copy constructor and a destructor, and we may also have methods for other purposes such as:

add a node to the beginning of the list
remove a node from the beginning of the list
return the value in the node at the Head
return true if the list is empty and false otherwise
return the number of nodes in the list
operators such as == and !=
insert a node into the list in ascending order (based on the data)
search for and remove a a node from somewhere in the middle of the list
print the data in the nodes
print the data in reverse order

Some linked-list processing can be done easily using recursion: a function may do something with the node at hand and then call itself to process the rest of the list.