Linked Lists Explained: Singly, Doubly & Circular — Operations, Complexity, Patterns

In plain words — the treasure hunt analogy

Imagine a treasure hunt where each clue card tells you only one thing: the location of the next clue. To find clue #7 you must start at clue #1 and follow the chain — there's no way to jump directly to #7. But if you're standing at clue #5 and want to insert a new clue between #5 and #6, you just change what #5 points to: it now points at your new card, and your new card points to #6. No one else moves. That's a linked list: pointer surgery at a known position is instant; getting to the position requires walking the chain.

Nodes and pointers

Arrays gain their power from contiguity — and pay for it with O(n) shifting on every middle insertion. The linked list abandons contiguity entirely: each element lives in its own independently-allocated node, holding the value plus a pointer (reference) to the next node. The structure exists only as a chain of pointers, held by a single external reference to the first node, the head. Rearranging the chain means rewriting a couple of pointers — no shifting, ever.

Singly linked list: 3 → 7 → 9 → 14 → null

  head
   │
   ▼
 ┌───┬───┐   ┌───┬───┐   ┌────┬───┐   ┌────┬───┐
 │ 3 │ ●─┼──►│ 7 │ ●─┼──►│  9 │ ●─┼──►│ 14 │ / │
 └───┴───┘   └───┴───┘   └────┴───┘   └────┴───┘
  node 0      node 1      node 2       node 3
  (val|next)                           (/ = null)

Each node lives at an arbitrary memory address — no formula
to compute "where is node 3?" directly.

To access node 2 (value 9):
  start at head (node 0) → follow .next → node 1 → follow .next → node 2 ✓
  Cost: 2 hops = O(position) = O(n) worst case

The three variants

• Singly linked: each node points to `next` only. Cheapest in memory (one pointer per node); you can only walk forward, and deleting a node requires a reference to the node *before* it.
• Doubly linked: each node has `next` and `prev`. You can walk both ways and delete a node given only a reference to that node itself — at the cost of one extra pointer per node and twice the pointer bookkeeping on every mutation. Usually paired with a tail reference for O(1) operations at both ends.
• Circular: the last node points back to the first (singly or doubly). Natural for round-robin rotation — schedulers, turn-taking, ring buffers — because 'next' never runs off the end. The traversal termination condition changes from 'until null' to 'until back at the start', a classic source of infinite loops.

Doubly linked list with head and tail references

         head                              tail
          │                                │
          ▼                                ▼
       ┌──┬──┬──┐    ┌──┬──┬──┐    ┌──┬──┬──┐
  null │/ │ 3│ ●├───►│●│  7│ ●├───►│●│ 9 │/│ null
       └──┴──┴──┘◄───┤  ├──┤  ◄────┤  ├──┤  │
                     └──┴──┴──┘    └──┴──┴──┘
       (prev|val|next)

Circular singly linked list (3 nodes):

   head
    │
    ▼
  ┌───┬───┐   ┌───┬───┐   ┌───┬───┐
  │ A │ ●─┼──►│ B │ ●─┼──►│ C │ ●─┼──┐
  └───┴───┘   └───┴───┘   └───┴───┘  │
  ▲                                   │
  └───────────────────────────────────┘
  C.next points back to A — no null sentinel

Core operations, step by step

Insertion at the head — O(1)

1. Create the new node with the value.
2. Set newNode.next = head (the new node now points at the old first node — do this FIRST).
3. Set head = newNode.

insertAtHead(value):
    newNode      ← Node(value)
    newNode.next ← head         # wire forward BEFORE updating head
    head         ← newNode      # now head points to new first node
    size         ← size + 1

# WRONG ORDER (loses the list):
#   head         ← newNode      ← now old first node is unreachable
#   newNode.next ← head         ← this just points newNode to itself

Order matters: assign head = newNode before wiring newNode.next and the rest of the list is orphaned — unreachable and, in unmanaged languages, leaked. Almost every linked-list bug is a pointer update done in the wrong order; the antidote is drawing boxes and arrows before writing code. Seriously: draw it.

Insertion after a known node — O(1)

1. newNode.next = prevNode.next (save the next link first)
2. prevNode.next = newNode (splice the new node in)

Deletion after a known node (singly) — O(1)

