TheoryQuestion Papers
TheoryCSESemester IIIData Structure and AlgorithmsUnit II

Representation of Linked List in Memory

A linked list is a fundamental data structure in computer science. It primarily allows efficient insertion and deletion operations compared to arrays. Like arrays, it is also used to implement other data structures such as stacks, queues, and deques.

Memory Representation of a Linked List

Unlike arrays, where elements are stored in contiguous memory locations, linked lists allocate memory dynamically for each node. This means that each node can be located anywhere in memory and is connected via pointers.

Linked list

Let’s see how memory is allocated for a linked list. The images below illustrate this more clearly:

Linked list
  • Heap Memory: The nodes of a linked list are dynamically allocated from the heap. Heap memory is used for objects whose size may not be known at compile time and allows for dynamic memory management.
  • Stack Memory: The pointer head is typically defined within a function (like main). Local variables, including pointers, are stored in the stack, which has a fixed size and is automatically managed when functions are called and return.

Allocation & Garbage Collection

In linked lists, memory for nodes is dynamically allocated on the heap. Garbage collection ensures that unused nodes are deallocated, preventing memory leaks. Languages with automatic garbage collection, like Python and Java, handle this automatically. In C and C++, manual memory management is required—using malloc for allocation and free for deallocation.

Allocation

  • Dynamic Memory: Linked lists allocate memory for each node dynamically, meaning memory is requested as needed during runtime.

  • Heap Allocation: Nodes are typically allocated on the heap, a region of memory where memory can be dynamically requested and released.

  • malloc (in C/C++): The malloc function allocates memory for a node, and the address of the allocated memory is returned.

Garbage Collection

  • Unreachable Nodes: When a node in a linked list becomes unreachable (i.e., no longer referenced by any part of the program), it is considered garbage and is eligible for collection.

  • Automatic vs. Manual:

    • Automatic (e.g., Python, Java): The garbage collector automatically identifies and deallocates unreachable memory, freeing it for reuse.
    • Manual (e.g., C, C++): The programmer is responsible for explicitly deallocating memory using the free function when it’s no longer needed.

  • Mark-and-Sweep (used in some garbage collectors): This algorithm involves two phases: marking reachable objects and sweeping to reclaim memory occupied by garbage.

  • Copying (another garbage collection approach): The heap is divided into two halves, and live objects are copied to one half, allowing the other half to be reclaimed.

  • Reference Counting: Each object maintains a reference count. When the count drops to zero, the object is considered unreachable and can be deallocated.

Benefits of Garbage Collection

  • Prevents Memory Leaks: Automatically deallocating unreachable memory prevents memory leaks, which occur when memory is allocated but never freed, potentially leading to system instability.

  • Simplifies Memory Management: Automatic garbage collection simplifies programming by relieving developers of the burden of manual memory management.

  • Avoids Dangling Pointers: By deallocating unreachable memory, garbage collection helps avoid dangling pointers—pointers that refer to memory that has already been freed.

  • Avoids Double Free Errors: Garbage collection also prevents double-free errors, where the same memory region is freed more than once.

    // Allocation
Node* node = (Node*)malloc(sizeof(Node));
node->data = 10;

// Deallocation (when node is no longer needed)
free(node);

Operations on Linked List

Basic operations that can be performed on linked lists include:

  1. Traversal
  2. Removal of a node
  3. Insertion of a node
  4. Searching
  5. Sorting

For simplicity, singly linked lists will be used to explain these operations below.

1. Traversal of a Linked List

Traversing a linked list means going through it by following the links from one node to the next.

Traversal is typically done to search for a specific node, read or modify a node’s contents, remove a node, or insert a node before or after a specific node.

To traverse a singly linked list, start at the head node and follow the next pointers until NULL is reached, as shown in the animation below:

Traverse
#include <iostream>
using namespace std;

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

void traverseAndPrint(Node* head) {
    Node* currentNode = head;
    while (currentNode) {
        cout << currentNode->data << " -> ";
        currentNode = currentNode->next;
    }
    cout << "nullptr" << endl;
}

int main() {
    Node* node1 = new Node;
    Node* node2 = new Node;
    Node* node3 = new Node;
    Node* node4 = new Node;
    Node* node5 = new Node;

    node1->data = 7;
    node2->data = 11;
    node3->data = 3;
    node4->data = 2;
    node5->data = 9;

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = nullptr;

    traverseAndPrint(node1);

    // Free the allocated memory
    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;

    return 0;
}

Output:

7 -> 11 -> 3 -> 2 -> 9 -> nullptr

2. Deletion in a Linked List

  • At the beginning: Update the head to point to the next node.
  • At a specific position: Update the previous node’s next pointer to skip the deleted node.
  • At the end: Set the previous node’s next pointer to nullptr.
#include <iostream>
using namespace std;

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

// Utility to print the list
void traverse(Node* head) {
    Node* temp = head;
    while (temp) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "nullptr" << endl;
}

// Delete from beginning
Node* deleteFromBeginning(Node* head) {
    if (!head) return nullptr;
    Node* temp = head;
    head = head->next;
    delete temp;
    return head;
}

// Delete at a given position (0-based index)
Node* deleteAtPosition(Node* head, int pos) {
    if (!head) return nullptr;
    if (pos == 0) return deleteFromBeginning(head);
    Node* temp = head;
    for (int i = 0; temp && i < pos - 1; ++i)
        temp = temp->next;
    if (temp && temp->next) {
        Node* toDelete = temp->next;
        temp->next = toDelete->next;
        delete toDelete;
    }
    return head;
}

