CircularlyLinkedList

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

Generic types (only for TS):

T - Type of elements stored in the list.

new CircularlyLinkedList()

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

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

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

length

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

Adding element increases list length:

const list = new CircularlyLinkedList();

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 CircularlyLinkedList([1]); // ->1-> is both last and current

list.addAfter(list.getLast(), 2); // list now is ->1->2->
list.addAfter(list.getLast(), 3); // list now is ->1->3->2->
list.addAfter(list.getLast(), 4); // list now is ->1->4->3->2->
list.addAfter(list.getCurrent(), 5); // list now is ->1->4->5->3->2->

Circular list structure implies that tail pointer stays the same whenever you add new elements after or before it. But as current is always the element after the last, this means that when you add a new element after the last element of the list, getCurrent() call will now return position of the newly added element. So addAfter() at the last element has literally the same effect as addCurrent(). This approach by default allows to fill circular list in a way of a stack. To fill list in the same order that the elements were supplied use the combination of addCurrent() and rotate() methods.

addCurrent()

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

Adding element as current:

const list = new CircularlyLinkedList();

list.addCurrent(1); // list now is ->1->
list.addCurrent(2); // list now is ->1->2->
list.addCurrent(3); // list now is ->1->3->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 CircularlyLinkedList([1, 2, 3]);

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

Fast clearing:

const list = new CircularlyLinkedList([1, 2, 3]);
const position = list.getCurrent(); // 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.
 */
getAfter(position: Position<T, Node<T>>): Position<T, Node<T>>

Getting position after the specified:

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

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

getCurrent()

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

Getting position of the current element:

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

list.getCurrent(); // Position of 1

getLast()

/**
 * Gets position of the current 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 first element:

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

list.getLast(); // Position of 3

getLast() and getCurrent() 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 O(1).
 *
 * @returns TRUE if the list is empty, FALSE otherwise.
 */
isEmpty(): boolean

Adding element makes list not empty:

const list = new CircularlyLinkedList();

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

removeCurrent()

/**
 * Removes current front 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.
 */
removeCurrent(): T

Removing element deprecates its position:

const list = new CircularlyLinkedList([1, 2, 3]);
const position = list.getCurrent();

list.removeCurrent() === 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 CircularlyLinkedList([1]);

list.replace(list.getCurrent(), 2); // list now is 2

rotate()

/**
 * Rotates current front element of the list to the back. Running time is O(1).
 */
rotate(): void

Rotating list to the element next to the current:

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

list.getCurrent(); // Position of 1
list.rotate(); // move 'last' pointer from 3 to 1
list.getCurrent(); // Position of 2
list.rotate(); // move 'last' pointer from 1 to 2
list.getCurrent(); // Position of 3
list.rotate(); // move 'last' pointer from 2 to 3
list.getCurrent(); // Position of 1

[Symbol.iterator]()

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

Building an array from list:

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

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

See also

Position