DoublyLinkedList

Positional linked list with elements linked in both directions from head to tail and vice versa.

Generic types (only for TS):

T - Type of elements stored in the list.

new DoublyLinkedList()

/**
 * Creates an instance of DoublyLinkedList.
 *
 * @param elements Array of elements to create the new linked list with.
 */
constructor(elements: T[] = [])

Creating a DoublyLinkedList with elements 1->2->3:

new DoublyLinkedList([1, 2, 3]);

length

/**
 * Number of elements in the list.
 *
 * @readonly
 */
get length(): number

Adding element increases list length:

const list = new DoublyLinkedList();

list.length === 0; // true
list.addFirst(1);
list.length === 1; // true

addAfter()

/**
 * Adds element after the specified position in the list. Throws an error if the position
 * does not belong to this list or its element has been removed from the list. Running time is O(1).
 *
 * @param position Position in the list.
 * @param element Element to add after the position.
 * @returns Position of the added element.
 */
addAfter(position: Position<T, Node<T>>, element: T): Position<T, Node<T>>

Adding element after the specified position:

const list = new DoublyLinkedList([1]);

list.addAfter(list.getFirst(), 2); // list now is 1<->2

addBefore()

/**
 * Adds element before the specified position in the list. Throws an error if the position
 * does not belong to this list or its element has been removed from the list. Running time is O(1).
 *
 * @param position Position in the list.
 * @param element Element to add before the position.
 * @returns Position of the added element.
 */
addBefore(position: Position<T, Node<T>>, element: T): Position<T, Node<T>>

Adding element before the specified position:

const list = new DoublyLinkedList([1]);

list.addBefore(list.getFirst(), 2); // list now is 2<->1

addFirst()

/**
 * Adds element at the front of the list. Running time is O(1).
 *
 * @param element Element to add.
 * @returns Position of the added element.
 */
addFirst(element: T): Position<T, Node<T>>

Adding element at the front of a list:

const list = new DoublyLinkedList();

list.addFirst(1); // list now is 1
list.addFirst(2); // list now is 2<->1

addLast()

/**
 * Adds element at the back of the list. Running time is O(1).
 *
 * @param element Element to add.
 * @returns Position of the added element.
 */
addLast(element: T): Position<T, Node<T>>

Adding element at the back of a list:

const list = new DoublyLinkedList();

list.addLast(1); // list now is 1
list.addLast(2); // list now is 1<->2

clear()

/**
 * Clears the list. If instant set TRUE it takes O(1) time but does not deprecate existing positions.
 *
 * @param instant TRUE to deprecate all existing positions, FALSE to skip deprecation (client code cares of it).
 */
clear(instant?: boolean): void;

Deep clearing:

const list = new DoublyLinkedList([1, 2, 3]);

list.length === 3; // true
list.clear(); // O(n)
list.length === 0; // true

Fast clearing:

const list = new DoublyLinkedList([1, 2, 3]);
const position = list.getFirst(); // Position of 1

list.clear(true); // O(1)
list.length === 0; // true
list.addAfter(position, 4); // list now is 4, error not thrown

delete()

/**
 * Deletes element at the specified position. Deprecates all positions pointing to that element.
 * Throws an error if the position does not belong to this list or its element has been removed.
 * Running time is O(1).
 *
 * @param position Position in the list.
 * @returns Deleted element.
 */
delete(position: Position<T, Node<T>>): T

Deleting element at the specified position:

const list = new DoublyLinkedList([1, 2, 3]);
const position = list.getFirst();

list.delete(position) === 1; // true, list now is 2<->3
list.getAfter(position); // throws 'ADSError: Position is deprecated'

getAfter()

/**
 * Gets position after the specified position in the list. Throws an error if the position
 * does not belong to this list or its element has been removed. Running time is O(1).
 *
 * @param position Position in the list.
 * @returns Position of the element next to the specified or undefined if the specified position is the last.
 */
getAfter(position: Position<T, Node<T>>): Position<T, Node<T>> | undefined

Getting position after the specified:

const list = new DoublyLinkedList([1, 2]);

list.getAfter(list.getFirst()); // Position of 2

getBefore()

/**
 * Gets position before the specified position in the list. Throws an error if the position
 * does not belong to this list or its element has been removed. Running time is O(1).
 *
 * @param position Position in the list.
 * @returns Position or undefined if the specified position is the first.
 */
getBefore(position: Position<T, Node<T>>): Position<T, Node<T>> | undefined

Getting position before the specified:

const list = new DoublyLinkedList([1, 2]);

list.getBefore(list.getLast()); // Position of 1

getFirst()

/**
 * Gets position of the first element in the list. Running time is O(1).
 *
 * @returns Position of the element or undefined if the list is empty.
 */
getFirst(): Position<T, Node<T>> | undefined

Getting position of the first element:

const list = new DoublyLinkedList([1, 2, 3]);

list.getFirst(); // Position of 1

getLast()

/**
 * Gets position of the last element in the list. Running time is O(1).
 *
 * @returns Position of the element or undefined if the list is empty.
 */
getLast(): Position<T, Node<T>> | undefined

Getting position of the last element:

const list = new DoublyLinkedList([1, 2, 3]);

list.getLast(); // Position of 3

getLast() and getFirst() return positions of the same element if list has only one element. These positions won't be the same object however.

isEmpty()

/**
 * Checks whether the list is empty or not. Running time is O(1).
 *
 * @returns TRUE if the list is empty, FALSE otherwise.
 */
isEmpty(): boolean

Adding element makes list not empty:

const list = new DoublyLinkedList();

list.isEmpty(); // true
list.addFirst(1);
list.isEmpty(); // false

removeFirst()

/**
 * Removes the first element from the list and returns it. Deprecates all positions pointing to that element.
 * Throws an error if the list is empty. Running time is O(1).
 *
 * @throws {ADSError} List is empty.
 * @returns Removed element.
 */
removeFirst(): T

Removing element deprecates its position:

const list = new DoublyLinkedList([1, 2, 3]);
const position = list.getFirst();

list.removeFirst() === 1; // true, list now is 2<->3
list.getAfter(position); // throws 'ADSError: Position is deprecated'

removeLast()

/**
 * Removes the last element from the list and returns it. Deprecates all positions pointing to that element.
 * Throws an error if the list is empty. Running time is O(1).
 *
 * @throws {ADSError} List is empty.
 * @returns Removed element.
 */
removeLast(): T

Removing element deprecates its position:

const list = new DoublyLinkedList([1, 2, 3]);
const position = list.getLast();

list.removeLast() === 1; // true, list now is 1<->2
list.getBefore(position); // throws 'ADSError: Position is deprecated'

replace()

/**
 * Replaces element at the specified position. Throws an error if the position
 * does not belong to this list or its element has been removed. Running time is O(1).
 *
 * @param position Position in the list.
 * @param element Element to replace the existing with.
 * @returns Replaced element.
 */
replace(position: Position<T, Node<T>>, element: T): T

Replacing element takes effect for all positions pointing to it:

const list = new DoublyLinkedList([1]);
const position = list.getFirst();

list.replace(list.getFirst(), 2);
position.element;// element now is 2

[Symbol.iterator]()

[Symbol.iterator](): IterableIterator<T>

Building an array from list:

const list = new DoublyLinkedList([1, 2, 3]);

Array.from(list); // [1, 2, 3]

See also

Position