// Delete from end
Node* deleteFromEnd(Node* head) {
    if (!head || !head->next) {
        delete head;
        return nullptr;
    }
    Node* temp = head;
    while (temp->next && temp->next->next)
        temp = temp->next;
    delete temp->next;
    temp->next = nullptr;
    return head;
}

int main() {
    Node* head = new Node{7, new Node{11, new Node{3, new Node{2, new Node{9, nullptr}}}}};

    cout << "Original List:\n";
    traverse(head);

    head = deleteFromBeginning(head);
    cout << "\nAfter deleting from beginning:\n";
    traverse(head);

    head = deleteAtPosition(head, 2);
    cout << "\nAfter deleting from position 2:\n";
    traverse(head);

    head = deleteFromEnd(head);
    cout << "\nAfter deleting from end:\n";
    traverse(head);

    // Free remaining nodes
    while (head) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

Output:

Original List:
7 -> 11 -> 3 -> 2 -> 9 -> nullptr

After deleting from beginning:
11 -> 3 -> 2 -> 9 -> nullptr

After deleting from position 2:
11 -> 3 -> 9 -> nullptr

After deleting from end:
11 -> 3 -> nullptr

3. Insertion in a Linked List

Insertion involves adding a new node to the list. It can be done in three common ways:

  • At the beginning: Make the new node point to the current head and update the head.
  • At a given position (middle): Traverse the list up to the position and update pointers to insert the new node.
  • At the end: Traverse to the last node and append the new node by setting the last node’s next to point to it.
#include <iostream>
using namespace std;

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

// Utility to print the list
void printList(Node* head) {
    while (head) {
        cout << head->data << " -> ";
        head = head->next;
    }
    cout << "nullptr" << endl;
}

// Insert at beginning
Node* insertAtBeginning(Node* head, int value) {
    Node* newNode = new Node{value, head};
    return newNode;
}

// Insert at specific position (0-based index)
Node* insertAtPosition(Node* head, int value, int pos) {
    if (pos == 0) return insertAtBeginning(head, value);
    Node* temp = head;
    for (int i = 0; temp && i < pos - 1; ++i)
        temp = temp->next;

    if (!temp) {
        cout << "Position out of bounds.\n";
        return head;
    }

    Node* newNode = new Node{value, temp->next};
    temp->next = newNode;
    return head;
}

// Insert at end
Node* insertAtEnd(Node* head, int value) {
    Node* newNode = new Node{value, nullptr};
    if (!head) return newNode;
    Node* temp = head;
    while (temp->next)
        temp = temp->next;
    temp->next = newNode;
    return head;
}

int main() {
    Node* head = nullptr;

    head = insertAtBeginning(head, 10);
    head = insertAtBeginning(head, 5);
    cout << "After inserting 5 and 10 at beginning:\n";
    printList(head);

    head = insertAtEnd(head, 20);
    cout << "\nAfter inserting 20 at end:\n";
    printList(head);

    head = insertAtPosition(head, 15, 2);
    cout << "\nAfter inserting 15 at position 2:\n";
    printList(head);

    // Free memory
    while (head) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

Output:

After inserting 5 and 10 at beginning:
5 -> 10 -> nullptr

After inserting 20 at end:
5 -> 10 -> 20 -> nullptr

After inserting 15 at position 2:
5 -> 10 -> 15 -> 20 -> nullptr

4. Searching in a Linked List

This involves traversing the list and comparing each node’s data with the target value until a match is found or the end is reached.

#include <iostream>
using namespace std;

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

bool search(Node* head, int target) {
    Node* temp = head;
    while (temp) {
        if (temp->data == target) return true;
        temp = temp->next;
    }
    return false;
}

int main() {
    Node* head = new Node{4, new Node{15, new Node{7, new Node{29, nullptr}}}};

    cout << "Searching for 15: " << (search(head, 15) ? "Found" : "Not Found") << endl;
    cout << "Searching for 99: " << (search(head, 99) ? "Found" : "Not Found") << endl;

    // Free memory
    while (head) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

Output:

Searching for 15: Found
Searching for 99: Not Found

5. Sorting a Linked List

Linked lists are often sorted using Merge Sort, which is efficient and works well with linked lists due to their nature (no need for random access).

#include <iostream>
using namespace std;

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

// Utility to print the list
void printList(Node* head) {
    while (head) {
        cout << head->data << " -> ";
        head = head->next;
    }
    cout << "nullptr" << endl;
}

// Merge two sorted lists
Node* merge(Node* l1, Node* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->data < l2->data) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

// Find the middle of the list
Node* getMiddle(Node* head) {
    if (!head) return head;
    Node* slow = head;
    Node* fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// Merge sort implementation
Node* mergeSort(Node* head) {
    if (!head || !head->next) return head;
    Node* middle = getMiddle(head);
    Node* nextHalf = middle->next;
    middle->next = nullptr;

    Node* left = mergeSort(head);
    Node* right = mergeSort(nextHalf);

    return merge(left, right);
}

int main() {
    Node* head = new Node{8, new Node{3, new Node{1, new Node{7, new Node{5, nullptr}}}}};

    cout << "Original List:\n";
    printList(head);

    head = mergeSort(head);

    cout << "\nSorted List:\n";
    printList(head);

    // Free memory
    while (head) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

Output:

Original List:
8 -> 3 -> 1 -> 7 -> 5 -> nullptr

Sorted List:
1 -> 3 -> 5 -> 7 -> 8 -> nullptr

Doubly Linked Lists

A doubly linked list is a more advanced data structure than a singly linked list, offering several advantages. The primary advantage is that it allows efficient traversal of the list in both directions. This is possible because each node contains a pointer to both the previous node and the next node. As a result, insertion and deletion operations can be performed more efficiently, and the list can be traversed forward and backward with ease.

Doubly Linked List

Representation

In a doubly linked list, each node consists of three fields:

  • Data
  • Pointer to the next node (next)
  • Pointer to the previous node (prev)
Doubly Linked List
struct Node {
    // To store the value or data
    int data;

    // Pointer to the previous node
    Node* prev;

    // Pointer to the next node
    Node* next;

    // Constructor
    Node(int d) {
        data = d;
        prev = next = nullptr;      
    }
};

Each node in a doubly linked list stores the data it holds, a pointer to the next node, and a pointer to the previous node. By connecting these nodes via the next and prev pointers, we can traverse the list in both directions—forward and backward—which is the key characteristic of a doubly linked list.

1. Traversal in a Doubly Linked List

Traversal in a doubly linked list involves visiting each node, processing its data, and moving to the next or previous node using the next and prev pointers.

Step-by-Step Approach

  1. Start from the head of the list.

  2. Traverse forward:

    • Visit the current node and process its data (e.g., print it).
    • Move to the next node using current = current->next.
    • Repeat until the end of the list (current == nullptr).

  3. Optionally, traverse backward:

    • Start from the tail (last node).
    • Visit the current node and process its data.
    • Move to the previous node using current = current->prev.
    • Repeat until the beginning of the list (current == nullptr).

This traversal is useful for displaying or processing all nodes in a doubly linked list.

// C++ Program for Forward Traversal (Iterative) of a Doubly Linked List

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node *next;
    Node *prev;

    Node(int val) {
        data = val;
        next = nullptr;
        prev = nullptr;
    }
};

// Function to traverse the doubly linked list in forward direction
void forwardTraversal(Node *head) {
    Node *curr = head;

    while (curr != nullptr) {
        cout << curr->data << " ";
        curr = curr->next;
    }

    cout << endl;
}

int main() {
    // Create a hardcoded doubly linked list:
    // 1 <-> 2 <-> 3
    Node *head = new Node(1);
    Node *second = new Node(2);
    Node *third = new Node(3);

    head->next = second;
    second->prev = head;
    second->next = third;
    third->prev = second;

    cout << "Forward Traversal: ";
    forwardTraversal(head);

    return 0;
}

Output

Forward Traversal: 1 2 3
  • Time Complexity: O(n), where n is the number of nodes in the list.
  • Auxiliary Space: O(1)

2. Finding the Length of a Doubly Linked List

A doubly linked list (DLL) is a type of linked list where each node has two pointers:

  1. One pointing to the next node.
  2. One pointing to the previous node.

To find the length of a doubly linked list, we traverse the list while counting the nodes.

Step-by-Step Approach

  1. Initialize a counter: Start with count = 0.

  2. Start from the head: Set a pointer (current) to the head.

  3. Traverse the list:

    • While current is not nullptr, increment count.
    • Move to the next node: current = current->next.

  4. End the loop: When current becomes nullptr, stop.

  5. Return the count.

#include <bits/stdc++.h>
using namespace std;

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

    Node(int val) {
        data = val;
        next = nullptr;
        prev = nullptr;
    }
};

// Function to find the size of the linked list
int findSize(Node *curr) {
    int size = 0;
    while (curr != nullptr) {
        size++;
        curr = curr->next;
    }
    return size;
}

int main() {
    // Create a hardcoded doubly linked list:
    // 1 <-> 2 <-> 3 <-> 4
    Node *head = new Node(1);
    head->next = new Node(2);
    head->next->prev = head;
    head->next->next = new Node(3);
    head->next->next->prev = head->next;
    head->next->next->next = new Node(4);
    head->next->next->next->prev = head->next->next;

    cout << "Length of the list: " << findSize(head);
    return 0;
}

Output

Length of the list: 4

3. Insertion in a Doubly Linked List

Insertion in a Doubly Linked List (DLL) involves adding a new node at a specific position while maintaining the connections between nodes. Since each node contains a pointer to both the previous and the next node, insertion requires adjusting these pointers carefully.

There are three primary types of insertion in a Doubly Linked List:

1. Insertion at the Beginning

  1. Create a new node with the given data.
  2. Set the next pointer of the new node to the current head.
  3. If the list is not empty, update the prev pointer of the current head to point to the new node.
  4. Update the head of the list to the new node.
// C++ program to insert a node at the beginning of a doubly linked list

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *next, *prev;

    Node(int new_data) {
        data = new_data;
        next = prev = NULL;
    }
};

// Function to insert a new node at the front of the doubly linked list
Node* insertAtFront(Node* head, int new_data) {
    Node* new_node = new Node(new_data);
    new_node->next = head;

    if (head != NULL)
        head->prev = new_node;

    return new_node;
}

void printList(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        cout << " " << curr->data;
        curr = curr->next;
    }
    cout << endl;
}

int main() {
    // Create a hardcoded doubly linked list:
    // 2 <-> 3 <-> 4
    Node* head = new Node(2);
    head->next = new Node(3);
    head->next->prev = head;
    head->next->next = new Node(4);
    head->next->next->prev = head->next;

    cout << "Original Linked List:";
    printList(head);

    cout << "After inserting node at the front:";
    int data = 1;
    head = insertAtFront(head, data);
    printList(head);

    return 0;
}

Output

Original Linked List: 2 3 4
After inserting node at the front: 1 2 3 4
  • Time Complexity: O(1)
  • Auxiliary Space: O(1)

2. Insertion at the End

  1. Create a new node with the given data.
  2. If the list is empty, set the new node as the head.
  3. Traverse the list to find the last node.
  4. Set the next pointer of the last node to the new node.
  5. Set the prev pointer of the new node to the last node.
// C++ program to insert a node at the end of a doubly linked list

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *next, *prev;

    Node(int new_data) {
        data = new_data;
        next = prev = nullptr;
    }
};