1. target = prevNode.next (the node to remove).
2. prevNode.next = target.next (splice it out of the chain).
3. Clear target.next if your environment benefits from it (helps garbage collectors; mandatory manual free in C/C++).

Notice what's constant-time and what isn't: the pointer surgery is O(1), but finding the node to operate on is O(n) — you must walk from the head, following pointers one hop at a time, because nodes are scattered across memory with no address formula. 'O(1) insertion' is only real when you already hold a reference to the neighborhood.

Insert node 5 between nodes A and B:

BEFORE:
  … → [A | ●] → [B | ●] → …
             └──────────►

STEP 1: newNode.next = A.next   (newNode points to B)
  … → [A | ●] → [B | ●] → …
             │
             ▼
          [5 | ●]──────────►B

STEP 2: A.next = newNode        (A now points to newNode)
  … → [A | ●] → [5 | ●] → [B | ●] → …

Two pointer writes, no data movement, no matter where in the list. O(1) ✓

Full complexity table

*Deleting the tail of a singly list is O(n) even with a tail reference — you need the node *before* the tail to splice, and reaching it means walking from the head. That single row is why doubly linked lists exist. Space: O(n) in all variants, plus one pointer per node (singly) or two (doubly) of overhead — and because nodes are scattered across the heap, iteration is far less cache-friendly than an array scan, a constant-factor penalty Big-O doesn't show but hardware charges anyway.

The dummy-head (sentinel) trick

Operations at the head are annoyingly special: inserting or deleting there mutates `head` itself, forcing edge-case branches. The fix: allocate a permanent dummy node before the real first element, and let every operation work 'after some node' uniformly. Delete-by-value, merge, partition — all collapse into single loops with no head special-casing.

# Delete all nodes with value == target (with dummy head)

function deleteAll(head, target):
    dummy      ← Node(0)       # sentinel — never removed
    dummy.next ← head
    curr       ← dummy

    while curr.next ≠ null:
        if curr.next.val == target:
            curr.next ← curr.next.next   # splice out, curr stays
        else:
            curr ← curr.next             # advance

    return dummy.next   # real head (might have changed)

# Without the dummy, the loop needs a special case every time
# the head itself is the target — dummy eliminates that branch.

Two classic pointer patterns

Reversing a singly linked list — O(n) time, O(1) space

1. prev = null, curr = head.
2. Loop while curr is not null: save nextTemp = curr.next; flip curr.next = prev; advance prev = curr; advance curr = nextTemp.
3. When the loop ends, prev is the new head.

function reverseList(head):
    prev ← null
    curr ← head
    while curr ≠ null:
        nextTemp   ← curr.next  # 1. SAVE next (or we lose the list)
        curr.next  ← prev       # 2. FLIP the pointer
        prev       ← curr       # 3. advance prev
        curr       ← nextTemp   # 4. advance curr
    return prev                 # new head

Trace on:  1 → 2 → 3 → null

Start:    prev=null,  curr=1
Step 1:   nextTemp=2, 1.next=null,   prev=1,    curr=2
Step 2:   nextTemp=3, 2.next=1,      prev=2,    curr=3
Step 3:   nextTemp=null, 3.next=2,   prev=3,    curr=null
Return:   prev=3  →  list: 3 → 2 → 1 → null ✓

Fast & slow pointers — Floyd's cycle detection

Two pointers walk from the head: slow moves one node per step, fast moves two. If the list has a cycle, fast laps slow and they meet inside the cycle (once both are in the cycle, fast closes the gap by exactly one node per step, so a meeting is guaranteed within one lap); if not, fast hits null and the list is clean. O(n) time, O(1) space — no visited-set required.

function hasCycle(head):
    slow ← head
    fast ← head
    while fast ≠ null and fast.next ≠ null:
        slow ← slow.next        # one hop
        fast ← fast.next.next   # two hops
        if slow == fast:
            return true         # they met inside the cycle
    return false                # fast hit null → no cycle

FINDING THE CYCLE START (after detection):
    Reset one pointer to head; keep the other at the meeting point.
    Advance both one step at a time — they meet at the cycle entrance.
    (Mathematical proof: if the tail is distance 'a' from head,
     and the cycle length is 'c', they meet after 'a' steps. Works
     because slow traveled a+b and fast traveled a+b+c = 2(a+b)
     ⟹ c = a+b ⟹ a = c-b steps from the meeting point to entry.)

