Linked Lists Basics

[qingquan-li]

Reference: Book: Data Structures Using C++ (Second Edition, D.S. Malik)

1. Linked Lists

A linked list is a collection of components, called nodes. Every node (except the last node) contains the address of the next node. Thus, every node in a linked list has two components: one to store the relevant information (that is, data) and one to store the address, called the link, of the next node in the list. The address of the first node in the list is stored in a separate location, called the head or first.

A pictorial representation of a node:

Linked list: A list of items, called nodes, in which the order of the nodes is determined by the address, called the link, stored in each node.

An example of a linked list:

The arrow in each node indicates that the address of the node to which it is pointing is stored in that node. The down arrow in the last node indicates that this link field is NULL.

For this linked list, the definition of the node is as follows. (Suppose that the data type is int.)

struct nodeType
{
    int info,
    nodeType *link;
};

The variable declaration is as follows:

nodeType *head;

Linked Lists - Some Properties:

• head - It points to the beginning of the linked list.
• current - It points to a specific node within the list, indicating a position of interest or traversal.
• info and link in each node - "info" holds the actual data value of the node, and "link" points to the next node in the sequence, with the final node's "link" pointing to "0" (NULL) signaling the end of the list.

2. Insertion

Definition of a node. (For simplicity, we assume that the info type is int.)

struct nodeType
{
    int info,
    nodeType *link;
};

Variable declaration:

nodeType *head, *p, *q, *newNode;

2.1 Insert with one pointer

Suppose that p points to the node with info 65, and a new node with info 50 is to be created and inserted after p:

newNode = new nodeType;  //create newNode
newNode->info = 50;      //store 50 in the new node

// Insert newNode in the list using only one pointer, p.
// The order in which these statements execute matters.
newNode->link = p->link;
p->link = newNode;

2.2 Insert with two pointer

Inserting a node in a linked list using two pointers, we can simplify the insertion code somewhat.

newNode = new nodeType;  //create newNode
newNode->info = 50;      //store 50 in the new node

// Insert newNode between p and q:
newNode->link = q;
p->link = newNode;

// Or (the order in which these statements execute does not matter):
p->link = newNode;
newNode->link = q;

3. Deletion

Suppose that the node with info 34 is to be deleted from the list. The following statement removes the node from the list:

p->link = p->link->link;

The resulting list after the preceding statement executes:

It is clear that the node with info 34 is removed from the list. However, the memory is still occupied by this node and this memory is inaccessible; that is, this node is dangling.

To deallocate the memory, we need a pointer to this node. The following statements delete the node from the list and deallocate the memory occupied by this node:

q = p->link;
p->link = q->link;
delete q;

4. Building a Linked List

A list can be built in two ways: forward and backward. In the forward manner, a new node is always inserted at the end of the linked list. In the backward manner, a new node is always inserted at the beginning of the list.

Suppose that the nodes are in the usual info-link form and info is of type int. Let us assume that we process the following data:

2 15 8 24 34

We need three pointers to build the list: one to point to the first node in the list, which cannot be moved, one to point to the last node in the list, and one to create the new node. Consider the following variable declaration:

nodeType *first, *last, *newNode;
int num;

Suppose that first points to the first node in the list. Initially, the list is empty, so both first and last are NULL. Thus, we must have the following statements to initialize first and last to NULL:

first = NULL;
last = NULL;

4.1 Building a Linked List in Forward Order

Suppose that we read a list of integers ending with -999. The following function, buildListForward, builds a linked list (in a forward manner) and returns the pointer of the built list:

nodeType* buildListForward()
{
    nodeType *first, *newNode, *last;
    int num;
    
    cout << "Enter a list of integers ending with -999." << endl; // 2 15 8 24 34 -999
    cin >> num;
    first = NULL;
    
    while (num != -999)
    {
        newNode = new nodeType;
        newNode->info = num;
        newNode->link = NULL;
        
        if (first == NULL)
        {
            first = newNode;
            last = newNode;
        }
        else
        {
            last->link = newNode;
            last = newNode;
        }
        cin >> num;
    }
    
    return first;
}

Breakdown:

newNode = new nodeType;
newNode->info = num;
newNode->link = NULL;
...
if (first == NULL)
{
    first = newNode;
    last = newNode;
}

newNode = new nodeType;
newNode->info = num;
newNode->link = NULL;
...
else
{
    last->link = newNode;
    last = newNode;
}

Build a completed program to call the buildListForward function to build the list:

#include <iostream>
using namespace std;

// Struct definition
struct nodeType {
    int info;
    nodeType* link;
};

// Function prototype
nodeType* buildListForward();

int main() {
    nodeType* head = buildListForward();

    // To display the list:
    nodeType* current = head;
    cout << "The linked list is:" << endl;
    while (current != NULL) {
        cout << current->info << " ";
        current = current->link;
    }
    cout << endl;

    // Cleaning up allocated memory
    while (head != NULL) {
        nodeType* temp = head;
        head = head->link;
        delete temp;
    }

    return 0;
}

Enter a list of integers ending with -999.
2 15 8 24 34 -999
The linked list is:
2 15 8 24 34 

4.2 Building a Linked List in Backward Order

For the previously given data—2, 15, 8, 24, and 34—the linked list is as shown below:

Because the new node is always inserted at the beginning of the list, we do not need to know the end of the list, so the pointer last is not needed.

Also, after inserting the new node at the beginning, the new node becomes the first node in the list. Thus, we need to update the value of the pointer first to correctly point to the first node in the list.

nodeType* buildListBackward()
{
    nodeType *first, *newNode;
	int num;
    
    cout << "Enter a list of integers ending with -999." << endl;
    cin >> num;
	first = NULL;

	while (num != -999)
    {
        newNode = new nodeType; // create a node
        newNode->info = num;    // store the data in newNode
        newNode->link = first;  // put newNode at the beginning of the list
        first = newNode;        // update the head pointer of the list, that is, first
        cin >> num;             // read the next number
    }
}