Engineering Fluency OS

Why This Matters

Arrays store elements in contiguous memory, which makes accessing by index fast but inserting or deleting in the middle slow. A linked list takes a different approach: each element is a node that holds a value and a pointer to the next node. This means insertions and deletions at the head happen in constant time, no shifting required.

Linked lists are the foundation of many other data structures like stacks, queues, and hash table chains. Understanding how nodes and pointers work teaches you how computers actually connect pieces of data in memory.

Define Terms

Visual Model

head

10next →

20next →

30next →

null

The full process at a glance. Click Start tour to walk through each step.

A linked list chains nodes together with pointers. Insertion and deletion at the head are O(1).

Code Example

Code

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

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  // Add to front - O(1)
  prepend(value) {
    const node = new Node(value);
    node.next = this.head;
    this.head = node;
    this.size++;
  }

  // Add to end - O(n)
  append(value) {
    const node = new Node(value);
    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.size++;
  }

  // Find a value - O(n)
  find(value) {
    let current = this.head;
    while (current) {
      if (current.value === value) return current;
      current = current.next;
    }
    return null;
  }

  // Delete first occurrence - O(n)
  delete(value) {
    if (!this.head) return false;
    if (this.head.value === value) {
      this.head = this.head.next;
      this.size--;
      return true;
    }
    let current = this.head;
    while (current.next) {
      if (current.next.value === value) {
        current.next = current.next.next;
        this.size--;
        return true;
      }
      current = current.next;
    }
    return false;
  }

  // Print all values
  print() {
    const values = [];
    let current = this.head;
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    console.log(values.join(" -> "));
  }
}

const list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.prepend(5);
list.print();       // 5 -> 10 -> 20 -> 30
list.delete(20);
list.print();       // 5 -> 10 -> 30
console.log(list.find(10)?.value); // 10

Interactive Experiment

Try these exercises:

Create a linked list and add 5 elements. Print it to verify the order.
Prepend an element, then append one. Which operation feels conceptually simpler?
Delete the head, then delete a middle element. Trace through the pointer updates.
Try to access the 3rd element directly. Why can't you use an index like list[2]?
What happens if you try to delete a value that doesn't exist in the list?

Quick Quiz

Coding Challenge

Reverse a Linked List

Write a function called `reverseList` that takes the head node of a singly linked list and returns the head of the reversed list. Each node has a `value` property and a `next` property. For example, 1 -> 2 -> 3 becomes 3 -> 2 -> 1.

Loading editor...

Real-World Usage

Linked lists appear in many real-world systems:

Browser history: Back/forward navigation uses a doubly linked list of visited pages.
Undo/redo: Each action is a node; undo moves backward, redo moves forward.
Memory allocators: Free memory blocks are tracked in linked lists.
Hash table chaining: Collisions are resolved by storing multiple values in a linked list at each bucket.
Music playlists: Songs in a playlist with next/previous navigation form a doubly linked list.

Linked Lists