Node* insertEnd(Node* head, int new_data) {
    Node* new_node = new Node(new_data);

    if (head == NULL) {
        return new_node;
    }

    Node* curr = head;
    while (curr->next != NULL) {
        curr = curr->next;
    }

    curr->next = new_node;
    new_node->prev = curr;

    return head;
}

void printList(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        cout << curr->data << " ";
        curr = curr->next;
    }
    cout << endl;
}

int main() {
    // Create a hardcoded doubly linked list:
    // 1 <-> 2 <-> 3
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->prev = head;
    head->next->next = new Node(3);
    head->next->next->prev = head->next;

    cout << "Original Linked List: ";
    printList(head);

    cout << "Inserting node with data 4 at the end: ";
    int data = 4;
    head = insertEnd(head, data);
    printList(head);

    return 0;
}

Output

Original Linked List: 1 2 3 
Inserting node with data 4 at the end: 1 2 3 4
  • Time Complexity: O(N), where N is the number of nodes
  • Auxiliary Space: O(1)

3. Insertion at a Specific Position

  1. Create a new node with the given data.
  2. If inserting at the beginning, follow the steps for insertion at the start.
  3. Traverse the list to find the node after which the new node should be inserted.
  4. Set the next pointer of the new node to the next of the current node.
  5. Set the prev pointer of the new node to the current node.
  6. Update the prev pointer of the next node to point to the new node (if it exists).
  7. Update the next pointer of the current node to point to the new node.
