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]
