jsschools

Singly Linked List

A linear data structure where each node holds a value and a pointer to the next node.

Spec ↗

Syntax

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

Parameters

NameTypeRequiredDescription
head Node | null No The first node in the list. Defaults to null for an empty list.

Returns

LinkedList — A new singly linked list instance.

Examples

class Node {
  constructor(val) { this.val = val; this.next = null; }
}
class LinkedList {
  constructor() { this.head = null; this.size = 0; }
  push(val) {
    const node = new Node(val);
    if (!this.head) { this.head = node; }
    else {
      let cur = this.head;
      while (cur.next) cur = cur.next;
      cur.next = node;
    }
    this.size++;
  }
  toArray() {
    const out = [];
    let cur = this.head;
    while (cur) { out.push(cur.val); cur = cur.next; }
    return out;
  }
}
const list = new LinkedList();
list.push(1); list.push(2); list.push(3);
console.log(list.toArray());
Output 
[ 1, 2, 3 ]

// O(1) prepend
function prepend(list, val) {
  const node = new Node(val);
  node.next = list.head;
  list.head = node;
  list.size++;
}
Output 
(no output — mutates the list in place)

Notes

| Operation | Best | Avg | Worst | Space | |----------------|------|------|-------|-------| | Access by idx | O(n) | O(n) | O(n) | O(n) | | Search | O(1) | O(n) | O(n) | O(1) | | Insert (head) | O(1) | O(1) | O(1) | O(1) | | Insert (tail) | O(n) | O(n) | O(n) | O(1) | | Delete (head) | O(1) | O(1) | O(1) | O(1) | | Delete (mid) | O(n) | O(n) | O(n) | O(1) | Store a `tail` pointer to make tail insertions O(1). No random access — iterate from head each time.

See also