Linked Lists

Introduction to Linked Lists

A linked list is a linear data structure where elements are not stored in contiguous memory locations. Instead, each element (node) contains a data field and a reference (link) to the next node in the sequence. This structure allows for efficient insertion and deletion of elements from any position in the list.

Unlike arrays, linked lists do not have a fixed size and can grow or shrink dynamically during program execution. This flexibility makes linked lists suitable for applications where the size of the data structure may change frequently.

    ┌───────────┐     ┌───────────┐     ┌───────────┐     ┌───────────┐
    │ Data: 10  │     │ Data: 20  │     │ Data: 30  │     │ Data: 40  │
    │ Next: ────┼────>│ Next: ────┼────>│ Next: ────┼────>│ Next: NULL│
    └───────────┘     └───────────┘     └───────────┘     └───────────┘
         Head                                                  Tail
                        

Key Characteristics of Linked Lists

• Dynamic Size: Linked lists can grow or shrink during program execution.
• Efficient Insertions and Deletions: Inserting or deleting elements in a linked list is efficient, especially when compared to arrays.
• No Random Access: Unlike arrays, linked lists do not allow direct access to elements by index. To access an element, you must traverse the list from the beginning.
• Extra Memory: Linked lists require extra memory for storing the references (links) to the next node.
• Sequential Access: Elements in a linked list are accessed sequentially, starting from the first node.

Concept and Terminology

Before diving into the implementation details, let's understand the basic concepts and terminology associated with linked lists:

Node

A node is the basic building block of a linked list. Each node contains:

• Data: The value or information stored in the node.
• Next: A reference (or pointer) to the next node in the sequence.

In C++, a node can be represented as a structure or class:

struct Node {
    int data;       // Data stored in the node
    Node* next;     // Pointer to the next node
};
                    

Head

The head is a reference to the first node in the linked list. It serves as the starting point for traversing the list.

Tail

The tail is a reference to the last node in the linked list. The next pointer of the tail node is NULL, indicating the end of the list.

Empty List

An empty linked list is one that contains no nodes. In this case, the head reference is NULL.

    Head: NULL
                        

Single Node List

A linked list with only one node. In this case, both the head and tail reference the same node, and the next pointer of this node is NULL.

    ┌───────────┐
    │ Data: 10  │
    │ Next: NULL│
    └───────────┘
     Head & Tail
                        

Primitive Operations

Linked lists support several basic operations. Let's explore each of them:

1. Creating a Linked List

To create a linked list, we first define the node structure and then create nodes and link them together.

#include <iostream>
using namespace std;

// Node structure
struct Node {
    int data;
    Node* next;
};

int main() {
    // Create three nodes
    Node* head = new Node();
    Node* second = new Node();
    Node* third = new Node();
    
    // Assign data values
    head->data = 10;
    second->data = 20;
    third->data = 30;
    
    // Connect nodes
    head->next = second;
    second->next = third;
    third->next = NULL;
    
    // Print the linked list
    Node* current = head;
    while (current != NULL) {
        cout << current->data << " ";
        current = current->next;
    }
    
    // Free memory
    delete head;
    delete second;
    delete third;
    
    return 0;
}
                    

2. Inserting a Node

Nodes can be inserted at the beginning, end, or at a specific position in the linked list.

Insertion at the Beginning

    ┌───────────┐     ┌───────────┐     ┌───────────┐
    │ Data: 10  │     │ Data: 20  │     │ Data: 30  │
    │ Next: ────┼────>│ Next: ────┼────>│ Next: NULL│
    └───────────┘     └───────────┘     └───────────┘
         Head                                Tail
                        

    ┌───────────┐     ┌───────────┐     ┌───────────┐     ┌───────────┐
    │ Data: 5   │     │ Data: 10  │     │ Data: 20  │     │ Data: 30  │
    │ Next: ────┼────>│ Next: ────┼────>│ Next: ────┼────>│ Next: NULL│
    └───────────┘     └───────────┘     └───────────┘     └───────────┘
         Head                                                  Tail
                        

