Algorithms and data structures for JS/TS
  • Introduction
  • GETTING STARTED
    • TS
    • Node.js
    • ES Modules
    • Browsers
  • PUBLIC API
    • How to read
    • Linked lists
      • SinglyLinkedList
      • DoublyLinkedList
      • CircularlyLinkedList
    • Stacks and queues
      • LinkedStack
      • LinkedQueue
      • LinkedDeque
      • CircularQueue
      • CircularArrayBuffer
      • UnsortedPriorityQueue
      • SortedPriorityQueue
      • AdaptableHeapPriorityQueue
    • Maps
      • SortedMap
      • MaximaSet
      • AVLTreeMap
      • SplayTreeMap
      • RedBlackTreeMap
    • Trees
      • GeneralTree
      • LinkedBinaryTree
      • PreorderTreeTraversal
      • InorderTreeTraversal
      • PostorderTreeTraversal
      • EulerTourTreeTraversal
    • Searches
      • Binary search
      • Quick select
    • Text processing
      • Longest common subsequence
      • Boyer-Moore
      • Knuth-Morris-Pratt
    • Position
    • Locator
    • Comparators
  • CONTRIBUTION NOTES
    • How to contribute
    • Project structure
  • Changelog
Powered by GitBook
On this page
  • new DoublyLinkedList()
  • length
  • addAfter()
  • addBefore()
  • addFirst()
  • addLast()
  • clear()
  • delete()
  • getAfter()
  • getBefore()
  • getFirst()
  • getLast()
  • isEmpty()
  • removeFirst()
  • removeLast()
  • replace()
  • [Symbol.iterator]()
  • See also

Was this helpful?

  1. PUBLIC API
  2. Linked lists

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

PreviousSinglyLinkedListNextCircularlyLinkedList

Last updated 5 years ago

Was this helpful?

Position