// C++ program to insert a node at a given position

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *next, *prev;

    Node(int new_data) {
        data = new_data;
        next = prev = nullptr;
    }
};

Node* insertAtPosition(Node* head, int pos, int new_data) {
    Node* new_node = new Node(new_data);

    // Insertion at the beginning
    if (pos == 1) {
        new_node->next = head;
        if (head != NULL)
            head->prev = new_node;
        return new_node;
    }

    Node* curr = head;
    for (int i = 1; i < pos - 1 && curr != NULL; ++i) {
        curr = curr->next;
    }

    if (curr == NULL) {
        cout << "Position is out of bounds." << endl;
        delete new_node;
        return head;
    }

    new_node->prev = curr;
    new_node->next = curr->next;

    if (curr->next != NULL)
        curr->next->prev = new_node;

    curr->next = new_node;

    return head;
}

void printList(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        cout << curr->data << " ";
        curr = curr->next;
    }
    cout << endl;
}

int main() {
    // Create a hardcoded doubly linked list:
    // 1 <-> 2 <-> 4
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->prev = head;
    head->next->next = new Node(4);
    head->next->next->prev = head->next;

    cout << "Original Linked List: ";
    printList(head);

    cout << "Inserting node with data 3 at position 3: ";
    int data = 3;
    int pos = 3;
    head = insertAtPosition(head, pos, data);
    printList(head);

    return 0;
}

Output

Original Linked List: 1 2 4 
Inserting node with data 3 at position 3: 1 2 3 4
  • Time Complexity: O(N)
  • Auxiliary Space: O(1)

4. Deletion in a Doubly Linked List

Deletion in a Doubly Linked List (DLL) involves removing a node while maintaining the integrity of the list. Since each node contains pointers to both its previous and next nodes, deletion requires careful pointer adjustments to ensure no broken links occur.

1. Deletion at the Beginning

  1. Check if the list is empty. If it is, return as there is nothing to delete.
  2. Store the current head node in a temporary variable.
  3. Move the head pointer to the next node.
  4. If the new head exists, update its prev pointer to NULL.
  5. Delete the old head node to free memory.
// C++ program to delete the head node 
// from a singly linked list

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node *next;
    Node(int x) {
        data = x;
        next = nullptr;
    }
};

// Delete the head node and return the new head
Node* deleteHead(Node* head) {

    // Check if the list is empty
    if (head == nullptr)
        return nullptr;

    // Store the current head in a temporary variable
    Node* temp = head;

    // Move the head pointer to the next node
    head = head->next;

    // Free the memory of the old head node
    delete temp;

    return head;
}

void printList(Node* curr) {
    while (curr != nullptr) {
        cout << curr->data << " ";
        curr = curr->next;
    }
}

int main() {

    // Create a hardcoded linked list:
    // 3 -> 12 -> 15 -> 18
    Node* head = new Node(3);
    head->next = new Node(12);
    head->next->next = new Node(15);
    head->next->next->next = new Node(18);
    
    head = deleteHead(head);
    printList(head);

    return 0;
}

Output

12 15 18
  • Time Complexity: O(1) — The deletion is performed in constant time.
  • Space Complexity: O(1)

2. Deletion at the End

  1. Check if the list is empty. If it is, return.
  2. Traverse the list to find the last node.
  3. Store the last node in a temporary variable.
  4. Update the next pointer of the second-last node to NULL, making it the new tail.
  5. Delete the last node to free memory.
// C++ Program to delete a node from the end of a Doubly Linked List

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *prev, *next;
    Node(int d) {
        data = d;
        prev = next = NULL;
    }
};

// Function to delete the last node of the doubly linked list
Node* delLast(Node* head) {

    // Corner cases
    if (head == NULL)
        return NULL;
    if (head->next == NULL) {
        delete head;
        return NULL;
    }

    // Traverse to the last node
    Node* curr = head;
    while (curr->next != NULL)
        curr = curr->next;

    // Update the previous node's next pointer
    curr->prev->next = NULL;

    // Delete the last node
    delete curr;

    return head;
}