// Function to insert a node at the beginning of the linked list
void insertAtBeginning(Node** head_ref, int new_data) {
    // Allocate new node
    Node* new_node = new Node();
    
    // Put in the data
    new_node->data = new_data;
    
    // Make next of new node as head
    new_node->next = *head_ref;
    
    // Move the head to point to the new node
    *head_ref = new_node;
}
                    

Insertion at the End

    ┌───────────┐     ┌───────────┐     ┌───────────┐
    │ Data: 10  │     │ Data: 20  │     │ Data: 30  │
    │ Next: ────┼────>│ Next: ────┼────>│ Next: NULL│
    └───────────┘     └───────────┘     └───────────┘
         Head                                Tail
                        

    ┌───────────┐     ┌───────────┐     ┌───────────┐     ┌───────────┐
    │ Data: 10  │     │ Data: 20  │     │ Data: 30  │     │ Data: 40  │
    │ Next: ────┼────>│ Next: ────┼────>│ Next: ────┼────>│ Next: NULL│
    └───────────┘     └───────────┘     └───────────┘     └───────────┘
         Head                                                  Tail
                        

// Function to insert a node at the end of the linked list
void insertAtEnd(Node** head_ref, int new_data) {
    // Allocate new node
    Node* new_node = new Node();
    
    // Put in the data
    new_node->data = new_data;
    
    // This new node is going to be the last node, so make next of it as NULL
    new_node->next = NULL;
    
    // If the Linked List is empty, then make the new node as head
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }
    
    // Else traverse till the last node
    Node* last = *head_ref;
    while (last->next != NULL) {
        last = last->next;
    }
    
    // Change the next of last node
    last->next = new_node;
}
                    

Insertion After a Given Node

    ┌───────────┐     ┌───────────┐     ┌───────────┐
    │ Data: 10  │     │ Data: 20  │     │ Data: 30  │
    │ Next: ────┼────>│ Next: ────┼────>│ Next: NULL│
    └───────────┘     └───────────┘     └───────────┘
         Head                                Tail
                        

    ┌───────────┐     ┌───────────┐     ┌───────────┐     ┌───────────┐
    │ Data: 10  │     │ Data: 20  │     │ Data: 25  │     │ Data: 30  │
    │ Next: ────┼────>│ Next: ────┼────>│ Next: ────┼────>│ Next: NULL│
    └───────────┘     └───────────┘     └───────────┘     └───────────┘
         Head                                                  Tail
                        

// Function to insert a node after a given node
void insertAfter(Node* prev_node, int new_data) {
    // Check if the given prev_node is NULL
    if (prev_node == NULL) {
        cout << "The given previous node cannot be NULL";
        return;
    }
    
    // Allocate new node
    Node* new_node = new Node();
    
    // Put in the data
    new_node->data = new_data;
    
    // Make next of new node as next of prev_node
    new_node->next = prev_node->next;
    
    // Move the next of prev_node as new_node
    prev_node->next = new_node;
}
                    

3. Deleting a Node

Nodes can be deleted from the beginning, end, or from a specific position in the linked list.

Deletion from the Beginning

    ┌───────────┐     ┌───────────┐     ┌───────────┐
    │ Data: 10  │     │ Data: 20  │     │ Data: 30  │
    │ Next: ────┼────>│ Next: ────┼────>│ Next: NULL│
    └───────────┘     └───────────┘     └───────────┘
         Head                                Tail
                        

    ┌───────────┐     ┌───────────┐
    │ Data: 20  │     │ Data: 30  │
    │ Next: ────┼────>│ Next: NULL│
    └───────────┘     └───────────┘
         Head              Tail
                        

// Function to delete the first node of the linked list
void deleteFirstNode(Node** head_ref) {
    // If linked list is empty
    if (*head_ref == NULL) {
        return;
    }
    
    // Store head node
    Node* temp = *head_ref;
    
    // Move head to next node
    *head_ref = temp->next;
    
    // Free old head
    delete temp;
}
                    

