Skip to content

README.md

Latest commit

 

History

History
107 lines (78 loc) · 3.06 KB

README.md

File metadata and controls

107 lines (78 loc) · 3.06 KB
Raw

List

Linked lists step by step: cons cells, car/cdr, immutable classes, then mutable singly, doubly, and circular lists.

Examples

  • 1-cons.js — frozen cons(value, next) cells; several heads share one tail
  • 2-access.js — first / rest (car / cdr) and walk a list with iterate
  • 3-list.js — list(...values) builds a chain; iterate over it
  • 4-class.js — ConsList with private fields, prepend, first, rest, and iterator
  • 5-mutable.js — mutable singly linked List (prepend, append, insert, delete, at)
  • 6-double.js — mutable DoubleList with the same API; O(1) append via tail
  • 7-circular.js — mutable CircularList with the same API; last next points to head

Cons cells (1–3)

A list is either null (empty) or an immutable cell { value, next }:

const cons = (value, next = null) => Object.freeze({ value, next });

const first = (list) => list.value; // car / head
const rest = (list) => list.next; // cdr / tail

Branches can share the same tail without copying:

  branch1   branch2   branch3
     │         │         │
     ▼         ▼         ▼
    [10]      [20]      [30]
     │         │         │
     └────┬────┴─────────┘
          ▼
         [3] → [2] → [1] → null

Immutable prepend is O(1): allocate one new cell that points at the old head.

Immutable class (4)

ConsList keeps #value, #next, and #size private. prepend returns a new list; older versions stay unchanged.

const three = empty.prepend(1).prepend(2).prepend(3);
const branch1 = three.prepend(10); // [10, 3, 2, 1]

Mutable lists (5–7)

Same idea of a growing chain, but one instance is updated in place. Examples 5–7 share an API:

prepend, append, insert, delete, at, toArray, [Symbol.iterator]

const list = new List();
list.prepend(1);
list.prepend(2);
list.prepend(3); // [3, 2, 1]
list.append(0); // [3, 2, 1, 0]
List (5) DoubleList (6) CircularList (7)
Links next prev + next next (ring)
End null tail pointer last next → head
append O(n) walk O(1) via tail O(n) to last
Index walk from head nearer of head/tail from head
Extra — fast unlink with prev toArray(start) wraps

Singly linked (5):

head → [3] → [2] → [1] → null

Doubly linked (6):

head ⇄ [3] ⇄ [2] ⇄ [1] ⇄ tail

Circular (7):

      ┌──────────────┐
      ▼              │
head → [3] → [2] → [1] ┘

Complexity

Immutable cons list:

prepend: O(1)
first:   O(1)
rest:    O(1)
iterate: O(n)

Mutable lists: prepend is O(1); at / insert / delete are O(n); DoubleList.append is O(1).

Prefer arrays when you need frequent indexed access, slice, or sort.