Linked Lists

A linked list is a data structure which is used to implement a list of items that are arranged in some order.

Each item in the list is represented as a single cell or node, each of which is made up two portions:

  1. data field – information relevant to the node
  2. link field – address of the next node in the list

Since the link field holds an address, it is implemented using a pointer. But a pointer to what?

In C++, a node can be implemented by defining either a structure or class:

struct Node                               class Node
   {                                         {
   int data;                                 ...
   Node *link;                               private:
   };                                          int data;
                                               Node *link;
                                             };

Typically, programs do not declare node variables. Instead, when the list is being built and manipulated, pointers to nodes are used.

Node *nodePtr;

The most common way to access a linked list is by starting at the first node in the list. This pointer is known as the head pointer. Sometimes a pointer is also maintained on the last node in the list. This pointer is known as the tail pointer.

Node *headPtr;
Node *tailPtr;

Notice that the picture now includes a head pointer and an X in the link field of the final node. The X is used to symbolize the null pointer. This pointer is used for any pointer variable that has no place to point. It is commonly used:

In a program, the null pointer may be written as NULL (which is defined in <cstdlib> and is NOT part of the std namespace) or by using 0.

Node *headPtr = NULL;

if (headPtr == 0)

Node Constructor

class Node
   {
   public:
     Node(int = 0, Node * = NULL);
   ...
   private:
     int data;
     Node *link;
   };

The constructor has parameters to initialize the two fields of the node. Its job will be to initialize the two fields.

Node::Node(int initialValue, Node *initialLink)
  {
  data = initialValue;
  link = initialLink;
  }

To create a node:

Node *p, *q, *r, *s;

p = new Node;

q = new Node(5);

r = new Node(12, p);

s = q;

Since pointers are typically used to refer to nodes, we need some way to reference the data members and call the methods. The symbol to use is the member selection operator ( -> ).

cout << q->data;

p->link = 0;

Processing a Linked List

There are some common practices that are performed on a linked list:

Finding the length of the list

This is done by counting the number of nodes in the list. To accomplish this, use a pointer variable and step through the list one node at a time:

  1. Initialize a counter variable to 0
  2. Initialize a pointer variable to the first node in the list
  3. If the pointer is NULL, then done. If it is not NULL, increment count.
  4. Move to the next node in the list and repeat step 3 until done

Searching the list for a specific node

Start with the first node in the list. Step through the list until the node or end of list is found.

Inserting a node into the linked list

There are three cases that need to be considered:

  1. The element to insert is first in the list
  2. The element to insert is in middle of the list
  3. The element to insert is last in the list

Case 1: Set the link field of the inserted node to the current first node in the list. Reset the head pointer to the inserted node.

Case 2: Start at the first node in the list. Step through the list until the correct insert position is found. Lets call the node before the place to insert beforeNode and the node after the place to insert afterNode. Set the link field of beforeNode to the inserted node. Set the inserted node's link field to afterNode.

Case 3: Start at the first node in the list. Step through the list until the end of the list is found. Set the link field of the last node to the inserted node. Set the link field of the inserted node to NULL.

In order to implement cases 2 and 3 correctly, a lag pointer or predecessor pointer needs to be used in order to connect the nodes.

Cases 2 and 3 can be combined if the pointers are properly maintained.

Deleting a node from the list

There are three cases that need to be considered:

  1. The list is empty
  2. The element to delete is first in the list
  3. The element to delete is not first in the list

Case 1: There is no element to delete

Case 2: Set the head pointer to first node's link field. Free up the memory of the deleted node.

Case 3: Start at the first node of the list. Step through the list until the node to delete is found. Set the link field of the node BEFORE the node to be deleted to the link field of the node to be deleted. Free up the memory of the node to be deleted. Again, a predecessor pointer is needed to connect the nodes surrounding the node to be deleted.