Deletion from the End

    ┌───────────┐     ┌───────────┐     ┌───────────┐
    │ Data: 10  │     │ Data: 20  │     │ Data: 30  │
    │ Next: ────┼────>│ Next: ────┼────>│ Next: NULL│
    └───────────┘     └───────────┘     └───────────┘
         Head                                Tail
                        

    ┌───────────┐     ┌───────────┐
    │ Data: 10  │     │ Data: 20  │
    │ Next: ────┼────>│ Next: NULL│
    └───────────┘     └───────────┘
         Head              Tail
                        

// Function to delete the last node of the linked list
void deleteLastNode(Node** head_ref) {
    // If linked list is empty
    if (*head_ref == NULL) {
        return;
    }
    
    // If there is only one node
    if ((*head_ref)->next == NULL) {
        delete *head_ref;
        *head_ref = NULL;
        return;
    }
    
    // Find the second last node
    Node* second_last = *head_ref;
    while (second_last->next->next != NULL) {
        second_last = second_last->next;
    }
    
    // Delete last node
    delete second_last->next;
    
    // Change next of second last
    second_last->next = NULL;
}
                    

Deletion of a Node at a Given Position

    ┌───────────┐     ┌───────────┐     ┌───────────┐     ┌───────────┐
    │ Data: 10  │     │ Data: 20  │     │ Data: 30  │     │ Data: 40  │
    │ Next: ────┼────>│ Next: ────┼────>│ Next: ────┼────>│ Next: NULL│
    └───────────┘     └───────────┘     └───────────┘     └───────────┘
         Head                                                  Tail
                        

    ┌───────────┐     ┌───────────┐     ┌───────────┐
    │ Data: 10  │     │ Data: 20  │     │ Data: 40  │
    │ Next: ────┼────>│ Next: ────┼────>│ Next: NULL│
    └───────────┘     └───────────┘     └───────────┘
         Head                                Tail
                        

// Function to delete a node at a given position
void deleteNodeAtPosition(Node** head_ref, int position) {
    // If linked list is empty
    if (*head_ref == NULL) {
        return;
    }
    
    // Store head node
    Node* temp = *head_ref;
    
    // If head needs to be removed
    if (position == 0) {
        *head_ref = temp->next;
        delete temp;
        return;
    }
    
    // Find previous node of the node to be deleted
    for (int i = 0; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }
    
    // If position is more than number of nodes
    if (temp == NULL || temp->next == NULL) {
        return;
    }
    
    // Node temp->next is the node to be deleted
    // Store pointer to the next of node to be deleted
    Node* next = temp->next->next;
    
    // Free memory
    delete temp->next;
    
    // Unlink the deleted node from list
    temp->next = next;
}
                    

4. Traversing a Linked List

Traversing a linked list means visiting each node of the list exactly once. This is typically done to perform some operation on each node, such as printing its data.

// Function to print the linked list
void printList(Node* node) {
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
    cout << endl;
}
                    

5. Searching in a Linked List

Searching in a linked list involves traversing the list and checking if a node with the given value exists.

// Function to search for a node with given data
bool search(Node* head, int x) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == x) {
            return true;
        }
        current = current->next;
    }
    return false;
}
                    

Linked List Abstract Data Type

A linked list is an abstract data type (ADT) that specifies a collection of elements with specific operations but does not specify how these operations are implemented. The ADT defines what operations are allowed on the data structure, but not how these operations are implemented.

Linked List ADT Specification

The Linked List ADT can be defined as follows:

ADT LinkedList {
    // Data
    A collection of elements with sequential access
    
    // Operations
    void insertAtBeginning(element)     // Insert element at the beginning
    void insertAtEnd(element)           // Insert element at the end
    void insertAfter(node, element)     // Insert element after a given node
    void deleteFirstNode()              // Delete the first node
    void deleteLastNode()               // Delete the last node
    void deleteNodeAtPosition(position) // Delete node at a given position
    bool search(element)                // Search for an element
    void printList()                    // Print the linked list
    bool isEmpty()                      // Check if the linked list is empty
    int size()                          // Return the number of elements in the linked list
}
                    

