Linked Lists

1. What is a Linked List?

A linked list is a linear data structure where each element (called a node) contains two things: the data itself and a pointer (reference) to the next node in the sequence. Unlike arrays, linked list nodes are not stored contiguously in memory -- they can be scattered anywhere in the heap.

Node Structure

Each node holds:

• Data -- the value stored in the node
• Next pointer -- a reference to the next node (or null if it is the last node)

Visual Representation

The head pointer always references the first node. The tail is the last node whose next pointer is null. Some implementations also maintain an explicit tail pointer for O(1) append operations.

Memory Layout: Array vs Linked List

2. Singly vs Doubly Linked List

Singly Linked List

Each node stores data and a single pointer to the next node. Traversal is one-directional -- you can only go forward.

Doubly Linked List

Each node stores data, a pointer to the next node, and a pointer to the previous node. Traversal goes both directions.

Trade-offs

3. Time Complexity

4. Implementation from Scratch

Singly Linked List

We build a Node class (data + next pointer) and a LinkedList class with core operations: append, prepend, insert_at, delete, search, display, and length.

Python -- Singly Linked List

Python
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None
        self._length = 0

    def append(self, data):
        """Add node to the end of the list."""
        new_node = Node(data)
        self._length += 1
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def prepend(self, data):
        """Add node to the beginning of the list. O(1)."""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        self._length += 1

    def insert_at(self, index, data):
        """Insert node at a specific index."""
        if index < 0 or index > self._length:
            raise IndexError("Index out of bounds")
        if index == 0:
            self.prepend(data)
            return
        new_node = Node(data)
        current = self.head
        for _ in range(index - 1):
            current = current.next
        new_node.next = current.next
        current.next = new_node
        self._length += 1

    def delete(self, data):
        """Delete the first node with the given value."""
        if not self.head:
            return
        if self.head.data == data:
            self.head = self.head.next
            self._length -= 1
            return
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                self._length -= 1
                return
            current = current.next

    def search(self, data):
        """Return True if value exists in the list."""
        current = self.head
        while current:
            if current.data == data:
                return True
            current = current.next
        return False

    def display(self):
        """Print the list as: 1 -> 2 -> 3 -> null"""
        parts = []
        current = self.head
        while current:
            parts.append(str(current.data))
            current = current.next
        print(" -> ".join(parts) + " -> null")

    def length(self):
        """Return the number of nodes."""
        return self._length


# Usage
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.prepend(0)
ll.insert_at(2, 99)
ll.display()       # 0 -> 1 -> 99 -> 2 -> 3 -> null
ll.delete(99)
ll.display()       # 0 -> 1 -> 2 -> 3 -> null
print(ll.search(2))  # True
print(ll.length())   # 4

JavaScript -- Singly Linked List

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

class LinkedList {
    constructor() {
        this.head = null;
        this._length = 0;
    }

    append(data) {
        const newNode = new Node(data);
        this._length++;
        if (!this.head) {
            this.head = newNode;
            return;
        }
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }

    prepend(data) {
        const newNode = new Node(data);
        newNode.next = this.head;
        this.head = newNode;
        this._length++;
    }

    insertAt(index, data) {
        if (index < 0 || index > this._length) {
            throw new Error("Index out of bounds");
        }
        if (index === 0) {
            this.prepend(data);
            return;
        }
        const newNode = new Node(data);
        let current = this.head;
        for (let i = 0; i < index - 1; i++) {
            current = current.next;
        }
        newNode.next = current.next;
        current.next = newNode;
        this._length++;
    }

    delete(data) {
        if (!this.head) return;
        if (this.head.data === data) {
            this.head = this.head.next;
            this._length--;
            return;
        }
        let current = this.head;
        while (current.next) {
            if (current.next.data === data) {
                current.next = current.next.next;
                this._length--;
                return;
            }
            current = current.next;
        }
    }

    search(data) {
        let current = this.head;
        while (current) {
            if (current.data === data) return true;
            current = current.next;
        }
        return false;
    }