void printList(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        cout << curr->data << " ";
        curr = curr->next;
    }
    cout << endl;
}

int main() {

    // Create a hardcoded doubly linked list:
    // 1 <-> 2 <-> 3
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->prev = head;
    head->next->next = new Node(3);
    head->next->next->prev = head->next;

    cout << "Original Linked List: ";
    printList(head);

    head = delLast(head);

    cout << "After Deletion at the end: ";
    printList(head);

    return 0;
}

Output

Original Linked List: 1 2 3 
After Deletion at the end: 1 2
  • Time Complexity: O(N), where N is the number of nodes in the list
  • Space Complexity: O(1)

3. Deletion at a Specific Position

  1. Check if the list is empty. If it is, return.
  2. Traverse the list to find the node to be deleted.
  3. Store the node to be deleted in a temporary variable.
  4. Update the next pointer of the previous node to point to the next node.
  5. Update the prev pointer of the next node to point to the previous node (if it exists).
  6. Delete the target node to free memory.
// C++ Program to delete a node at a specific position
// in a Doubly Linked List

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node *prev, *next;
    Node(int d) {
        data = d;
        prev = next = NULL;
    }
};

// Function to delete a node at a specific position
Node* delPos(Node* head, int pos) {

    if (head == NULL)
        return head;

    Node* curr = head;

    // Traverse to the node at the given position
    for (int i = 1; curr != NULL && i < pos; ++i)
        curr = curr->next;

    // If position is out of range
    if (curr == NULL)
        return head;

    // Update pointers
    if (curr->prev != NULL)
        curr->prev->next = curr->next;
    if (curr->next != NULL)
        curr->next->prev = curr->prev;

    // If deleting the head node
    if (head == curr)
        head = curr->next;

    delete curr;
    return head;
}

void printList(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        cout << curr->data << " ";
        curr = curr->next;
    }
    cout << endl;
}

int main() {

    // Create a hardcoded doubly linked list:
    // 1 <-> 2 <-> 3
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->prev = head;
    head->next->next = new Node(3);
    head->next->next->prev = head->next;

    head = delPos(head, 2);
    printList(head);

    return 0;
}

Output

1 3
  • Time Complexity: O(N), where N is the number of nodes
  • Space Complexity: O(1)

Advantages of Doubly Linked List

  • Efficient traversal in both directions: Allows movement forward and backward.
  • Easy insertion and deletion: Modifying a node is simpler due to the presence of both prev and next pointers.
  • Can be used to implement stacks and queues: Supports operations needed for these data structures.

Disadvantages of Doubly Linked List

  • More complex than singly linked lists: Requires maintaining two pointers per node.
  • More memory overhead: Additional space is needed to store the extra pointer.

Applications of Doubly Linked List

  • Undo/redo operations in text editors
  • Browser history management to navigate back and forth between visited pages
  • Playlist management in music players
  • Cache implementation (e.g., LRU Cache)
  • Implementation of Deque (double-ended queue)

Circular Linked List

A circular linked list is a data structure where the last node connects back to the first, forming a loop. This structure allows for continuous traversal without any interruptions. Circular linked lists are especially helpful for tasks like scheduling and managing playlists, allowing for smooth navigation. In this tutorial, we’ll cover the basics of circular linked lists, how to work with them, their advantages and disadvantages, and their applications.

A circular linked list is a special type of linked list where all the nodes are connected to form a circle. Unlike a regular linked list, which ends with a node pointing to NULL, the last node in a circular linked list points back to the first node. This means that you can keep traversing the list without ever reaching a NULL value.

Types of Circular Linked Lists

We can create a circular linked list from both singly linked lists and doubly linked lists. So, circular linked lists are basically of two types:

1. Circular Singly Linked List

In a circular singly linked list, each node has just one pointer called the “next” pointer. The next pointer of the last node points back to the first node, forming a circle. In this type of linked list, we can only move through the list in one direction.

Circular Linked List

2. Circular Doubly Linked List

In a circular doubly linked list, each node has two pointers: prev and next, similar to a doubly linked list. The prev pointer points to the previous node and the next pointer points to the next node. Here, in addition to the last node storing the address of the first node, the first node also stores the address of the last node.

Circular Linked List

Operations on the Circular Linked List

1. Insertion in the Circular Linked List

Insertion is a fundamental operation in linked lists that involves adding a new node to the list. The only extra step is connecting the last node to the first one. In the circular linked list mentioned below, we can insert nodes in four ways:

  • Insertion in an Empty Circular Linked List - To insert a node in an empty circular linked list, we create a new node with the given data, set its next pointer to point to itself, and update the last pointer to reference this new node.

    Circular Linked List
    #include <iostream>
using namespace std;

struct Node{
    int data;
    Node *next;
    Node(int value){
        data = value;
        next = nullptr;
    }
};

// Function to insert a node into an empty circular singly linked list
Node *insertInEmptyList(Node *last, int data){
    if (last != nullptr) return last;

    // Create a new node
    Node *newNode = new Node(data);

    // Point newNode to itself
    newNode->next = newNode;

    // Update last to point to the new node
    last = newNode;
    return last;
}

void printList(Node* last){
    if (last == NULL) return;

    // Start from the head node
    Node* head = last->next;
    while (true) {
        cout << head->data << " ";
        head = head->next;
        if (head == last->next) break;
    }
    cout << endl;
}

