doubly-linked-list.md

Doubly linked list

In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the sequence of nodes) and one data field.

Usage

JS Example

import { createDoublyLinkedList } from "algo-ds";

const doublyLinkedList = createDoublyLinkedList();
doublyLinkedList.addFront("Yarik");
doublyLinkedList.addFront(10);

TS Example

import { createDoublyLinkedList } from "algo-ds";

type NodeValueType = number | string;

const doublyLinkedList = createDoublyLinkedList<NodeValueType>();
doublyLinkedList.addFront("Yarik");
doublyLinkedList.addFront(10);
doublyLinkedList.addFront(true); // Type error

API

interface Node<NodeValueType> {
  value: NodeValueType;
  next: Node | null;
  prev: Node | null;
}

interface IDoublyLinkedList<NodeValueType> {
  head: Node<NodeValueType> | null;
  tail: Node<NodeValueType> | null;
  size: number;

  addFront: (value: NodeValueType) => void;
  addEnd: (value: NodeValueType) => void;
  removeFront: () => void;
  removeEnd: () => void;
  remove: (value: NodeValueType) => boolean;
  clear: () => void;
  contains: (value: NodeValueType) => boolean;
  forEach: (fn: ForEachFunction<NodeValueType>) => void;
  copyToArray: () => NodeValueType[];
  isEmpty: () => boolean;
  addBefore: (valueBefore: NodeValueType, value: NodeValueType) => boolean;
  addAfter: (valueAfter: NodeValueType, value: NodeValueType) => boolean;
  getNodeByValue: (value: NodeValueType) => Node<NodeValueType> | null;
}

---

• head: Node<NodeValueType> | null - A link to the first node

Time: O(1)

doublyLinkedList.addFront(1);
doublyLinkedList.addFront(2);
doublyLinkedList.addFront(3);

doublyLinkedList.head; //-> { value: 3, prev: null, next: Node }

---

• tail: Node<NodeValueType> | null - A link to the last node

Time: O(1)

doublyLinkedList.addFront(1);
doublyLinkedList.addFront(2);
doublyLinkedList.addFront(3);

doublyLinkedList.tail; //-> { value: 1, prev: Node, next: null }

---

• size: number - Number of nodes in the list

Time: O(1)

doublyLinkedList.addFront(1);
doublyLinkedList.addFront(2);
doublyLinkedList.addFront(3);

doublyLinkedList.size; //-> 3

---

• addFront(value: NodeValueType): void - Inserting an element at the front of the list.

Time: O(1)

Space: O(1)

doublyLinkedList.addFront({ name: "Yarik" });
doublyLinkedList.addFront({ name: "Mike" });
doublyLinkedList.addFront({ name: "Alice" });

doublyLinkedList.head; //-> { value: "Alice", prev: null, next: Node }

---

• addEnd(value: NodeValueType): void - Inserting an element at the end of the list.

Time: O(1)

Space: O(1)

doublyLinkedList.addEnd({ age: 12 });
doublyLinkedList.addEnd({ age: 23 });
doublyLinkedList.addEnd({ age: 45 });

doublyLinkedList.tail; //-> { value: { age: 45 }, prev: Node, next: null }

---

• removeFront(): void - Remove the first node

Time: O(1)

doublyLinkedList.addFront("a");
doublyLinkedList.addFront("b");
doublyLinkedList.addFront("c");
doublyLinkedList.addFront("d");

doublyLinkedList.removeFront(); // Removed the first node with value "d"
doublyLinkedList.head.value; //-> "c"

---

• removeEnd(): void - Remove the last node

Time: O(1)

doublyLinkedList.addFront("a");
doublyLinkedList.addFront("b");
doublyLinkedList.addFront("c");
doublyLinkedList.addFront("d");

doublyLinkedList.removeEnd(); // // Removed the last node with value "a"
doublyLinkedList.tail.value; //-> "b"

---

• remove(value: NodeValueType): boolean - Removing given value from the list

Time: O(n) | n - number of nodes in the list

Space: O(1)

doublyLinkedList.addFront("a");
doublyLinkedList.addFront("b");
doublyLinkedList.addFront("c");
doublyLinkedList.addFront("d");

doublyLinkedList.remove("a"); //-> Returns `true` because it found a node with this value
doublyLinkedList.remove("f"); //-> Returns `false` because it can't find a node with this value
doublyLinkedList.forEach(v => console.log(v)); // "d" "c" "b"

---

• clear(): void - Remove all nodes

Time: O(1)

doublyLinkedList.addFront("a");
doublyLinkedList.addFront("b");
doublyLinkedList.addFront("c");
doublyLinkedList.addFront("d");

doublyLinkedList.size; //-> 4
doublyLinkedList.head.value; //-> "d"
doublyLinkedList.tail.value; //-> "a"

doublyLinkedList.clear();

doublyLinkedList.size; //-> 0
doublyLinkedList.head; //-> null
doublyLinkedList.tail; //-> null

---

• contains(value: NodeValueType): boolean - The method checks to see if a value is in the list

Time: O(n) | n - number of nodes

doublyLinkedList.addFront("a");
doublyLinkedList.addFront("b");
doublyLinkedList.addFront("c");

doublyLinkedList.contains("a"); //-> true
doublyLinkedList.contains("h"); //-> false

---

• forEach(fn: (value: NodeValueType, index: number) => void): void - The method executes a provided function once for each node's value.

Time: O(n) | n - number of nodes

doublyLinkedList.addFront("a");
doublyLinkedList.addFront("b");
doublyLinkedList.addFront("c");
doublyLinkedList.forEach((char, i) => console.log(`${i}:${char}`)); // "0:c" "1:b" "2:a"

---

• copyToArray(): NodeValueType[] - Create an array from the linked list

Time: O(n) | n - number of nodes

Space: O(n) | n - number of nodes

doublyLinkedList.addFront(1);
doublyLinkedList.addFront(2);
doublyLinkedList.addFront(3);

const arr = doublyLinkedList.copyToArray(); // [3, 2, 1]
const newArr = arr.map(n => n + 1); // [4, 3, 2]

doublyLinkedList.clear();
newArr.forEach(doublyLinkedList.addFront);

doublyLinkedList.head.value; //-> 2
doublyLinkedList.tail.value; //-> 4

---

• isEmpty(): boolean - Checking whether the list is empty

Time: O(1)

doublyLinkedList.isEmpty(); // true
doublyLinkedList.addFront(1);
doublyLinkedList.isEmpty(); // false

---

• getNodeByValue(value: NodeValueType): Node<NodeValueType> | null - Returns a node of value

Time: O(n) | n - number of nodes

const person = { name: "Yarik" };
doublyLinkedList.getNodeByValue(person); // null
doublyLinkedList.addFront(person);
doublyLinkedList.getNodeByValue(person); // { value: { name: "Yarik" }, prev: null, next: null }

---

• addBefore(valueBefore: NodeValueType, value: NodeValueType): boolean - Inserting before given value

Time: O(n) | n - number of nodes

doublyLinkedList.addBefore(1, 2); // false
doublyLinkedList.addFront(1);
doublyLinkedList.addBefore(1, 2); // true
doublyLinkedList.copyToArray(); // [2, 1]

---

• addAfter(valueAfter: NodeValueType, value: NodeValueType): boolean - Inserting after given value

Time: O(n) | n - number of nodes

doublyLinkedList.addAfter(1, 2); // false
doublyLinkedList.addFront(1);
doublyLinkedList.addAfter(1, 2); // true
doublyLinkedList.copyToArray(); // [1, 2]

---