    display() {
        const parts = [];
        let current = this.head;
        while (current) {
            parts.push(current.data);
            current = current.next;
        }
        console.log(parts.join(" -> ") + " -> null");
    }

    length() {
        return this._length;
    }
}

// Usage
const ll = new LinkedList();
ll.append(1);
ll.append(2);
ll.append(3);
ll.prepend(0);
ll.insertAt(2, 99);
ll.display();        // 0 -> 1 -> 99 -> 2 -> 3 -> null
ll.delete(99);
ll.display();        // 0 -> 1 -> 2 -> 3 -> null
console.log(ll.search(2));  // true
console.log(ll.length());   // 4

Doubly Linked List

The doubly linked list adds a prev pointer to each node. This enables O(1) deletion of a given node and backward traversal, at the cost of extra memory per node.

Python -- Doubly Linked List

Python
class DNode:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None


class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self._length = 0

    def append(self, data):
        """Add node to end. O(1) with tail pointer."""
        new_node = DNode(data)
        self._length += 1
        if not self.head:
            self.head = new_node
            self.tail = new_node
            return
        new_node.prev = self.tail
        self.tail.next = new_node
        self.tail = new_node

    def prepend(self, data):
        """Add node to beginning. O(1)."""
        new_node = DNode(data)
        self._length += 1
        if not self.head:
            self.head = new_node
            self.tail = new_node
            return
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node

    def delete_node(self, node):
        """Delete a specific node reference. O(1)."""
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev
        self._length -= 1

    def delete_value(self, data):
        """Delete first node with given value."""
        current = self.head
        while current:
            if current.data == data:
                self.delete_node(current)
                return
            current = current.next

    def search(self, data):
        """Return True if value exists."""
        current = self.head
        while current:
            if current.data == data:
                return True
            current = current.next
        return False

    def display_forward(self):
        parts = []
        current = self.head
        while current:
            parts.append(str(current.data))
            current = current.next
        print("null <-> " + " <-> ".join(parts) + " <-> null")

    def display_backward(self):
        parts = []
        current = self.tail
        while current:
            parts.append(str(current.data))
            current = current.prev
        print("null <-> " + " <-> ".join(parts) + " <-> null")

    def length(self):
        return self._length

JavaScript -- Doubly Linked List

JavaScript
class DNode {
    constructor(data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this._length = 0;
    }

    append(data) {
        const newNode = new DNode(data);
        this._length++;
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
            return;
        }
        newNode.prev = this.tail;
        this.tail.next = newNode;
        this.tail = newNode;
    }

    prepend(data) {
        const newNode = new DNode(data);
        this._length++;
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
            return;
        }
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head = newNode;
    }

    deleteNode(node) {
        if (node.prev) {
            node.prev.next = node.next;
        } else {
            this.head = node.next;
        }
        if (node.next) {
            node.next.prev = node.prev;
        } else {
            this.tail = node.prev;
        }
        this._length--;
    }

    deleteValue(data) {
        let current = this.head;
        while (current) {
            if (current.data === data) {
                this.deleteNode(current);
                return;
            }
            current = current.next;
        }
    }

    search(data) {
        let current = this.head;
        while (current) {
            if (current.data === data) return true;
            current = current.next;
        }
        return false;
    }

    displayForward() {
        const parts = [];
        let current = this.head;
        while (current) {
            parts.push(current.data);
            current = current.next;
        }
        console.log("null <-> " + parts.join(" <-> ") + " <-> null");
    }

    displayBackward() {
        const parts = [];
        let current = this.tail;
        while (current) {
            parts.push(current.data);
            current = current.prev;
        }
        console.log("null <-> " + parts.join(" <-> ") + " <-> null");
    }

    length() {
        return this._length;
    }
}

5. Common Linked List Techniques

Fast and Slow Pointers (Tortoise and Hare)

This technique uses two pointers that move at different speeds through the list. The slow pointer moves one step at a time, while the fast pointer moves two steps. This pattern is used to detect cycles and find the middle of a linked list.

