Linked Lists: Singly & Doubly Linked Chains

Pointers, head, tail, insertion/deletion O(1) vs sequential traversal O(n)

« Static vs Dynamic Arrays & Memory Layout« Previous Stacks (LIFO) & Queues (FIFO) »Next »

Linked Lists store elements in separate node objects scattered across memory, connected linearly through pointer references (next and prev).

Linked Lists vs Arrays

Insert / Delete at Head: O(1) for Linked List (just update pointers); O(n) for Arrays (requires shifting all subsequent elements).

Random Access by Index: O(n) for Linked List (must traverse sequentially from head); O(1) for Arrays.

Doubly Linked List: Each node contains both .next and .prev pointers, enabling bidirectional traversal and O(1) removal if the node pointer is known.

Singly Linked List Node in JavaScript

Try It Yourself »

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

// Build chain: 1 -> 2 -> 3
const head = new ListNode(1, new ListNode(2, new ListNode(3)));

// Insert 0 at head in O(1) time
const newHead = new ListNode(0, head);

// Sequential traversal O(n)
let current = newHead;
while (current !== null) {
  console.log(current.val);
  current = current.next;
}

Inserting at head requires zero element shifting.

Google AdSense Slot (inContentBanner)

Set your Publisher ID in src/config/ads.ts to display live ads.

Test Yourself With Exercise

+15 XP

What is the time complexity of inserting a new node at the head of a Singly Linked List?

« Previous: Static vs Dynamic Arrays & Memory Layout Next: Stacks (LIFO) & Queues (FIFO) »