Overview

Data Structures are the building blocks of computer science and programming. The enable us to organize and manage data efficiently. One such fundamental data structure is the linked list. In this post, we will explore what linked list are, how they work, and how to implement them in C++.

What is a Linked List?

A Linked list is a linear data structure in which elements, called nodes, are connected sequentially. Unlike arrays, linked lists do not require contiguous memory locations. Each node in a linked list contains two parts: the data and a reference (or pointer) to the next node in the sequence. The last node typically points to a null value, indicating the end of the list.

Unlike arrays, the elements are not stored at a contiguous location. Since for any element to be added in an array, we need the exact next memory location to be empty, and it is impossible to guarantee that it is possible. Hence adding elements to an array is not possible after the initial assignment of size.

Index:      0        1        2        3        4        5        6        7        8        9
        +-------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
        |  10   |   20   |   30   |   40   |  50    |   60   |   70   |   80   |   90   |   100  |
        +-------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
Address: 0x1000 | 0x1004 | 0x1008 | 0x100C | 0x1010 | 0x1014 | 0x1018 | 0x101C | 0x1020 | 0x1024 |

In the diagram above, each element occupies a contiguous block of memory, and the memory address are shown beneath each element.

Head → +--------+------+       +------+------+       +------+------+       +------+------+ 
       |  10    | next |    →  |  20  | next |    →  | 30   | next |    →  | 40   | next | → NULL
       +--------+------+       +------+------+       +------+------+       +------+
------+
Address: 0x2000 | 0x2004       0x2008 | 0x200C       0x2010 | 0x2014       0x2018 | 0x201C

Linked lists come in various forms, with the most common types being:

1. Singly Linked List: In a singly linked list, each node points to the next node in the sequence. It only allows traversal in one direction, form the head (the first node) to the tail (the last node).
2. Doubly Linked List: In a doubly linked list, each node points to both the next and the previous node in the sequence. This allows for bidirectional traversal.
3. Circular Linked List: A circular linked list is similar to the a singly or doubly linked list but with the tail node pointing back to the head, forming a loop.

Singly Linked List
Head → +------+------+     +------+------+     +------+------+     +------+------+
       | data | next |  →  | data | next |  →  | data | next |  →  | data | next | → NULL
       +------+------+     +------+------+     +------+------+     +------+------+


Doubly Linked List
Head → +------+-------------+     +------+------+------+     +------+------+------+------+
       |prev  | data | next |  ←  |prev  | data | next |  ←  |prev  | data | next | → NULL
       +------+------+------+     +------+------+------+     +------+------+------+------+


Circular Linked List
Head → +------+------+     +------+------+         +------+------+         +------+------+
       | data | next |  →  | data | next |  →  | data | next |  →  | data | next | → Head
       +------+------+     +------+------+      ------+------+         +------+

Node Syntax:

#include <iostream>
using namespace std;

// Define the Node class
class Node {
public:
    int data;     // Data stored in the node
    Node* next;   // Pointer to the next node

    // Constructor
    Node(int value) {
        data = value;   // Initialize data with the provided value
        next = nullptr; // Initialize next as null since it's the end of the list
    }
};

int main() {
    // Create a node with data 10
    Node* myNode = new Node(10);

    // Access the data stored in the node and print it
    cout << "Data stored in the node: " << myNode->data << endl;

    // Access the next pointer (which is null in this case)
    if (myNode->next == nullptr) {
        cout << "Next pointer is null." << endl;
    } else {
        cout << "Next pointer is not null." << endl;
    }

    // Remember to deallocate memory to avoid memory leaks
    delete myNode;

    return 0;
}

// Output
Data stored in the node: 10
Next pointer is null.

Let's break this example to understand how it works:

1. The class has two data types: data which contains the value of the node and a pointer next, which points to the next node in the list.
2. There is a constructor which assigns the value to a new node.
3. A new keyword is used to dynamically allocate memory to new node with data as 10.

Pointers in C++

Pointers are variables that store memory addresses. they allow for indirect access and manipulation of data by referring to the memory location where the data is stored.

Example:

int main() {
    int x = 2;
    int* y = &x;  // y references x
    cout << y << '\n';  // Output: Address of x in memory
}

y is a pointer variable that stores the memory address of variable x, &x gets the address of x, which is then stored in y.

Node vs Node*:

In the context of linked list or other data structures, a Node refers to the structure that contains data. In contrast, Node* (Node pointer) specifically denotes a pointer variable that stores the address of the Node it is pointing to.

class Node {
public:
    int data;
    Node* next;
};

Memory Space:

