Singly Linked List

Data Structures

avgO(n)worstO(n)spaceO(n)

head

A list of 4 nodes; head points at 12

1 / 45

Code

class Node {  constructor(public value: number, public next: Node | null = null) {}}class LinkedList {  head: Node | null = null;  insert(value: number, index: number) {    const node = new Node(value);    if (index === 0 || !this.head) {      node.next = this.head;      this.head = node;      return;    }    let cur = this.head;    for (let i = 0; i < index - 1 && cur.next; i++) cur = cur.next;    node.next = cur.next;    cur.next = node;  }  delete(value: number) {    let prev: Node | null = null;    let cur = this.head;    while (cur && cur.value !== value) {      prev = cur;      cur = cur.next;    }    if (!cur) return false;    if (prev) prev.next = cur.next;    else this.head = cur.next;    return true;  }  search(value: number) {    let cur = this.head;    while (cur) {      if (cur.value === value) return cur;      cur = cur.next;    }    return null;  }}

structure Node(value, next)end structurestructure LinkedList  head ← null  procedure insert(value, index)    node ← new Node(value)    if index = 0 or head = null then      node.next ← head      head ← node      return    end if    cur ← head    advance cur index − 1 times (or to the tail)    node.next ← cur.next    cur.next ← node  end procedure  procedure delete(value)    prev ← null    cur ← head    while cur ≠ null and cur.value ≠ value do      prev ← cur      cur ← cur.next    end while    if cur = null then return false    if prev ≠ null then prev.next ← cur.next    else head ← cur.next    return true  end procedure  procedure search(value)    cur ← head    while cur ≠ null do      if cur.value = value then return cur      cur ← cur.next    end while    return null  end procedureend structure

Variables

length=4

Counters

hops: 0
relinks: 0

Starting contents4 values

Operations6 / 40

1. insert(33 @ 2)
2. insert(5 @ 0)
3. search(41)
4. delete(27)
5. insert(19)
6. delete(99)

How it works

Each node stores a value and a pointer to the next node, so inserting or deleting rewires a pointer or two instead of shifting elements. The price is access: reaching position i means walking i links from the head.

Complexity

Best: O(1)
Average: O(n)
Worst: O(n)
Space: O(n)

Singly Linked List

How it works

Complexity

Search algorithms