This ADT specification defines what a linked list is and what operations it supports, but it does not specify how these operations are implemented. The implementation can vary depending on the specific requirements and constraints.

Linked List Variants

There are several variants of linked lists, each with its own characteristics and use cases. Let's explore some of the most common ones:

1. Singly Linked List

A singly linked list is the simplest type of linked list, where each node contains a data field and a reference (link) to the next node in the sequence. The last node's next reference points to NULL, indicating the end of the list.

    ┌───────────┐     ┌───────────┐     ┌───────────┐
    │ Data: 10  │     │ Data: 20  │     │ Data: 30  │
    │ Next: ────┼────>│ Next: ────┼────>│ Next: NULL│
    └───────────┘     └───────────┘     └───────────┘
         Head                                Tail
                        

We've already seen the implementation of a singly linked list in the previous sections.

2. Doubly Linked List

In a doubly linked list, each node contains a data field and two references (links): one to the next node and one to the previous node. This allows for traversal in both directions.

            ┌─────────────────┐     ┌─────────────────┐     ┌─────────────────┐
            │   Data: 10      │     │   Data: 20      │     │   Data: 30      │
    NULL <──┤ Prev:    Next: ─┼────>│ Prev:    Next: ─┼────>│ Prev:    Next: ─┼──> NULL
            └─────────────────┘     └─────────────────┘     └─────────────────┘
                 Head                                             Tail
                        

Here's a C++ implementation of a doubly linked list:

#include <iostream>
using namespace std;

// Node structure for doubly linked list
struct Node {
    int data;
    Node* next;
    Node* prev;
};

// Function to insert a node at the beginning of the doubly linked list
void insertAtBeginning(Node** head_ref, int new_data) {
    // Allocate new node
    Node* new_node = new Node();
    
    // Put in the data
    new_node->data = new_data;
    
    // Make next of new node as head and previous as NULL
    new_node->next = *head_ref;
    new_node->prev = NULL;
    
    // Change prev of head node to new node
    if (*head_ref != NULL) {
        (*head_ref)->prev = new_node;
    }
    
    // Move the head to point to the new node
    *head_ref = new_node;
}

// Function to insert a node at the end of the doubly linked list
void insertAtEnd(Node** head_ref, int new_data) {
    // Allocate new node
    Node* new_node = new Node();
    
    // Put in the data
    new_node->data = new_data;
    
    // This new node is going to be the last node, so make next of it as NULL
    new_node->next = NULL;
    
    // If the Linked List is empty, then make the new node as head
    if (*head_ref == NULL) {
        new_node->prev = NULL;
        *head_ref = new_node;
        return;
    }
    
    // Else traverse till the last node
    Node* last = *head_ref;
    while (last->next != NULL) {
        last = last->next;
    }
    
    // Change the next of last node
    last->next = new_node;
    
    // Make last node as previous of new node
    new_node->prev = last;
}

// Function to print the doubly linked list
void printList(Node* node) {
    Node* last = NULL;
    cout << "Traversal in forward direction: ";
    while (node != NULL) {
        cout << node->data << " ";
        last = node;
        node = node->next;
    }
    cout << endl;
    
    cout << "Traversal in reverse direction: ";
    while (last != NULL) {
        cout << last->data << " ";
        last = last->prev;
    }
    cout << endl;
}

int main() {
    // Start with the empty list
    Node* head = NULL;
    
    // Insert nodes at the beginning
    insertAtBeginning(&head, 30);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 10);
    
    // Insert node at the end
    insertAtEnd(&head, 40);
    
    // Print the doubly linked list
    printList(head);
    
    return 0;
}
                    

3. Linear and Circular Linked List