int main(){
    Node *last = nullptr;

    // Insert a node into the empty list
    last = insertInEmptyList(last, 1);

    // Print the list
    cout << "List after insertion: ";
    printList(last);

    return 0;
}

    Output

    List after insertion: 1
    • Time Complexity: O(1)
    • Auxiliary Space: O(1)

  • Insertion at the Beginning in Circular Linked List - To insert a new node at the beginning of a circular linked list, we create a new node and check if the list is empty. If it is, the new node points to itself. If not, we make the new node’s next pointer point to the current head (last->next) and update the last node’s next to the new node, preserving the circular structure.

    Circular Linked List
    #include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;

    Node(int value){
        data = value;
        next = nullptr;
    }
};

// Function to insert a node at the beginning of the circular linked list
Node* insertAtBeginning(Node* last, int value){
    Node* newNode = new Node(value);

    if (last == nullptr) {
        newNode->next = newNode;
        return newNode;
    }

    newNode->next = last->next;
    last->next = newNode;

    return last;
}

void printList(Node* last){
    if (last == NULL) return;

    Node* head = last->next;
    while (true) {
        cout << head->data << " ";
        head = head->next;
        if (head == last->next) break;
    }
    cout << endl;
}

int main(){
    Node* first = new Node(2);
    first->next = new Node(3);
    first->next->next = new Node(4);

    Node* last = first->next->next;
    last->next = first;

    cout << "Original list: ";
    printList(last);

    last = insertAtBeginning(last, 5);

    cout << "List after inserting 5 at the beginning: ";
    printList(last);

    return 0;
}

    Output

    Original list: 2 3 4 
List after inserting 5 at the beginning: 5 2 3 4
    • Time Complexity: O(1)
    • Auxiliary Space: O(1)

  • Insertion at the End in Circular Linked List - To insert a node at the end of a circular linked list, we create a new node. If the list is empty, we make it point to itself. Otherwise, we update the tail’s next pointer to the new node and then set the tail to the new node, preserving the circular linkage.

    Circular Linked List
    #include <iostream>
using namespace std;

struct Node{
    int data;
    Node *next;
    Node(int value){
        data = value;
        next = nullptr;
    }
};

// Function to insert a node at the end of a circular linked list
Node *insertEnd(Node *tail, int value){
    Node *newNode = new Node(value);
    if (tail == nullptr){
        tail = newNode;
        newNode->next = newNode;
    }
    else{
        newNode->next = tail->next;
        tail->next = newNode;
        tail = newNode;
    }
    return tail;
}

void printList(Node *last){
    if (last == NULL) return;

    Node *head = last->next;
    while (true){
        cout << head->data << " ";
        head = head->next;
        if (head == last->next) break;
    }
    cout << endl;
}

int main(){
    Node *first = new Node(2);
    first->next = new Node(3);
    first->next->next = new Node(4);

    Node *last = first->next->next;
    last->next = first;

    cout << "Original list: ";
    printList(last);

    last = insertEnd(last, 5);
    last = insertEnd(last, 6);

    cout << "List after inserting 5 and 6: ";
    printList(last);

    return 0;
}

    Output

    Original list: 2 3 4 
List after inserting 5 and 6: 2 3 4 5 6
    • Time Complexity: O(1)
    • Auxiliary Space: O(1)

4. Insertion at a Specific Position in Circular Linked List - To insert a node at a specific position in a circular linked list, we handle edge cases for an empty list and invalid positions. For valid positions, we traverse the list and adjust the pointers to insert the new node, updating the tail if it’s inserted at the end.

Circular Linked List
#include <iostream>
using namespace std;

struct Node{
    int data;
    Node *next;
    Node(int value){
        data = value;
        next = nullptr;
    }
};

// Function to insert a node at a specific position in a circular linked list
Node *insertAtPosition(Node *last, int data, int pos){
    if (last == nullptr){
        if (pos != 1){
            cout << "Invalid position!" << endl;
            return last;
        }
        Node *newNode = new Node(data);
        last = newNode;
        last->next = last;
        return last;
    }

    Node *newNode = new Node(data);
    Node *curr = last->next;

    if (pos == 1){
        newNode->next = curr;
        last->next = newNode;
        return last;
    }

    for (int i = 1; i < pos - 1; ++i){
        curr = curr->next;
        if (curr == last->next){
            cout << "Invalid position!" << endl;
            return last;
        }
    }

    newNode->next = curr->next;
    curr->next = newNode;

    if (curr == last) last = newNode;

    return last;
}

void printList(Node *last){
    if (last == NULL) return;

    Node *head = last->next;
    while (true){
        cout << head->data << " ";
        head = head->next;
        if (head == last->next) break;
    }
    cout << endl;
}

int main(){
    Node *first = new Node(2);
    first->next = new Node(3);
    first->next->next = new Node(4);

    Node *last = first->next->next;
    last->next = first;

    cout << "Original list: ";
    printList(last);

    int data = 5, pos = 2;
    last = insertAtPosition(last, data, pos);
    cout << "List after insertions: ";
    printList(last);

    return 0;
}

Output

Original list: 2 3 4 
List after insertions: 2 5 3 4

Deletion from a Circular Linked List

Deletion involves removing a node from the linked list. The main difference is that we need to ensure the list remains circular after the deletion. We can delete a node in a circular linked list in three ways:

  1. Delete the first node in a circular linked list

    To delete the first node of a circular linked list, we check if the list is empty or has only one node. If so, we handle those cases by deleting the node and updating the last pointer. For multiple nodes, we update the last node’s next pointer to skip the head and free the head node, returning the updated last pointer.

    Circular Linked List
    #include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int value) {
        data = value;
        next = nullptr;
    }
};

