Linked Lists

A linear data structure where elements are not stored at contiguous memory locations but are linked using pointers.

What is it?

A linked list is a chain of nodes, where each node contains data and a pointer to the next node. A perfect real-world example is your web browser's history. When you navigate from one page to another, a new node is created for the new page, and it points to the previous one. Clicking the "Back" button simply follows the pointer to the previous node. Unlike an array, inserting a new page between two existing pages in your history is incredibly efficient (O(1)). You just need to update the pointers of the surrounding nodes. The downside is that you can't instantly jump to the 10th page in your history; you have to traverse the first 9 nodes to get there (O(n) access time).

Time Complexity

AccessO(n)

SearchO(n)

InsertionO(1)

DeletionO(1)

Implementation Example

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

class LinkedList {
  constructor() {
    this.head = null;
  }
  
  // Method to add a node at the end
  append(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }
}

Linked Lists

Linked Lists Deep Dive

Linked lists trade random access for constant-time structural edits, which is ideal for editors, schedulers, and buffering systems.

?But why does this matter?

Pointer-rich structures place more pressure on CPU caches; thoughtful node sizing and pooling prevents GC churn.

Visual Flow

How it actually moves

Insert at head/tail

O(1)

Pointer rewiring touches only adjacent nodes.

Random access

O(n)

Nodes must be traversed sequentially to find index i.

Deletion

O(1)

Given a node reference, removal is immediate after pointer updates.

Insert node after target

Create the new node with the incoming value.

Point the new node’s next reference to target.next.

Update target.next to the new node.

If tracking tail pointers, update them when insertion occurs at the end.

The cost is constant because only neighboring pointers are touched.

Watch the best explainer

Data structures: Introduction to Linked List

mycodeschool

The classic linked-list explainer millions of engineers learned from.

Imagine a scavenger hunt

Each clue points you to the next location. You can add a new clue between two existing ones without rewriting the whole list, but you can’t skip directly to clue #50 without following the chain.

Real-world analogy

Music apps queue tracks by linking them so friends can add songs anywhere in the line-up.

Takeaway

Linked lists excel when insert/delete operations happen frequently at arbitrary positions.

Practical applications

• Undo/redo stacks in design tools where edits are replayed sequentially.
• Music players queuing tracks dynamically from different sources.
• Networking buffers (e.g., Linux sk_buff) that splice packets efficiently.

Technical insights

• Singly linked lists optimize for append or prepend operations; doubly linked lists enable bi-directional traversal.
• Sentinel nodes reduce conditionals by keeping head/tail pointers always valid.
• Memory pools or arena allocators mitigate fragmentation caused by per-node allocations.

When to reach for it

• Streaming scenarios with unpredictable insert positions
• Implementing LRU caches or schedulers

Operations Breakdown

Insert at head/tail

O(1)

Pointer rewiring touches only adjacent nodes.

Random access

O(n)

Nodes must be traversed sequentially to find index i.

Deletion

O(1)

Given a node reference, removal is immediate after pointer updates.

Best practices

• Prefer intrusive lists (where objects carry next/prev) to avoid wrapper allocations in systems code.
• Batch allocations of nodes to improve spatial locality.
• Embed size counters when frequent length queries are expected.

Common pitfalls

• Poor cache utilization leads to performance cliffs for traversal-heavy workloads.
• Losing track of head/tail after pointer updates introduces hard-to-debug leaks.
• Recursive list algorithms risk stack overflows on untrusted input size.

Every kind of Linked Lists

Interviewers rarely say which flavor they mean — they expect you to recognize it from the problem. Each variant below comes with the algorithms it unlocks.

Type 1 of 4

Singly Linked List

→ full page

Each node points forward only. Cheap insertion at the head, but you can never look back — which is exactly what the classic tricks exploit.

What to know

Fast/slow pointers meet inside a cycle (Floyd); resetting one to head finds the cycle start.
Reversal rewires next pointers one node at a time with three cursors (prev/curr/next).
A dummy head node removes every "is it the first node?" special case.

Algorithms to reach for

Floyd’s cycle detection

O(n)

Detect and locate loops without extra memory

Iterative reversal

O(n)

Reverse whole list or k-groups in place

Fast/slow middle finding

O(n)

Find midpoint in one pass (merge sort on lists)

Merge two sorted lists

O(n + m)

Zipper-merge by relinking, no allocation

In the wild: Hash table chaining buckets, immutable functional lists, memory allocator free lists.

Practice problems — hints, approach & solution on their own pages

Reverse Linked ListEasy Linked List Cycle IIMedium Middle of the Linked ListEasy Merge Two Sorted ListsEasy

Type 2 of 4

Doubly Linked List

→ full page

Nodes point both ways, so any node can delete itself in O(1) once you hold a reference to it — the key to LRU caches.

What to know

LRU cache = hashmap (key → node) + doubly linked list ordered by recency.
Sentinel head and tail nodes eliminate all edge cases at both ends.
Costs one extra pointer per node versus singly linked.

Algorithms to reach for

LRU cache (hashmap + DLL)

O(1) per op

O(1) get and put with eviction (LeetCode 146)

O(1) node unlink

O(1)

Remove a known node without traversal

In the wild: Browser back/forward history, MRU lists, text editor gap navigation, OS page replacement.

Practice problems — hints, approach & solution on their own pages

LRU CacheMedium Design Browser HistoryMedium Flatten a Multilevel Doubly Linked ListMedium

Type 3 of 4

Circular Linked List

→ full page

The tail points back to the head. Iteration never "ends", which models anything that goes around forever.

What to know

Round-robin scheduling walks the circle giving each node a time slice.
The Josephus problem (survivor in a killing circle) has an O(n) recurrence.
Termination checks compare against the start node instead of null.

Algorithms to reach for

Round-robin traversal

O(1) per step

Fair cyclic scheduling of tasks/players

Josephus elimination

O(n)

Find the surviving position in a circle

In the wild: CPU schedulers, multiplayer turn order, token-ring networks, carousel UIs.

Practice problems — hints, approach & solution on their own pages

Find the Winner of the Circular GameMedium

Type 4 of 4

Skip List

→ full page

A sorted linked list with express lanes: each node is promoted to higher levels by coin flips, giving O(log n) expected search without rotations.

What to know

Level-i lanes skip ~2^i nodes; search drops down a level when the next node overshoots.
Simpler to implement lock-free than balanced trees — why Redis chose it.
Expected O(log n) holds with high probability; worst case is O(n) but vanishingly rare.

Algorithms to reach for

Skip list search/insert/delete

O(log n) expected

Sorted-set operations with simple code

Range iteration

O(log n + k)

Walk bottom lane between two bounds

In the wild: Redis sorted sets (ZSET), LevelDB/RocksDB memtables, concurrent ordered maps.

Practice problems — hints, approach & solution on their own pages

Design SkiplistHard

Pseudo Code • Insert node after target

Flow Diagram

Create the new node with the incoming value.
Point the new node’s next reference to target.next.
Update target.next to the new node.
If tracking tail pointers, update them when insertion occurs at the end.

The cost is constant because only neighboring pointers are touched.

Hands-on code

Compare how the same idea looks in JavaScript, Python, and Go.

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

function insertAfter(target, value) {
  if (!target) return null;
  const node = new Node(value);
  node.next = target.next;
  target.next = node;
  return node;
}