In a linear linked list, the last node's next reference points to NULL, indicating the end of the list. In contrast, in a circular linked list, the last node's next reference points back to the first node, forming a circle.

    ┌───────────┐     ┌───────────┐     ┌───────────┐
    │ Data: 10  │     │ Data: 20  │     │ Data: 30  │
    │ Next: ────┼────>│ Next: ────┼────>│ Next: NULL│
    └───────────┘     └───────────┘     └───────────┘
         Head                                Tail
                        

    ┌───────────┐     ┌───────────┐     ┌───────────┐
    │ Data: 10  │     │ Data: 20  │     │ Data: 30  │
    │ Next: ────┼────>│ Next: ────┼────>│ Next: ────┼─┐
    └───────────┘     └───────────┘     └───────────┘ │
         Head                                         │
           ^                                          │
           └──────────────────────────────────────────┘
                        

Here's a C++ implementation of a circular linked list:

#include <iostream>
using namespace std;

// Node structure
struct Node {
    int data;
    Node* next;
};

// Function to insert a node at the beginning of the circular linked list
void insertAtBeginning(Node** head_ref, int new_data) {
    // Allocate new node
    Node* new_node = new Node();
    
    // Put in the data
    new_node->data = new_data;
    
    // If the linked list is empty, make the new node as head and point it to itself
    if (*head_ref == NULL) {
        new_node->next = new_node;
        *head_ref = new_node;
        return;
    }
    
    // Find the last node
    Node* last = *head_ref;
    while (last->next != *head_ref) {
        last = last->next;
    }
    
    // Make next of new node as head
    new_node->next = *head_ref;
    
    // Make next of last node as new node
    last->next = new_node;
    
    // Move the head to point to the new node
    *head_ref = new_node;
}

// Function to insert a node at the end of the circular linked list
void insertAtEnd(Node** head_ref, int new_data) {
    // Allocate new node
    Node* new_node = new Node();
    
    // Put in the data
    new_node->data = new_data;
    
    // If the linked list is empty, make the new node as head and point it to itself
    if (*head_ref == NULL) {
        new_node->next = new_node;
        *head_ref = new_node;
        return;
    }
    
    // Find the last node
    Node* last = *head_ref;
    while (last->next != *head_ref) {
        last = last->next;
    }
    
    // Make next of new node as head
    new_node->next = *head_ref;
    
    // Make next of last node as new node
    last->next = new_node;
}

// Function to print the circular linked list
void printList(Node* head) {
    if (head == NULL) {
        cout << "List is empty" << endl;
        return;
    }
    
    Node* temp = head;
    do {
        cout << temp->data << " ";
        temp = temp->next;
    } while (temp != head);
    cout << endl;
}

int main() {
    // Start with the empty list
    Node* head = NULL;
    
    // Insert nodes at the beginning
    insertAtBeginning(&head, 30);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 10);
    
    // Insert node at the end
    insertAtEnd(&head, 40);
    
    // Print the circular linked list
    cout << "Circular Linked List: ";
    printList(head);
    
    return 0;
}
                    

4. Circular Doubly Linked List

A circular doubly linked list combines the features of both doubly linked lists and circular linked lists. Each node contains a data field and two references: one to the next node and one to the previous node. The last node's next reference points back to the first node, and the first node's previous reference points to the last node.

    ┌─────────────────┐     ┌─────────────────┐     ┌─────────────────┐
    │   Data: 10      │     │   Data: 20      │     │   Data: 30      │
┌───┤ Prev:    Next: ─┼────>│ Prev:    Next: ─┼────>│ Prev:    Next: ─┼───┐
│   └─────────────────┘     └─────────────────┘     └─────────────────┘   │
│            ^                      ^                      ^              │
│            │                      │                      │              │
└────────────┘                      │                      └──────────────┘
                                    │
                                   Head
                        

Representation of Stacks and Queues Using Linked Lists

Linked lists can be used to implement other data structures like stacks and queues. Let's see how:

