SinglyLinkedList

Positional linked list with elements linked in one direction from head to tail.

Generic types (only for TS):

T - Type of elements stored in the list.

new SinglyLinkedList()

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

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

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

length

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

Adding element increases list length:

const list = new SinglyLinkedList();

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 SinglyLinkedList();

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

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 SinglyLinkedList();

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 SinglyLinkedList();

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 SinglyLinkedList([1, 2, 3]);

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

Fast clearing:

const list = new SinglyLinkedList([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

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 SinglyLinkedList([1, 2]);

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

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 SinglyLinkedList([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 SinglyLinkedList([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 SinglyLinkedList();

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 SinglyLinkedList([1, 2, 3]);
const position = list.getFirst();

list.removeFirst() === 1; // true, list now is 2->3
list.getAfter(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 SinglyLinkedList([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 SinglyLinkedList([1, 2, 3]);

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