Linked Lists

Updated Nov 16, 2026 · 4 min read
On this page

    Arrays are great until you need to insert or remove in the middle, again and again: each change shifts everything after it. A linked list makes those changes O(1) if you already hold the right node, at the price of slow access by position. Linked list problems are common in interviews less because the structure is popular in real code and more because they test careful pointer handling under pressure.

    How it works

    Nodes and pointers

    Each node stores a value and a pointer to the next node; the list is reached only through head.
    Each node stores a value and a pointer to the next node; the list is reached only through head.

    A singly linked list is a chain of nodes. Each node holds a value and a pointer (next) to the following node. The last node points to null. You keep a reference to the first node, the head, and reach everything else by following pointers.

    class ListNode:
        def __init__(self, val=0, next=None):
            self.val = val
            self.next = next

    Nodes don't sit next to each other in memory, so there's no way to jump to the 5th node: you walk from head, one step at a time. A doubly linked list adds a prev pointer to each node, so you can also walk backwards and remove a node in O(1) when you only hold the node itself. LRU caches use exactly that.

    Insert and delete by rewiring

    To insert after node a, first point the new node at a.next, then point a at the new node; nothing else moves.
    To insert after node a, first point the new node at a.next, then point a at the new node; nothing else moves.

    To insert a new node after node a:

    1. new.next = a.next
    2. a.next = new

    The order matters. If you set a.next = new first, the rest of the list is lost. Deleting the node after a is one line: a.next = a.next.next.

    The dummy head

    A dummy node in front of the real head means the first node is never a special case; return dummy.next.
    A dummy node in front of the real head means the first node is never a special case; return dummy.next.

    Many bugs come from the head being special: deleting it, or inserting before it, needs different code from every other position. A dummy node placed before the head removes the special case. Do all the work from the dummy, then return dummy.next.

    Operations and costs

    OperationSingly linkedArray
    Access the k-th elementO(k)O(1)
    Insert or delete at headO(1)O(n)
    Insert or delete after a node you holdO(1)O(n)
    Insert at tail (with a tail pointer)O(1)O(1) amortized
    Search for a valueO(n)O(n)
    Extra memory per elementone pointer (two if doubly linked)none

    When to reach for it

    In interviews, you are usually handed a linked list rather than choosing one. Choose one yourself when:

    • You need O(1) insert and delete at both ends or in the middle, and you keep references to nodes (a doubly linked list plus a hash map gives an LRU cache).
    • You are merging or splicing sequences without copying them.

    Most linked list problems use a small set of techniques:

    • Dummy head for anything that might change the first node.
    • Two pointers, slow and fast: find the middle, detect a cycle, find the k-th node from the end.
    • Reverse in place with three pointers (prev, curr, next).
    • Merge two sorted lists by always attaching the smaller head.

    Example

    Remove every node with a given value. With a dummy head, the first node needs no special handling:

    def remove_value(head, target):
        dummy = ListNode(0, head)
        prev = dummy
        while prev.next:
            if prev.next.val == target:
                prev.next = prev.next.next   # unlink, stay on prev
            else:
                prev = prev.next
        return dummy.next
    ListNode removeValue(ListNode head, int target) {
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        while (prev.next != null) {
            if (prev.next.val == target) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }
        return dummy.next;
    }
    ListNode* removeValue(ListNode* head, int target) {
        ListNode dummy(0, head);
        ListNode* prev = &dummy;
        while (prev->next) {
            if (prev->next->val == target) {
                prev->next = prev->next->next;  // free the node here if you own it
            } else {
                prev = prev->next;
            }
        }
        return dummy.next;
    }
    func removeValue(head *ListNode, target int) *ListNode {
        dummy := &ListNode{Next: head}
        prev := dummy
        for prev.Next != nil {
            if prev.Next.Val == target {
                prev.Next = prev.Next.Next
            } else {
                prev = prev.Next
            }
        }
        return dummy.Next
    }

    Time: O(n). Space: O(1). With input 3 → 7 → 3 → 1 and target 3, the result is 7 → 1; with 3 → 3 it's an empty list, and the dummy makes that case work without extra code.

    Finding the middle uses slow and fast pointers: fast moves two steps for every one step of slow, so when fast reaches the end, slow is in the middle.

    def middle(head):
        slow = fast = head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        return slow   # for an even length, the second of the two middles

    Common mistakes

    • Losing the rest of the list. Save next before you overwrite a pointer.
    • Null checks. fast.next.next crashes if fast.next is null. Check fast and fast.next in the loop condition.
    • Forgetting the head case. Without a dummy, deleting the first node or inserting before it needs separate code.
    • Moving prev after a deletion. After unlinking a node, stay on prev, or you will skip the next match.
    • Returning the wrong head. After reversing or with a dummy, the head has changed; return the new one.
    • Cycles in your own code. A wrong pointer update can create a loop and your traversal never ends. Draw three nodes and trace each assignment.

    Say this in the interview

    • "I'll add a dummy node before the head so deleting the first node isn't a special case."
    • "I'll save curr.next before I change it so I don't lose the rest of the list."
    • "Slow and fast pointers find the middle in one pass with O(1) space."

    Used in