1. Stack Implementation Using Linked List

A stack follows the Last In First Out (LIFO) principle. In a linked list implementation of a stack, we can use the head of the linked list as the top of the stack. Insertion (push) and deletion (pop) operations are performed at the head of the linked list.

    ┌───────────┐     ┌───────────┐     ┌───────────┐
    │ Data: 30  │     │ Data: 20  │     │ Data: 10  │
    │ Next: ────┼────>│ Next: ────┼────>│ Next: NULL│
    └───────────┘     └───────────┘     └───────────┘
         Top
    (Last In)                        (First In)
                        

Here's a C++ implementation of a stack using a linked list:

#include <iostream>
using namespace std;

// Node structure
struct Node {
    int data;
    Node* next;
};

class Stack {
private:
    Node* top;
    
public:
    // Constructor
    Stack() {
        top = NULL;
    }
    
    // Push operation
    void push(int x) {
        // Create new node
        Node* new_node = new Node();
        
        // Put in the data
        new_node->data = x;
        
        // Link the old list off the new node
        new_node->next = top;
        
        // Move the top to point to the new node
        top = new_node;
        
        cout << x << " pushed to stack" << endl;
    }
    
    // Pop operation
    int pop() {
        // Check for stack underflow
        if (isEmpty()) {
            cout << "Stack Underflow" << endl;
            return -1;
        }
        
        // Store the top node
        Node* temp = top;
        
        // Store the top data
        int popped = temp->data;
        
        // Move the top to the next node
        top = top->next;
        
        // Free memory
        delete temp;
        
        return popped;
    }
    
    // Peek operation
    int peek() {
        // Check for empty stack
        if (isEmpty()) {
            cout << "Stack is empty" << endl;
            return -1;
        }
        
        return top->data;
    }
    
    // Check if stack is empty
    bool isEmpty() {
        return top == NULL;
    }
    
    // Display stack elements
    void display() {
        // Check for stack underflow
        if (isEmpty()) {
            cout << "Stack is empty" << endl;
            return;
        }
        
        cout << "Stack elements: ";
        Node* temp = top;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
};

int main() {
    Stack s;
    
    s.push(10);
    s.push(20);
    s.push(30);
    
    s.display();
    
    cout << "Top element: " << s.peek() << endl;
    
    cout << s.pop() << " popped from stack" << endl;
    
    s.display();
    
    return 0;
}
                    

2. Queue Implementation Using Linked List

A queue follows the First In First Out (FIFO) principle. In a linked list implementation of a queue, we can use the head of the linked list as the front of the queue and the tail as the rear of the queue. Insertion (enqueue) is performed at the rear, and deletion (dequeue) is performed at the front.

    ┌───────────┐     ┌───────────┐     ┌───────────┐
    │ Data: 10  │     │ Data: 20  │     │ Data: 30  │
    │ Next: ────┼────>│ Next: ────┼────>│ Next: NULL│
    └───────────┘     └───────────┘     └───────────┘
        Front                              Rear
    (First Out)                         (Last In)
                        

Here's a C++ implementation of a queue using a linked list:

#include <iostream>
using namespace std;

// Node structure
struct Node {
    int data;
    Node* next;
};

class Queue {
private:
    Node* front;
    Node* rear;
    
public:
    // Constructor
    Queue() {
        front = rear = NULL;
    }
    
    // Enqueue operation
    void enqueue(int x) {
        // Create a new node
        Node* new_node = new Node();
        
        // Put in the data
        new_node->data = x;
        
        // The new node is going to be the last node, so make next of it as NULL
        new_node->next = NULL;
        
        // If queue is empty, make the new node as both front and rear
        if (isEmpty()) {
            front = rear = new_node;
            cout << x << " enqueued to queue" << endl;
            return;
        }
        
        // Change the next of rear
        rear->next = new_node;
        
        // Move the rear to the new node
        rear = new_node;
        
        cout << x << " enqueued to queue" << endl;
    }
    
