Comprehensive Linked Lists Tutorial

Introduction to Linked Lists

A linked list is a linear data structure where elements are stored in nodes. Each node contains two parts: data and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory locations, making them dynamic in size.

Time Complexity: Access: O(n), Insertion: O(1) at head, Deletion: O(1) at head

Space Complexity: O(n)

Types of Linked Lists

1. Singly Linked List

In a singly linked list, each node points to the next node in the sequence. The last node points to null. Singly linked lists are simple and efficient for operations such as insertion and deletion at the head, but they require sequential access to traverse the list.

Example (C++):

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

Node* head = new Node();
head->data = 10;
head->next = nullptr;

2. Doubly Linked List

In a doubly linked list, each node contains two pointers: one pointing to the next node and another pointing to the previous node. This allows for bidirectional traversal, making it easier to traverse in both directions and delete nodes without needing to traverse from the head.

Example (C++):

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

Node* head = new Node();
head->data = 10;
head->next = nullptr;
head->prev = nullptr;

3. Circular Linked List

In a circular linked list, the last node points back to the first node, forming a loop. Circular linked lists can be useful for applications that require continuous looping over a list, such as implementing a round-robin scheduler.

Example (C++):

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

Node* head = new Node();
Node* second = new Node();
head->data = 10;
second->data = 20;
head->next = second;
second->next = head;

4. Circular Doubly Linked List

In a circular doubly linked list, the last node points to the first node and the first node points to the last node, with each node having pointers to both next and previous nodes. This allows for continuous looping in both directions, making it suitable for applications like implementing a playlist that can be navigated forward and backward.

Basic Operations

1. Insertion

Insertion can occur at the head, tail, or any position in the linked list. The operation's complexity depends on the position where the insertion occurs. Insertion at the head is O(1), while insertion at the tail requires O(n) unless a tail pointer is maintained.

Example (C++):

// Insert at the head of a singly linked list
void insertAtHead(Node*& head, int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = head;
    head = newNode;
}

2. Deletion

Deletion can occur at the head, tail, or any position in the linked list. Similar to insertion, the complexity depends on the position of the node to be deleted. Deletion at the head is O(1), while deleting a node in the middle or end requires O(n) for traversal.

Example (C++):

// Delete a node from a singly linked list
void deleteNode(Node*& head, int key) {
    Node* temp = head;
    Node* prev = nullptr;

    // If head node holds the key to be deleted
    if (temp != nullptr && temp->data == key) {
        head = temp->next;
        delete temp;
        return;
    }

    // Search for the key
    while (temp != nullptr && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    // If key was not present
    if (temp == nullptr) return;

    // Unlink the node
    prev->next = temp->next;
    delete temp;
}

3. Traversal

Traversal involves visiting each node in the linked list from the head to the last node. This operation is O(n) since each node needs to be visited sequentially.

Example (C++):

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

4. Searching

Searching involves finding whether a value exists in the linked list. This operation also has a time complexity of O(n) since each node must be checked sequentially.

Example (C++):

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

Advanced Concepts

1. Reversing a Linked List

Reversing a linked list changes the direction of all links so that the last node becomes the first node. This operation is commonly used in algorithms that require the data to be processed in reverse order.

The method used here involves iterating through the list while maintaining three pointers: prev, current, and next. As you traverse the list, you reverse the link between each pair of nodes by pointing the current node to its prev node.

Example (C++):

Node* reverse(Node* head) {
    Node* prev = nullptr;
    Node* current = head;
    Node* next = nullptr;

    while (current != nullptr) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    head = prev;
    return head;
}

2. Detecting a Loop in a Linked List

A loop in a linked list means that a node's next pointer points back to one of the previous nodes, creating a cycle. Detecting loops is crucial in scenarios like detecting infinite loops in algorithms.

The method used here is Floyd’s Cycle-Finding Algorithm, also known as the Tortoise and Hare algorithm. It involves two pointers, one moving twice as fast as the other. If there is a loop, these pointers will eventually meet; otherwise, the faster pointer will reach the end of the list.

Example (C++):

bool detectLoop(Node* head) {
    Node* slow = head;
    Node* fast = head;

    while (slow != nullptr && fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast)
            return true;
    }

    return false;
}

3. Merging Two Sorted Linked Lists

Merging two sorted linked lists into one sorted list is a common operation in algorithms like merge sort. This operation is crucial in scenarios where you need to combine multiple sorted sequences into a single sorted sequence.

The method used here involves recursively comparing the data of the two linked lists. The smaller data value is added to the new merged list, and the process is repeated with the remaining elements of the two lists.

Example (C++):

Node* mergeSortedLists(Node* l1, Node* l2) {
    if (!l1) return l2;
    if (!l2) return l1;

    if (l1->data < l2->data) {
        l1->next = mergeSortedLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeSortedLists(l1, l2->next);
        return l2;
    }
}

4. Removing Duplicates from a Linked List

In a sorted linked list, duplicates can be removed to ensure all elements are unique. This is often required when dealing with data that should not contain repeated entries.

The method used here involves traversing the list and comparing each node with its next node. If the data in the current node is the same as in the next node, the next node is skipped, effectively removing the duplicate.

Example (C++):

void removeDuplicates(Node* head) {
    Node* current = head;

    while (current != nullptr && current->next != nullptr) {
        if (current->data == current->next->data) {
            Node* nextNext = current->next->next;
            delete current->next;
            current->next = nextNext;
        } else {
            current = current->next;
        }
    }
}

When to Use Linked Lists

Linked lists are versatile data structures that can be used in various scenarios where dynamic memory allocation, efficient insertions, and deletions are required. Each type of linked list has its unique advantages and is suitable for specific use cases:

1. Singly Linked List

Singly linked lists are best used in situations where:

2. Doubly Linked List

Doubly linked lists are particularly useful when:

3. Circular Linked List

Circular linked lists are ideal in scenarios such as:

4. Circular Doubly Linked List

Circular doubly linked lists are particularly useful when:

Key Points and Summary