Detect Cycle in a Linked List

If a cycle exists, the fast pointer will eventually "lap" the slow pointer and they will meet. If no cycle exists, the fast pointer reaches null.

Python
def has_cycle(head):
    """Floyd's cycle detection. O(n) time, O(1) space."""
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next          # Move 1 step
        fast = fast.next.next     # Move 2 steps
        if slow == fast:
            return True           # Cycle detected
    return False                  # No cycle

JavaScript
function hasCycle(head) {
    let slow = head;
    let fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;          // Move 1 step
        fast = fast.next.next;     // Move 2 steps
        if (slow === fast) {
            return true;            // Cycle detected
        }
    }
    return false;                  // No cycle
}

Find Middle of a Linked List

When fast reaches the end, slow is at the middle. If the list has even length, slow will be at the second of the two middle nodes.

Python
def find_middle(head):
    """Return middle node. O(n) time, O(1) space."""
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow   # slow is now at the middle

JavaScript
function findMiddle(head) {
    let slow = head;
    let fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Reversing a Linked List (Iterative)

This is one of the most important linked list operations. We use three pointers: prev, curr, and next_node. At each step, we reverse one link.

Step-by-Step Visual Walkthrough

Python
def reverse_list(head):
    """Reverse a singly linked list. O(n) time, O(1) space."""
    prev = None
    curr = head
    while curr:
        next_node = curr.next   # Save next
        curr.next = prev        # Reverse the link
        prev = curr             # Move prev forward
        curr = next_node        # Move curr forward
    return prev                 # prev is the new head

JavaScript
function reverseList(head) {
    let prev = null;
    let curr = head;
    while (curr !== null) {
        const nextNode = curr.next;  // Save next
        curr.next = prev;            // Reverse the link
        prev = curr;                 // Move prev forward
        curr = nextNode;             // Move curr forward
    }
    return prev;                     // prev is the new head
}

Merging Two Sorted Linked Lists

Use a two-pointer approach with a dummy head node. Compare current nodes from both lists, attach the smaller one to the merged list, and advance that pointer.

Python
def merge_two_lists(l1, l2):
    """Merge two sorted lists into one sorted list."""
    dummy = Node(0)       # Dummy head simplifies edge cases
    current = dummy

    while l1 and l2:
        if l1.data <= l2.data:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    # Attach the remaining nodes
    current.next = l1 if l1 else l2

    return dummy.next     # Skip the dummy node

JavaScript
function mergeTwoLists(l1, l2) {
    const dummy = new Node(0);
    let 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;
    }

    // Attach remaining nodes
    current.next = l1 !== null ? l1 : l2;

    return dummy.next;
}

6. LeetCode Problems

These are the essential linked list problems. Master these and you will handle most linked list interview questions.

206. Reverse Linked List (Full Solution)

Problem: Given the head of a singly linked list, reverse the list and return the reversed list.

Approach: Use three pointers -- prev, curr, and next_node. Walk through the list, reversing each link as you go. When curr becomes null, prev points to the new head.

Python
class Solution:
    def reverseList(self, head):
        # Initialize prev to None -- this becomes the new tail
        prev = None
        curr = head

        while curr:
            # 1) Save the next node before we break the link
            next_node = curr.next

            # 2) Reverse the link: point curr backwards
            curr.next = prev

            # 3) Advance prev and curr one step forward
            prev = curr
            curr = next_node

        # When loop ends, curr is None and prev is the new head
        return prev

# Time: O(n) -- visit each node once
# Space: O(1) -- only use pointer variables

JavaScript
var reverseList = function(head) {
    let prev = null;
    let curr = head;

    while (curr !== null) {
        // 1) Save next before breaking the link
        const nextNode = curr.next;

        // 2) Reverse the link
        curr.next = prev;

        // 3) Move pointers forward
        prev = curr;
        curr = nextNode;
    }

    // prev is the new head
    return prev;
};

// Time: O(n) | Space: O(1)

21. Merge Two Sorted Lists (Full Solution)