FINDING THE MIDDLE (no cycle):
    When fast reaches the end, slow is at the middle.
    Used in merge sort on lists and palindrome-list check.

Worked example: merge two sorted lists

A concrete operation that combines the dummy-head pattern with pointer manipulation. Given lists 1→3→5 and 2→4→6, produce 1→2→3→4→5→6.

function mergeSorted(l1, l2):
    dummy ← Node(0)
    curr  ← dummy

    while l1 ≠ null and l2 ≠ null:
        if l1.val ≤ l2.val:
            curr.next ← l1
            l1        ← l1.next
        else:
            curr.next ← l2
            l2        ← l2.next
        curr ← curr.next

    # Attach remaining nodes (at most one list is non-empty)
    if l1 ≠ null: curr.next ← l1
    if l2 ≠ null: curr.next ← l2

    return dummy.next

Trace: l1=1→3→5,  l2=2→4→6
  Compare 1 vs 2 → take 1. Tail: 1
  Compare 3 vs 2 → take 2. Tail: 1→2
  Compare 3 vs 4 → take 3. Tail: 1→2→3
  Compare 5 vs 4 → take 4. Tail: 1→2→3→4
  Compare 5 vs 6 → take 5. Tail: 1→2→3→4→5
  l1 exhausted → attach remaining l2 (6)
  Result: 1→2→3→4→5→6 ✓

Time: O(n + m).  Space: O(1) — only pointers reused, no new nodes.

Common pitfalls

• Losing the rest of the list. Overwriting a .next before saving what it pointed to orphans the tail. Save first (nextTemp = curr.next), then flip.
• Null / empty-list edge cases. Empty list, single node, operations on the head or tail — test all four on every list function. Most submissions that fail, fail here.
• Forgetting prev in singly lists. You cannot splice out a node you're standing on without the node behind you. Either track prev while walking or use a doubly linked list.
• Infinite loops in circular lists. 'while (node != null)' never terminates in a circular list. Terminate on returning to the start node instead.
• Using a linked list where an array wins. If your access pattern is 'read by index' or 'iterate fast', the array's cache behavior beats the list's O(1) splices in practice. Lists earn their keep only when cheap splicing at held positions is the hot operation.
• Off-by-one in fast/slow pointer. Check both fast ≠ null AND fast.next ≠ null before advancing two hops — failing either check causes a null-pointer crash on the second hop.

When to use vs avoid

• Use: queues and deques built by hand; LRU caches (doubly linked list + hash map — the canonical pairing, giving O(1) lookup AND O(1) move-to-front); adjacency lists in graphs; any workload dominated by splicing at known positions.
• Use: when you don't know the total number of elements up front and insertion/deletion at both ends is the primary operation (a deque for a sliding-window maximum problem, for example).
• Avoid: anything needing random access, binary search, or tight iteration over large data — arrays dominate all three due to cache locality.
• Avoid: when memory per element is tight — every node carries at least one pointer (8 bytes on 64-bit machines) of overhead beyond the payload.

Practice problems

1. Find kth from end. Find the kth node from the end of a singly linked list in one pass, O(1) space. Hint: start a 'fast' pointer k nodes ahead of 'slow'; when fast hits null, slow is at the target.
2. Detect cycle and find entry. Implement Floyd's algorithm to both detect the cycle and return the node where the cycle begins. Trace through the mathematical argument yourself.
3. Reverse in k-groups. Given a linked list and integer k, reverse every consecutive group of k nodes. (Hard — decomposes into: find group end, reverse group using the save-flip-advance pattern, reconnect.) This is a canonical interview hard problem.

Key takeaways

• A linked list is nodes + pointers: O(1) splicing at a held position, O(n) access by position — the array's mirror image.
• Singly = one pointer, forward only; doubly = bidirectional and O(1) delete-at-node; circular = last points to first, for rotation.
• Pointer updates have a mandatory order — save the old next before overwriting. Draw the boxes and arrows.
• The dummy-head sentinel removes head special-cases; fast/slow pointers detect cycles and find middles in O(1) space.
• In-memory, arrays usually beat lists on real hardware; lists win specifically when splice-at-position is the dominant operation.

Next: two structures usually built *on top of* arrays or lists — first the stack, then queues and deques. Drill linked-list questions in the **AI Learning app** between lessons.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play