# Linked Lists (Singly)

> Nodes chained by pointers — O(1) insert/delete at head, O(n) everything else.

- **Category**: Data Structures
- **Subcategory**: linear
- **Canonical URL**: https://designpattern.fyi/data_structures/linked-lists/

---

## Description
Clean, reusable architecture pattern.


## Use Cases
Hash table separate chaining — each bucket is a linked list of entries with the same hash. O(1) prepend per collision. Undo stack in a text editor — each edit is a node, undo pops the head. LRU cache — doubly linked list + hash map gives O(1) eviction.



## Implementation Example

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

class SinglyLinkedList {
  #head = null;
  #tail = null;
  #size = 0;

  get length() { return this.#size; }

  // O(1) — Prepend to front (rewire head pointer)
  prepend(value) {
    const node = new Node(value);
    node.next = this.#head;
    this.#head = node;
    if (!this.#tail) this.#tail = node;
    this.#size++;
  }

  // O(1) — Append to end (requires tail pointer)
  append(value) {
    const node = new Node(value);
    if (!this.#tail) {
      this.#head = this.#tail = node;
    } else {
      this.#tail.next = node;
      this.#tail = node;
    }
    this.#size++;
  }

  // O(1) — Remove head node
  removeHead() {
    if (!this.#head) return null;
    const val = this.#head.value;
    this.#head = this.#head.next;
    if (!this.#head) this.#tail = null; // List is now empty
    this.#size--;
    return val;
  }

  // O(n) — Find by value (must walk from head)
  find(value) {
    let cur = this.#head;
    while (cur) {
      if (cur.value === value) return cur;
      cur = cur.next;
    }
    return null;
  }

  // O(n) — Delete by value
  delete(value) {
    if (!this.#head) return false;
    if (this.#head.value === value) { this.removeHead(); return true; }
    let cur = this.#head;
    while (cur.next) {
      if (cur.next.value === value) {
        if (cur.next === this.#tail) this.#tail = cur; // Update tail
        cur.next = cur.next.next;
        this.#size--;
        return true;
      }
      cur = cur.next;
    }
    return false;
  }

  // O(n) — Reverse in-place (classic interview question)
  reverse() {
    let prev = null, cur = this.#head;
    this.#tail = this.#head;
    while (cur) {
      const next = cur.next;
      cur.next = prev;
      prev = cur;
      cur = next;
    }
    this.#head = prev;
  }

  toArray() {
    const result = [];
    let cur = this.#head;
    while (cur) { result.push(cur.value); cur = cur.next; }
    return result;
  }
}

const list = new SinglyLinkedList();
list.append(10);
list.append(20);
list.append(30);
list.prepend(5);
list.reverse();

```



## Trade-offs


### Advantages

- O(1) prepend and head removal — no shifting, just pointer rewiring

- Truly dynamic — nodes allocated individually, no capacity planning

- Zero wasted capacity — each node allocated only when needed

- O(1) insert/delete at any position if you already hold the node pointer




### Considerations & Drawbacks

- O(n) access by index — must walk from head every time

- Terrible cache performance — nodes scattered across heap, no prefetch benefit

- Extra memory per node for the next pointer (8 bytes on 64-bit)

- No backwards traversal — singly-linked means forward-only







---
**Reference**: [Original Source](https://www.bigocheatsheet.com)