    // Dequeue operation
    int dequeue() {
        // If queue is empty, return error
        if (isEmpty()) {
            cout << "Queue Underflow" << endl;
            return -1;
        }
        
        // Store the front node
        Node* temp = front;
        
        // Store the front data
        int dequeued = temp->data;
        
        // Move the front to the next node
        front = front->next;
        
        // If front becomes NULL, change rear also as NULL
        if (front == NULL) {
            rear = NULL;
        }
        
        // Free memory
        delete temp;
        
        return dequeued;
    }
    
    // Front operation
    int getFront() {
        // If queue is empty, return error
        if (isEmpty()) {
            cout << "Queue is empty" << endl;
            return -1;
        }
        
        return front->data;
    }
    
    // Rear operation
    int getRear() {
        // If queue is empty, return error
        if (isEmpty()) {
            cout << "Queue is empty" << endl;
            return -1;
        }
        
        return rear->data;
    }
    
    // Check if queue is empty
    bool isEmpty() {
        return front == NULL;
    }
    
    // Display queue elements
    void display() {
        // If queue is empty, return
        if (isEmpty()) {
            cout << "Queue is empty" << endl;
            return;
        }
        
        cout << "Queue elements: ";
        Node* temp = front;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
};

int main() {
    Queue q;
    
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    
    q.display();
    
    cout << "Front element: " << q.getFront() << endl;
    cout << "Rear element: " << q.getRear() << endl;
    
    cout << q.dequeue() << " dequeued from queue" << endl;
    
    q.display();
    
    return 0;
}
                    

Application of Linked List - Garbage Collection

Garbage collection is a form of automatic memory management. The garbage collector attempts to reclaim memory occupied by objects that are no longer in use by the program. Linked lists are often used in the implementation of garbage collectors.

Mark and Sweep Algorithm

One of the most common garbage collection algorithms is the Mark and Sweep algorithm. It consists of two phases:

1. Mark Phase

In this phase, the garbage collector traverses the object graph starting from the root objects (objects that are directly accessible from the program) and marks all reachable objects as "in use".

2. Sweep Phase

In this phase, the garbage collector scans the entire heap and reclaims memory from objects that are not marked as "in use".

Linked lists are used in the implementation of the free list, which is a data structure that keeps track of free memory blocks. When memory is reclaimed during the sweep phase, it is added to the free list. When the program needs to allocate memory, it first checks the free list to see if there's a suitable block available.

    ┌───────────┐     ┌───────────┐     ┌───────────┐
    │ Size: 64  │     │ Size: 128 │     │ Size: 32  │
    │ Next: ────┼────>│ Next: ────┼────>│ Next: NULL│
    └───────────┘     └───────────┘     └───────────┘
        Free List
                        

Reference Counting

Another garbage collection technique is reference counting. In this approach, each object has a count of the number of references to it. When the reference count drops to zero, the object is no longer accessible and can be reclaimed.

Linked lists can be used to implement a list of objects with zero reference counts, which are candidates for garbage collection.

Advantages of Using Linked Lists in Garbage Collection

• Dynamic Size: The free list can grow or shrink as needed.
• Efficient Insertion and Deletion: Memory blocks can be added to or removed from the free list efficiently.
• Memory Coalescing: Adjacent free blocks can be merged to form larger blocks, reducing fragmentation.

Summary

In this section, we covered linked lists, a fundamental data structure in computer science:

• Introduction to linked lists and their key characteristics
• Basic concepts and terminology: node, head, tail, etc.
• Primitive operations: creating, inserting, deleting, traversing, and searching
• Linked list as an Abstract Data Type (ADT)
• Variants of linked lists: singly linked list, doubly linked list, circular linked list, etc.
• Implementation of stacks and queues using linked lists
• Application of linked lists in garbage collection

Linked lists are versatile data structures with numerous applications in computer science. Understanding linked lists is essential for solving many algorithmic problems and implementing various features in software applications.