Linked lists and trees

Linked lists and trees

Until now the structures relied on arrays. These two are based on nodes that link to each other through references.

Linked list

Each node holds a value and a reference to the next node. The list only needs to remember the head (head).

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

class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }
  add(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) current = current.next;
      current.next = newNode;
    }
    this.length++;
  }
  toArray() {
    const output = [];
    let current = this.head;
    while (current) {
      output.push(current.value);
      current = current.next;
    }
    return output;
  }
}

Advantage: inserting at the start is O(1). Downside: accessing by index is O(n) (you have to traverse from the head).

Tree (introduction)

A tree is a hierarchical structure: each node has a value and a list of children. The top node is the root.

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
  addChild(value) {
    const child = new TreeNode(value);
    this.children.push(child);
    return child;
  }
}

Trees model hierarchies: the DOM, file systems, org charts...

Examples

Traverse a tree depth-first

function traverse(node, level = 0) {
  console.log("  ".repeat(level) + node.value);
  for (const child of node.children || []) {
    traverse(child, level + 1);
  }
}
const root = { value: "root", children: [
  { value: "a", children: [] },
  { value: "b", children: [{ value: "b1", children: [] }] },
]};
traverse(root);