Linked Lists

A linked list is a linear data structure where elements are stored in nodes, and each node points to the next node via a reference (pointer). Unlike arrays, linked list nodes are not stored in contiguous memory — they can live anywhere in the heap, connected only by these pointers.

Arrays vs Linked Lists — The Core Difference

To understand why linked lists exist, you first need to see what makes arrays limiting in certain situations.

Arrays allocate a fixed block of contiguous memory. The runtime computes any element's address as base + index * elementSize, which is why random access is O(1). The downside: inserting or deleting in the middle requires shifting every element after the insertion point — an O(n) operation just to maintain contiguity.

Linked lists trade that random-access speed for dynamic, O(1) insert-and-delete at the head. Each node allocates independently, so there is no shifting. The cost is that you must traverse from the head to reach any node — O(n) access instead of O(1).

Property	Array	Linked List
Memory layout	Contiguous block	Scattered nodes on the heap
Size	Fixed (or amortized dynamic)	Grows and shrinks freely
Random access	O(1) — index arithmetic	O(n) — must traverse
Insert at head	O(n) — shift all elements	O(1) — update pointer
Insert at tail	O(1) amortized (dynamic array)	O(n) without tail pointer
Insert at middle	O(n) — shift elements	O(n) traversal + O(1) pointer swap
Delete at head	O(n) — shift all elements	O(1) — update head pointer
Cache performance	Excellent (spatial locality)	Poor (pointer chasing)

Note

Modern CPUs prefetch contiguous memory aggressively. Arrays often outperform linked lists in practice even when the theoretical complexity is the same, because of cache locality. Prefer linked lists when you need guaranteed O(1) head insertions/deletions and random access is rare.

Anatomy of a Node

Every linked list is built from nodes. A node holds two things:

val (or data) — the actual value stored in this node
next — a reference to the next node, or null if this is the last node

class Node {
  constructor(val) {
    this.val = val    // the data this node carries
    this.next = null  // pointer to the next node (null = end of list)
  }
}

Visually, a three-node list holding the values 10 → 20 → 30 looks like this:


  head
   |
   v
 +------+------+    +------+------+    +------+------+
 |  10  |  *---+--->|  20  |  *---+--->|  30  | null |
 +------+------+    +------+------+    +------+------+
   Node 1             Node 2             Node 3 (tail)

Each box represents one Node object. The left cell is val; the right cell is next — shown as *--- (a pointer arrow) when it points to another node, or null when there is no next node.

Head and Tail Pointers

A LinkedList object typically maintains two special references:

head — points to the first node. Without head, you cannot reach any node in the list.
tail — points to the last node. Without tail, appending to the end requires traversing the entire list every time.


  LinkedList
  +----------+      +------+------+    +------+------+    +------+------+
  | head *---+----->|  10  |  *---+--->|  20  |  *---+--->|  30  | null |
  | tail *---+------+------+------+    +------+------+    +------+------+
  | size = 3 |                                               ^
  +----------+                                               |
                                                         tail points here

When the list is empty, both head and tail are null and size is 0.

Note

Singly linked list implementations sometimes skip the `tail` pointer to keep the code simpler, accepting O(n) tail insertions. When append performance matters, always track `tail`.

Traversal

Because there is no index arithmetic, the only way to visit every node is to start at head and follow next pointers until you reach null.

function traverse(head) {
  let current = head       // start at the first node

  while (current !== null) {
    console.log(current.val)  // process the current node
    current = current.next    // move to the next node
  }
}
// Time: O(n) — visits every node once
// Space: O(1) — only one pointer variable

Tip

The traversal pattern — `let current = head; while (current !== null)` — appears in almost every linked list algorithm. Make it second nature.

Types of Linked Lists

There are three main variants, each adding a structural capability on top of the last:

1. Singly Linked List

Each node has one pointer: next. Traversal is one-directional — forward only. This is the simplest and most memory-efficient variant.

  [10] --> [20] --> [30] --> null

