Linked Lists

Here's a short and incomplete introduction to Linked Lists in C++ that I wrote sometime in 2004/05.


What is a Linked List?

A Linked List is a form of sequential storage—a data structure in which the first record stores the memory address of the next, the seconds stores the address of the third and so on. Hence, each record consists of two portions: an information part and a pointer. If you're wondering why a pointer is necessary, the idea is to make each record point to the immediately next one in memory, so that the whole structure consists of individual records linked to each other. That's why its called a Linked List.

The individual records are referred to as nodes. The first node (also called the 0th node) is called the head node, and the last node (loosely referred to as the (n-1)th node for a n-size list) is called the tail node. There exist 3 different kinds of linked lists:

  1. Singly Linked List
  2. Doubly Linked List
  3. Circular Linked List

Before I describe in detail each of the above mentioned types of lists, you should know the structure of a linked list. We start with the singly linked list because its the easiest to understand for a novice. Below is a diagrammatic representation of a singly linked list.

linked1.gif

hPtr is a pointer that points to the head Node. After all, you need to know where to start traversing the list. hPtr stores the memory address of the first node (node 0 or head node). Subsequent nodes after node 0 consist of a next pointer that points to the node. Node 2 is the last node and it is grounded, i.e. it's next pointer stores the value NULL. The idea of grounded nodes actually comes from electronic circuit conventions, where a point at relative zero potential is often shown grounded on a circuit diagram.

The NULL value tells the compiler where to stop (or else it would continue to traverse memory locations which may or may not belong to your program, producing what are loosely referred to as junk values; errors might also occur if protected memory locations are accessed and the compiler may hang or exit with an error code, depending on your operating environment).

To summarize, a singly linked list consists of a head node pointer, (n-1)-nodes each consisting of an information part and a pointer that points to the next node (next pointer) and a tail node that has its next pointer assigned to NULL. Make sure you're pretty clear about the concept of singly linked lists. Try playing with the code/algorithm given below, experiment with your own ideas and don't feel afraid of messing up the memory-if you're a novice, chances are that you'll encounter more compile time errors than runtime errors so you shouldn't be afraid of making incorrect memory calls (most compilers won't let you get away with mistakes unless you're smart—its a misconception that novice programmers are likely to cause damage to their computers during pointer experiments).


Creating and Traversing a Singly Linked List

Now we come to the fun part, creating your own list (sounds nice doesn't it?) and using it in your own C++ program. Here is the code. We assume that a minimal data structure called List has been created with the following contents

  • x (integer)
  • nextNode (pointer of type List)

We define cNode as the ith node (typical node—we use cNode for all I/O operations), hNode as the first (head) node and temp as a temporary node that is created each time the user inputs new data. The operator -> (minus followed by greater than symbol) is used to indicate a reference to a variable internal to the structure. For instance, cNode->x is used to gain access to the value x stored in the node named cNode. To access nextNode (the next pointer), we use cNode->nextNode.

1. Set choice := 1
2. Set hNode  := new List                          // (create a new memory location for the first node)
3. Set cNode  := hNode                             // (start from head node) 
4. Do (steps 5 through 10)
5.     Input cNode->x
6.     Input choice
7.     Is choice <> 1?
          YES: exit loop (step 11)
          NO : continue (step 7)
8.     Set temp := new List                        // (create a new memory location for a new node)
9.     Set cNode->nextNode  := temp                // (point cNode's next pointer to this new node)
10.     Set cNode           := cNode->nextNode     // (advance cNode to point to the newly created node)
11. While (choice = 1) 
12. Set cNode->nextNode := NULL                    // (make next pointer of tail node NULL)
13. Stop
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License