Interview OS
Back to Algorithms & Data Structures

Library

Linked lists

O(1) insert/delete with a pointer.

Linear

Overview

Linked lists store elements in nodes connected by pointers, trading random access for O(1) insertion and deletion at a known position. Mastery is about pointer manipulation — reversing, detecting cycles, and merging without losing nodes.

How it works

Linear
NodeTraverseMutateOutputValue+nextnode.nextWalk pointersO(n)SpliceO(1) at nodeUse
DataClientServiceEdge

Step by step, with examples

  1. 1

    Value+next

    • Nodes chained together by pointers.
  2. 2

    Walk pointers

    • Follow next until null.
  3. 3

    Splice

    • Insert or delete by relinking.
  4. 4

    Use

    • No random access; ideal for queues.
    • Example: LRU cache

Overview

Nodes linked by pointers; O(1) insertion/removal given a node, but O(n) access.

When to use it

  • Frequent splice operations
  • Implementing queues/deques
  • LRU cache (with hash map)

Reference

// Reverse a singly linked list
function reverse(head){
  let prev=null;
  while(head){ const n=head.next; head.next=prev; prev=head; head=n; }
  return prev;
}

Common pitfalls

  • Losing the next pointer before reassigning
  • Off-by-one with dummy heads

Where this content comes from

For full transparency, this content is curated and verified from these sources:

CLRS — Introduction to AlgorithmsCurated competitive-programming archivesOppZen-authored algorithm guides