Overview#

A linked list is a data structure made up of nodes connected in a chain. Each node stores data and points to the next node via a pointer. Unlike arrays, linked lists don’t rely on contiguous indices; instead, they rely on reference relationships between nodes.

The advantage of a linked list is that inserting and deleting nodes doesn’t require shifting large numbers of elements; the trade-off is that you can’t randomly access a position in O(1) like you can with an array.

In frontend development and algorithms, linked lists frequently appear in LRU caches, queues, undo stacks, virtual list scheduling, and various pointer problems.

Prerequisites

• Node references: linked lists chain nodes together via next
• Pointer rewiring: insertion and deletion are essentially modifying references
• Dummy head node: unifies the handling of the head node and ordinary nodes

Problem Definition#

Linked lists are well-suited for representing data where “order exists, but position doesn’t depend on an index.”

A singly linked list node can be abstracted as:

1
value + next

Multiple nodes chained together:

1
head -> A -> B -> C -> null

The problem linked lists solve is: when we only know a reference to some node, how do we efficiently change the connections around it?

Core Principle: Step-by-Step Diagrams#

1
Before insertion: A -> B
2
Step 1: X -> B
3
Step 2: A -> X
4
After insertion: A -> X -> B

1
Before deletion: A -> B -> C
2
After deletion: A ------> C

1
dummy -> head -> ...

Basic Operations and Complexity#

The most critical thing in linked list problems isn’t complexity—it’s the order of pointer updates. Get one node reference wrong and you might break the chain or create a cycle.

TypeScript Implementation#

1
class ListNode<T> {
2
  constructor(
3
    public value: T,
4
    public next: ListNode<T> | null = null,
5
  ) {}
6
}

1
function reverseList<T>(head: ListNode<T> | null): ListNode<T> | null {
2
  let prev: ListNode<T> | null = null;
3
  let current = head;
4

5
  while (current !== null) {
6
    const next = current.next;
7
    current.next = prev;
8
    prev = current;
9
    current = next;
10
  }
11

12
  return prev;
13
}

1
function removeElements<T>(head: ListNode<T> | null, target: T): ListNode<T> | null {
2
  const dummy = new ListNode<T>(target, head);
3
  let current: ListNode<T> | null = dummy;
4

5
  while (current.next !== null) {
6
    if (current.next.value === target) {
7
      current.next = current.next.next;
8
    } else {
9
      current = current.next;
10
    }
11
  }
12

13
  return dummy.next;
14
}

Engineering Optimization: Doubly Linked Lists and LRU#

A singly linked list can only be traversed forward. If you need O(1) deletion of an arbitrary node, you typically use a doubly linked list:

1
prev <- node -> next

An LRU cache is a combination of a doubly linked list and a hash map:

• Map is responsible for O(1) node lookup;
• The doubly linked list is responsible for O(1) moving of the most recently used node;
• The head represents the most recent, the tail represents the oldest.

1
class DoublyNode<K, V> {
2
  prev: DoublyNode<K, V> | null = null;
3
  next: DoublyNode<K, V> | null = null;
4

5
  constructor(
6
    public key: K,
7
    public value: V,
8
  ) {}
9
}

The value of linked lists in engineering often isn’t in using them alone, but in combining them with hash maps to supplement “order maintenance” capabilities.

Applications and Limitations#

Summary#

• Linked lists maintain order through reference relationships, not contiguous indices.
• The core of insertion and deletion is changing pointer directions.
• Dummy nodes can significantly reduce head-node boundary handling.
• To reverse a linked list, first save next, then modify the current node’s pointer.
• Linked lists are often combined with hash maps for caching and order maintenance.