// Function to delete the first node of the circular linked list
Node* deleteFirstNode(Node* last) {
    if (last == nullptr) {
        // If the list is empty
        cout << "List is empty" << endl;
        return nullptr;
    }

    Node* head = last->next;

    if (head == last) {
        // If there is only one node in the list
        delete head;
        last = nullptr;
    } else {
        // More than one node in the list
        last->next = head->next;
        delete head;
    }

    return last;
}

void printList(Node* last) {
    if(last == NULL) return ;
 
    Node *head = last->next;
    while (true){
        cout << head->data << " ";
        head = head->next;
        if (head == last->next) break;
    }
    cout << endl;
}

int main() {
    // Create circular linked list: 2, 3, 4
    Node* first = new Node(2);
    first->next = new Node(3);
    first->next->next = new Node(4);

    Node* last = first->next->next;
    last->next = first;

    cout << "Original list: ";
    printList(last);

    // Delete the first node
    last = deleteFirstNode(last);

    cout << "List after deleting first node: ";
    printList(last);

    return 0;
}

    Output

    Original list: 2 3 4 
List after deleting first node: 3 4

  2. Delete a specific node in a circular linked list

    To delete a specific node from a circular linked list, we handle empty list and single-node cases. For other nodes, we use two pointers to find the node, update the previous node’s next pointer to skip the target, and delete it, updating the last pointer if needed.

    Circular Linked List
    #include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int value) {
        data = value;
        next = nullptr;
    }
};

// Function to delete a specific node in the circular linked list
Node* deleteSpecificNode(Node* last, int key) {
    if (last == nullptr) {
        // If the list is empty
        cout << "List is empty, nothing to delete." << endl;
        return nullptr;
    }

    Node* curr = last->next;
    Node* prev = last;

    // If the node to be deleted is the only node in the list
    if (curr == last && curr->data == key) {
        delete curr;
        last = nullptr;
        return last;
    }

    // If the node to be deleted is the first node
    if (curr->data == key) {
        last->next = curr->next;
        delete curr;
        return last;
    }

    // Traverse the list to find the node to be deleted
    while (curr != last && curr->data != key) {
        prev = curr;
        curr = curr->next;
    }

    // If the node to be deleted is found
    if (curr->data == key) {
        prev->next = curr->next;
        if (curr == last) {
            last = prev;
        }
        delete curr;
    } else {
        // If the node to be deleted is not found
        cout << "Node with data " << key
          << " not found." << endl;
    }

    return last;
}

// Function to print the circular linked list
void printList(Node* last) {
     if (last == NULL){
        cout << "List is Empty";
        return;
    }

    Node *head = last->next;
    while (true){
        cout << head->data << " ";
        head = head->next;
        if (head == last->next) break;
    }
    cout << endl;
}

int main() {
    // Create circular linked list: 2, 3, 4
    Node* first = new Node(2);
    first->next = new Node(3);
    first->next->next = new Node(4);

    Node* last = first->next->next;
    last->next = first;

    cout << "Original list: ";
    printList(last);

    // Delete a specific node
    int key = 3;
    last = deleteSpecificNode(last, key);

    cout << "List after deleting node " << key << ": ";
    printList(last);

    return 0;
}

    Output

    Original list: 2 3 4 
List after deleting node 3: 2 4

  3. Delete the last node in a circular linked list

    To delete the last node in a circular linked list, we handle the empty and single-node cases. For multiple nodes, we traverse to find the second-last node, update its next pointer to the head, delete the last node, and return the updated last pointer.

    Circular Linked List
    #include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int value) {
        data = value;
        next = nullptr;
    }
};

// Function to delete the last node in the circular linked list
Node* deleteLastNode(Node* last) {
    if (last == nullptr) {
        // If the list is empty
        cout << "List is empty, nothing to delete." << endl;
        return nullptr;
    }
    Node* head = last->next;

    // If there is only one node in the list
    if (head == last) {
        delete last;
        last = nullptr;
        return last;
    }
    // Traverse the list to find the second last node
    Node* curr = head;
    while (curr->next != last) {
        curr = curr->next;
    }
    // Update the second last node's next pointer
    // to point to head
    curr->next = head;
    delete last;
    last = curr;

    return last;
}

void printList(Node* last) {
   if(last == NULL) return;

    Node *head = last->next;
    while (true){
        cout << head->data << " ";
        head = head->next;
        if (head == last->next) break;
    }
    cout << endl;
}

int main() {
    // Create circular linked list: 2, 3, 4
    Node* first = new Node(2);
    first->next = new Node(3);
    first->next->next = new Node(4);

    Node* last = first->next->next;
    last->next = first;

    cout << "Original list: ";
    printList(last);

    // Delete the last node
    last = deleteLastNode(last);

    cout << "List after deleting last node: ";
    printList(last);

    return 0;
}

    Output

    Original list: 2 3 4 
List after deleting last node: 2 3

Searching in a Circular Linked List

Searching in a circular linked list is similar to searching in a regular linked list. We start at a given node and traverse the list until we either find the target value or return to the starting node. Since the list is circular, we must keep track of where we started to avoid an infinite loop.

#include <iostream>
using namespace std;
 
class Search {
private:
    class Node {
    public:
        int data;
        Node* next;
 
        Node(int data)
        {
            this->data = data;
            next = nullptr;
        }
    };
 
public:
    Node* head = nullptr;
    Node* tempo = nullptr;
 
    // Function to add new nodes at the end of the list
    void addNode(int data)
    {
        Node* new1 = new Node(data);
 
        // If linked list is empty
        if (head == nullptr) {
            head = new1;
        }
        else {
            tempo->next = new1;
        }
 
        tempo = new1;
 
        // last node points to the first node
        tempo->next = head;
    }
 
