Doubly Linked List

Data Structures

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

head

tail

3 nodes linked both ways, from head 14 to tail 7

1 / 42

Code

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

structure Node  prev ← null  next ← null  valueend structurestructure DoublyLinkedList  head ← null  tail ← null  length ← 0  procedure insert(value, index)    node ← new Node(value)    if the list is empty then      head ← tail ← node    else if index = 0 then      node.next ← head      head.prev ← node      head ← node    else if index ≥ length then    ▷ O(1) append via tail      node.prev ← tail      tail.next ← node      tail ← node    else      cur ← head      advance cur index times      node.prev ← cur.prev      node.next ← cur      cur.prev.next ← node      cur.prev ← node    end if    length ← length + 1  end procedure  procedure delete(value)    cur ← head    while cur ≠ null and cur.value ≠ value do cur ← cur.next    if cur = null then return false    if cur.prev ≠ null then cur.prev.next ← cur.next    else head ← cur.next    if cur.next ≠ null then cur.next.prev ← cur.prev    else tail ← cur.prev    length ← length − 1    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=3

Counters

hops: 0
relinks: 0

Starting contents3 values

Operations6 / 40

1. insert(52)
2. insert(21 @ 2)
3. insert(3 @ 0)
4. delete(36)
5. search(52)
6. delete(52)

How it works

Every node links both to its successor and its predecessor, and the list keeps a tail pointer. That makes appends and removals of a known node O(1), at the cost of one extra pointer per node and twice the rewiring on every edit.

Complexity

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

Doubly Linked List

How it works

Complexity

Search algorithms