parikshan

Linked List

The core idea

A linked list is a sequence where each node knows only where the next one is. You cannot index into it; you walk it. That single constraint produces a small family of techniques: dummy heads to avoid edge-case bugs at the start, two-pointer (slow/fast) tricks to find the middle or detect cycles, and in-place pointer reversal to flip a sublist.

Linked lists are unfashionable in application code because arrays beat them on cache locality. They remain the right answer in two places: when you need O(1) insert/delete at arbitrary positions given a node reference (LRU caches), and when memory layout is fragmented (kernel data structures, allocator free lists). Most importantly for this catalog, they are the cleanest way to learn pointer reasoning, which transfers to trees and graphs.

When to reach for it

Trigger phrases:

  • "given the head of a linked list"
  • "reverse the list / sublist"
  • "find the middle / kth from end"
  • "detect a cycle / find where it starts"
  • "merge two / k sorted lists"
  • "rearrange nodes without copying values"

If the problem could be solved trivially by copying the list to an array, ask whether the spec forbids it (often it does; otherwise the problem is uninteresting).

How to approach

  1. Draw the list with arrows on paper. Always. The bugs live in the arrows you don't draw.
  2. Use a dummy head for any problem that might delete or replace the first node. The dummy makes the first node behave like the rest.
  3. For "find a position in one pass", use slow / fast pointers. Slow walks one step, fast walks two; when fast reaches the end, slow is at the middle.
  4. For "reverse a sublist", carry three pointers: prev, curr, nxt. At each step: stash nxt = curr.next, redirect curr.next = prev, advance.

Real-world applications

  • LRU / LFU caches: doubly-linked lists give O(1) move-to-front.
  • Operating-system schedulers: ready queues are often doubly-linked.
  • Music / playlist apps: previous and next track.
  • Undo-redo trees in editors.
  • Garbage collectors: free lists of unused memory blocks.
  • Networking: kernel packet buffers (sk_buff in Linux).

In the AI-integrated workspace

Linked-list code that an agent writes is famously off-by-one. The two failure modes:

  • Missing dummy head: the agent writes a special case for head == null and another for "delete head", then forgets one when the problem changes shape. Always demand a dummy.
  • Lost-tail bug: when reversing, the agent reassigns curr.next before saving curr.next. The reverse silently truncates after one step.

Code review checklist: (1) is there a dummy node? (2) does every curr.next = ... happen after nxt = curr.next is stored? (3) does the function return the new head, not the original head?

Also: linked-list problems are where AI agents are most likely to confidently produce plausible but wrong code, because the bugs do not show up on length-1 or length-2 inputs. Always test with the empty list, the single-node list, and a list of exactly the loop's boundary length.

Problems in this cluster

Easy: reverse-linked-list, merge-two-sorted-lists, middle-of-linked-list, palindrome-linked-list. Medium: remove-nth-from-end, add-two-numbers, lru-cache.

Start with reverse-linked-list. The three-pointer dance there is the muscle memory every later linked-list problem reuses.