    void find(int key)
    {
        // temp will traverse the circular linked list for
        // searching the element
        Node* temp = head;
 
        // flag used to check if the element is found or not
        int f = 0;
        if (head == nullptr) {
            cout << "List is empty" << endl;
        }
        else {
            do {
                if (temp->data == key) {
                    cout << key << " Found" << endl;
                    f = 1;
                    break;
                }
                temp = temp->next;
            } while (temp != head);
 
            if (f == 0) {
                cout << key << " Not Found" << endl;
            }
        }
    }
};
 
// Driver code
int main()
{
    Search s;
 
    // Adds data to the list
    s.addNode(5);
    s.addNode(4);
    s.addNode(3);
    s.addNode(2);
 
    // Search for node 2 in the list
    int key = 2;
    s.find(key);
 
    // Search for node 6 in the list
    key = 6;
    s.find(key);
 
    return 0;

Output

2 Found  
6 Not Found

Advantages of Circular Linked Lists

  • In a circular linked list, the last node points to the first node. There are no null references, making traversal easier and reducing the chances of encountering null pointer exceptions.
  • We can traverse the list from any node and return to it without needing to restart from the head, which is useful in applications requiring circular iteration.
  • Circular linked lists can easily implement circular queues, where the last element connects back to the first, allowing for efficient resource management.
  • In a circular linked list, each node has a reference to the next node in the sequence. Although it doesn’t have a direct reference to the previous node like a doubly linked list, we can still find the previous node by traversing the list.

Disadvantages of Circular Linked Lists

  • Circular linked lists are more complex to implement than singly linked lists.
  • Traversing a circular linked list without a clear stopping condition can lead to infinite loops if not handled carefully.
  • Debugging can be more challenging due to the circular nature, as traditional methods of traversing linked lists may not apply.

Applications of Circular Linked Lists

  • They are used for time-sharing among different users, typically through a Round-Robin scheduling mechanism.
  • In multiplayer games, a circular linked list can be used to switch between players. After the last player’s turn, the list cycles back to the first player.
  • Circular linked lists are often used in buffering applications, such as streaming data, where data is continuously produced and consumed.
  • In media players, circular linked lists can manage playlists, allowing users to loop through songs continuously.
  • Browsers use circular linked lists to manage the cache. This allows you to navigate back through your browsing history efficiently by pressing the BACK button.

Linked List with Header Node

A linked list with a header node is a type of linked list that contains a special, often empty, node at the beginning of the list. This header node does not store actual data but serves as a reference point for the list. It simplifies certain operations and provides a consistent starting point, even when the list is empty. The header node's next pointer points to the first actual data node in the list, or NULL if the list is empty.

#include <iostream>
#include <cstdlib>

using namespace std;

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

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = new Node;
    if (newNode == nullptr) {
        cerr << "Failed to allocate memory for new node" << endl;
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = nullptr;
    return newNode;
}

// Function to create a linked list with a header node
Node* createLinkedListWithHeader() {
    Node* header = createNode(-1); // Dummy data for header
    return header;
}

// Function to insert a new node at the beginning of the list
void insertAtBeginning(Node* header, int data) {
    Node* newNode = createNode(data);
    newNode->next = header->next;
    header->next = newNode;
}

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

// Function to free the memory allocated for the linked list
void freeList(Node* header) {
    Node* current = header;
    Node* next;
    while (current != nullptr) {
        next = current->next;
        delete current;
        current = next;
    }
}

int main() {
    // Create a linked list with a header node
    Node* myList = createLinkedListWithHeader();

    // Insert elements into the list
    insertAtBeginning(myList, 3);
    insertAtBeginning(myList, 2);
    insertAtBeginning(myList, 1);

    // Print the list
    cout << "Linked List: ";
    printList(myList);

    // Free the memory used by the list
    freeList(myList);

    return 0;
}

Output

Linked List: 1 2 3

Applications

  • Linked lists can be used to implement stacks, queues, deques, sparse matrices, and the adjacency list representation of graphs.
  • Dynamic memory allocation in operating systems and compilers (linked list of free blocks).
  • Manipulation of polynomials.
  • Arithmetic operations on long integers.
  • In operating systems, they are used in memory management, process scheduling (e.g., circular linked list for round-robin scheduling), and file systems.
  • Algorithms that frequently insert or delete items from large collections of data.
  • LRU cache, which uses a doubly linked list to keep track of the most recently used items in a cache.

Applications of Linked Lists in the Real World:

  • The list of songs in a music player is linked to the previous and next songs.
  • In a web browser, previous and next web page URLs can be linked through the previous and next buttons (doubly linked list).
  • In an image viewer, the previous and next images can be linked with the help of the previous and next buttons (doubly linked list).
  • Circular linked lists can be used to implement structures that cycle through elements repeatedly.
  • Linked lists are preferred over arrays for implementing queue and deque data structures due to fast insertions and deletions from the front.
How's article quality?

Sign up to view full contents of the page

Arrays

Definition, 1d and 2d arrays, operations on arrays, sparse matrices, structures and arrays of structures.

Stacks

Representation of stack in memory, operations on stack and applications.

On this page

Representation of Linked List in Memory
Allocation & Garbage Collection
Allocation
Garbage Collection
Operations on Linked List
1. Traversal of a Linked List
2. Deletion in a Linked List
3. Insertion in a Linked List
4. Searching in a Linked List
5. Sorting a Linked List
Doubly Linked Lists
1. Traversal in a Doubly Linked List
2. Finding the Length of a Doubly Linked List
3. Insertion in a Doubly Linked List
4. Deletion in a Doubly Linked List
Circular Linked List
Types of Circular Linked Lists
Operations on the Circular Linked List
Linked List with Header Node
Applications