Problem: Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Approach: Create a dummy node as the anchor. Compare the front of both lists, attach the smaller node, advance that pointer. When one list is exhausted, attach the rest of the other.

Python
class Solution:
    def mergeTwoLists(self, list1, list2):
        # Dummy node eliminates edge cases for the first node
        dummy = ListNode(0)
        tail = dummy

        while list1 and list2:
            if list1.val <= list2.val:
                # Attach list1's current node
                tail.next = list1
                list1 = list1.next
            else:
                # Attach list2's current node
                tail.next = list2
                list2 = list2.next
            tail = tail.next

        # One list might still have nodes remaining
        tail.next = list1 if list1 else list2

        return dummy.next  # Skip the dummy

# Time: O(n + m) where n, m are list lengths
# Space: O(1) -- we reuse existing nodes

JavaScript
var mergeTwoLists = function(list1, list2) {
    const dummy = new ListNode(0);
    let tail = dummy;

    while (list1 !== null && list2 !== null) {
        if (list1.val <= list2.val) {
            tail.next = list1;
            list1 = list1.next;
        } else {
            tail.next = list2;
            list2 = list2.next;
        }
        tail = tail.next;
    }

    // Attach remaining nodes
    tail.next = list1 !== null ? list1 : list2;

    return dummy.next;
};

// Time: O(n + m) | Space: O(1)

141. Linked List Cycle (Full Solution)

Problem: Given the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if some node can be reached again by continuously following the next pointer.

Approach: Use Floyd's Tortoise and Hare algorithm. The slow pointer moves one step, the fast pointer moves two steps. If they ever meet, there is a cycle. If fast reaches null, there is no cycle.

Python
class Solution:
    def hasCycle(self, head):
        # Two pointers starting at head
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next           # Tortoise: 1 step
            fast = fast.next.next      # Hare: 2 steps

            if slow == fast:
                return True            # They met -- cycle exists!

        # Fast reached the end -- no cycle
        return False

# Time: O(n) -- at most 2 passes through the list
# Space: O(1) -- only two pointers

JavaScript
var hasCycle = function(head) {
    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow.next;            // Tortoise: 1 step
        fast = fast.next.next;       // Hare: 2 steps

        if (slow === fast) {
            return true;              // Cycle detected
        }
    }

    return false;                    // No cycle
};

// Time: O(n) | Space: O(1)

Other Key Problems (Approach Overview)

19. Remove Nth Node From End of List

Technique: Use two pointers separated by a gap of n. Advance the first pointer n steps ahead. Then move both pointers together until the first reaches the end. The second pointer is now at the node just before the one to remove.

143. Reorder List

Technique: Three-step process:

1. Find middle using slow/fast pointers
2. Reverse the second half of the list
3. Merge the two halves by alternating nodes

Input: 1 -> 2 -> 3 -> 4 -> 5 becomes 1 -> 5 -> 2 -> 4 -> 3

2. Add Two Numbers

Technique: Traverse both lists simultaneously, adding corresponding digits plus any carry. Create new nodes for each digit of the result. Remember to handle the final carry (e.g., 99 + 1 = 100 creates an extra node).

146. LRU Cache

Technique: Combine a doubly linked list (for O(1) removal and reinsertion to track recency) with a hash map (for O(1) key lookup). The most recently used item goes to the front; when capacity is exceeded, remove from the back (least recently used).

7. When to Use Linked Lists

Use linked lists when:

• Frequent insertions/deletions at the head -- O(1) vs O(n) for arrays
• You do not need random access -- you always iterate sequentially
• Implementing stacks -- push/pop at head are both O(1)
• Implementing queues -- enqueue at tail, dequeue at head (with tail pointer)
• Building an LRU cache -- doubly linked list + hash map
• Unknown or highly variable data size -- no need to pre-allocate or resize

Avoid linked lists when:

• You need random access by index -- use an array
• Memory is tight -- pointers add overhead per node
• Cache performance matters -- arrays have better locality
• You need binary search -- requires O(1) index access (use arrays)

8. Practice Quiz