O(1) insert at head
O(n) insert at tail (without tail pointer)
Cannot traverse backwards
Memory per node: val + 1 pointer

2. Doubly Linked List

Each node has two pointers: next (forward) and prev (backward). You can traverse in both directions, and deletion of a known node becomes O(1) instead of O(n) because you no longer need to find the previous node.

  null <-- [10] <--> [20] <--> [30] --> null

O(1) insert and delete at both head and tail
Bidirectional traversal
Used to implement LRU caches, browser history, undo/redo stacks
Memory per node: val + 2 pointers

3. Circular Linked List

The tail node's next points back to the head instead of null. There is no natural end — traversal must check for the head pointer to avoid an infinite loop. Circular doubly linked lists (where tail points to head AND head points to tail) power many OS schedulers and round-robin algorithms.

  +------------------------------------+
  |                                    |
  v                                    |
 [10] --> [20] --> [30] --> [40] ------+

No null terminator — every node has a valid next
Useful for rotating structures: music playlists, CPU scheduling
Must track a "start" reference to know when a full cycle is complete

Complexity Summary

This table compares a singly linked list with a tail pointer against a dynamic array (like JavaScript arrays or Java ArrayList):

Operation	Array	Singly Linked List	Notes
Access by index	O(1)	O(n)	Arrays win — index arithmetic is instant
Search by value	O(n)	O(n)	Both must scan linearly
Insert at head	O(n)	O(1)	Linked list wins — update head pointer only
Insert at tail	O(1) amortized	O(1) with tail ptr / O(n) without	Dynamic array amortized append vs tail pointer
Insert at index i	O(n)	O(n)	Both: traverse to position first
Delete at head	O(n)	O(1)	Linked list wins — advance head pointer
Delete at tail	O(1) amortized	O(n) singly / O(1) doubly	Singly linked list must find second-to-last node
Delete by value	O(n)	O(n)	Both: scan then adjust
Space overhead	Low	Higher (pointer per node)	Each node allocates a pointer-sized reference

When to Use a Linked List

Linked lists are the right tool in specific situations. They are not a general-purpose replacement for arrays.

Reach for a linked list when:

You need constant-time insertions or deletions at the head (or head and tail in a doubly linked list)
The number of elements is highly unpredictable and you want to avoid array reallocation
You are implementing a stack or queue and raw performance matters more than index-based access
You are building LRU cache eviction, an undo stack, or a playlist data structure

Stick with an array when:

You need frequent random access (arr[i]) — arrays are O(1), linked lists are O(n)
Cache performance is critical — arrays have excellent spatial locality
You need to sort the data — sorting algorithms assume random access
The size is known up front and small — array overhead is lower

Warning

In JavaScript, arrays are already dynamic (backed by hidden resizable buffers). The performance benefit of a linked list over a JS array for head insertions is often theoretical — V8 optimises arrays heavily. Use linked lists when solving algorithm problems or when building explicit queue/deque structures where the semantics matter.

A Minimal Singly Linked List

Here is the skeleton you will expand in the next page:

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

class LinkedList {
  constructor() {
    this.head = null   // first node
    this.tail = null   // last node (saves O(n) appends)
    this.size = 0      // number of nodes
  }
}

// Create an empty list
const list = new LinkedList()
// list.head === null, list.tail === null, list.size === 0

Key Takeaways

A linked list is a chain of nodes connected by pointers — no contiguous memory required.
head is the entry point; tail enables O(1) appends; size avoids O(n) length calculations.
Singly linked lists are one-directional; doubly linked lists add a prev pointer for O(1) tail deletion.
Circular linked lists have no null terminator — perfect for round-robin and scheduling.
Prefer linked lists for O(1) head operations; prefer arrays for O(1) random access.
Every linked list algorithm uses the same traversal pattern: follow next until null.

Tip

The next page covers the **Singly Linked List** in full detail — inserting, deleting, searching, reversing, and more, all with step-by-step code.