#3 - Linked Lists - Data Structures and Algorithms using C++

Introduction to Linked Lists

A linked list is a fundamental data structure that consists of a sequence of elements, where each element points to the next element in the sequence. Unlike arrays, linked lists don't store elements in contiguous memory locations, making them more flexible for dynamic data management.

Key Advantages of Linked Lists:

Dynamic size - can grow or shrink during runtime
Efficient insertion and deletion at the beginning
Flexible memory allocation
No memory wastage as size can be adjusted

Types of Linked Lists

1. Singly Linked List

A singly linked list is the simplest type of linked list where each node contains data and a pointer to the next node in the sequence. The last node points to NULL.


class Node {
    int data;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

2. Doubly Linked List

In a doubly linked list, each node contains data and two pointers - one pointing to the next node and another pointing to the previous node. This allows for bidirectional traversal.


class DoublyNode {
    int data;
    DoublyNode next;
    DoublyNode prev;
    
    DoublyNode(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

3. Circular Linked List

A circular linked list is a variation where the last node points back to the first node, creating a circle. It can be either singly or doubly circular.

Essential Operations

Reversing a Linked List

Reversing a linked list is a fundamental operation that can be performed either iteratively or recursively.


Node reverseList(Node head) {
    Node prev = null;
    Node current = head;
    Node next = null;
    
    while (current != null) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

Floyd's Cycle Detection Algorithm

Also known as the "tortoise and hare" algorithm, this method detects cycles in a linked list using two pointers moving at different speeds.


boolean hasCycle(Node head) {
    if (head == null) return false;
    
    Node slow = head;
    Node fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

Merging Sorted Lists

Merging two sorted linked lists while maintaining the sort order is a common operation.


Node mergeSortedLists(Node l1, Node l2) {
    Node dummy = new Node(0);
    Node current = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.data <= l2.data) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    
    if (l1 != null) current.next = l1;
    if (l2 != null) current.next = l2;
    
    return dummy.next;
}

Common Interview Questions

1. Find the Middle Node

Question: How would you find the middle node of a linked list in one pass?

Answer: Use the slow and fast pointer technique. Move one pointer at normal speed and another at double speed. When the fast pointer reaches the end, the slow pointer will be at the middle.

2. Detect and Remove Cycle

Question: How would you detect and remove a cycle in a linked list?

Answer: First use Floyd's algorithm to detect the cycle. Then place one pointer at head and another at the meeting point. Move both one step at a time until they meet at the cycle's start. Remove the cycle by setting the next pointer to null.

3. Reverse in Groups

Question: How would you reverse a linked list in groups of k?

Answer: Use a recursive approach where you reverse k nodes at a time, then recursively call the function for the remaining nodes.

4. Intersection Point

Question: How would you find the intersection point of two linked lists?

Answer: Calculate the length difference of both lists. Move the pointer of the longer list ahead by the difference. Then move both pointers together until they meet at the intersection point.

Time Complexity Analysis

Operation	Singly Linked List	Doubly Linked List
Insertion at beginning	O(1)	O(1)
Insertion at end	O(n)	O(1)
Deletion at beginning	O(1)	O(1)
Deletion at end	O(n)	O(1)
Search	O(n)	O(n)

#3 - Linked Lists - Data Structures and Algorithms using C++ | Akash Vishwakarma