Let's talk about assuming the data is stored in integer. Another main difference between an array and a linked list is the memory used. In the case of an array, we are storing integers that consume 4 Bytes for every int, whereas in a linked list, we are storing data and a pointer to every node, so the memory used up will depend on the configuration of the system.

Therefore, in the case of a 64 Bit system, it occupies or consumes more space than a 32 Bit system.

Code

Linked list can be achieved by different styles

#include <iostream>

// Define the structure for a node in the linked list
struct Node {
    int data;
    Node* next;
};

class LinkedList {
public:
    LinkedList() {
        head = nullptr;
    }

    // Function to insert a node at the end of the linked list
    void insert(int value) {
        Node* newNode = new Node;
        newNode->data = value;
        newNode->next = nullptr;

        if (!head) {
            head = newNode;
            return;
        }

        Node* current = head;
        while (current->next) {
            current = current->next;
        }

        current->next = newNode;
    }

    // Function to display the linked list
    void display() {
        Node* current = head;
        while (current) {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }

private:
    Node* head;
};

int main() {
    LinkedList myList;
    myList.insert(1);
    myList.insert(2);
    myList.insert(3);
    myList.display();
    
    return 0;
}

// Output
1 -> 2 -> 3 -> nullptr

Explanation

In this code:

• We define a Node structure to represent each element in the linked list.
• The LinkedList class contains methods for inserting elements at the end and displaying the linked list.
• In the main function, we create an instance of LinkedList, insert three elements, and then display the list.

Advantages

1. Dynamic Size: Linked lists can grow or shrink dynamically, unlike arrays, which have fixed sizes.
2. Insertions and Deletions: Insertions and deletions are efficient operations in linked lists, especially when done at the beginning or in the middle.
3. No Wasted Memory: Linked lists do not require a contiguous block of memory, reducing memory waste.

Disadvantages

1. Random Access: Accessing an element at a specific index takes O(n) time in a singly linked list, whereas arrays offer constant-time access O(1).
2. Memory Overhead: Each node in a linked list requires extra memory for the next pointer.
3. Traversal Overhead: Traversing a linked list requires O(n) time, whereas arrays allow for direct access to elements.

Difference Between Arrays and Linked List

1. Memory Allocation:
   1. Arrays: Contiguous block of memory allocated for an array, where each element occupies a fixed-size space in memory. This means elements are stored in adjacent memory locations.
   2. Linked Lists: Elements in a linked list are not stored in contiguous memory locations. Each element (node) contains a data field and a reference (pointer) to the next element in the sequence. Memory for each node is allocated dynamically.
2. Insertion and Deletion:
   1. Arrays: Insertion and deletion in arrays can be less efficient, especially if elements need to be shifted to accommodate the change. In the worst case, inserting or deleting an element can have a time complexity of O(n), where n is the number of elements in the array.
   2. Linked Lists: Insertion and deletion operations are more efficient in the linked lists, especially for operations in the middle of the list, as they only require adjusting the pointers. But for worst case it too takes O(n) time.
3. Access Time:
   1. Arrays: Accessing elements in an array is generally faster compared to linked lists, especially when using indexing. Access time is constant O(1) because the location of the element in known.
   2. Linked Lists: Accessing elements in a linked list can be slower because you have to traverse the list from the beginning to find the desired element. Access time in a linked list is O(n) in the worst case.
4. Memory Overhead:
   1. Arrays: Arrays have less memory overhead because they only store the elements themselves.
   2. Linked Lists: Linked lists have more memory overhead due to the additional memory required for storing pointers to the next elements.
5. Dynamic Memory Allocation:
   1. Arrays: In C++, arrays have a fixed size, and resizing them requires creating a new array and copying elements.
   2. Linked Lists: Linked lists can easily grow or shrink in size as elements are added or removed without requiring a complete copy of the data.

Linked List Operations

Linked list support various operations, including:

1. Insertion: Adding an element at the beginning, end, or any specific position in the list.
2. Deletion: Removing elements from the list, including the first, last, or a specific element.
3. Traversal: Iterating through the list to access or modify elements.
4. Searching: Finding a specific element based on its value.
5. Reversal: Inverting the order of elements in the list.
6. Merging: Combining two or more linked lists.

Practical Usage of Linked Lists

Linked lists are used in many real-world applications, such as:

1. Memory Allocation: Dynamic memory allocation systems often use linked lists to manage free memory blocks.
2. Text Editors: Implementing undo and redo functionality using a linked list of document states.
3. Music and Video Players: Managing playlists and tracks.
4. Symbol Tables: Data structures used in compilers and interpreters.