Function

Static Public Summary
public	Node(value: any, prev: Node \| null, next: Node \| null) Base node class.
public	concat(x: Node, z: Node, y: Node): Node Concatenate two input lists.
public	empty(): Node Return an empty list.
public	from(iterable: Iterable): Node Creates a list from an input iterable.
public	* iter(first: Node): IterableIterator<Node> Generator of nodes in list in order.
public	last(first: Node): Node Returns the last node of a list.
public	len(x: Node): number Compute the length of a list (can be empty).
public	pop(x: Node): [Node, Node] Removes last Node from a list.
public	push(x: Node, z: Node, value: any): Node Push value to list.
public	rotate_left(x: Node, z: Node, n: number): [Node, Node] Do nothing if x is empty or n is zero.
public	rotate_right(x: Node, z: Node, n: number): [Node, Node] Do nothing if x is empty or n is zero.
public	shift(x: Node): [Node, Node] Removes first Node from a list.
public	split(x: Node, z: Node): undefined[] Split a list at a Node.
public	unshift(x: Node, value: any): Node Unshift value to list.
public	* values(first: Node): IterableIterator<any> Generator of nodes in list in order.

Static Private Summary
private	_concat(z: Node, y: Node) Concatenate two input lists.
private	_erase(x: Node, y: Node) Erase range [x, y) from list.
private	_extend(z: Node, iterable: Iterable): Node Extend a list with an iterable.
private	_insertAfter(x: Node, value: any): * _insertAfter.
private	_insertBefore(x: Node, value: any): * _insertBefore.
private	_insertBetween(x: Node, y: Node, value: any): * _insertBetween.
private	* _iter(first: Node): IterableIterator<Node> Generator of nodes in list in order.
private	* _iter_fast(first: Node): IterableIterator<Node> Generator of nodes in list in order.
private	_last(first: Node): Node Returns the last node of a list.
private	_len(x: Node): number Compute the length of a non-empty list.
private	_pop(x: Node): Node Removes last Node from a non-empty list.
private	_push(z: Node, value: any): Node Push value to list.
private	_remove(x: Node) Removes input Node from its list.
private	_rotate_left(x: Node, z: Node, k: number): [Node, Node] Rotate list to the left k steps.
private	_rotate_left_modulo(x: Node, z: Node, n: number, k: number): [Node, Node] Rotate non-empty list to the left n steps.
private	_rotate_left_unknown_length(x: Node, z: Node, k: number): [Node, Node] Rotate list to the right n steps.
private	_rotate_right(x: Node, z: Node, k: number): [Node, Node] Rotate list to the right k steps.
private	_rotate_right_modulo(x: Node, z: Node, n: number, k: number): [Node, Node] Rotate non-empty list to the right n steps.
private	_rotate_right_unknown_length(x: Node, z: Node, k: number): [Node, Node] Rotate list to the right n steps.
private	_rotate_to(x: , y: , z: *)
private	_shift(x: Node): Node Removes first Node from a non-empty list.
private	_split(x: Node) Split a list at Node x.
private	_unshift(x: Node, value: any): Node Unshift value to list.

Static Public

public Node(value: any, prev: Node | null, next: Node | null) source

import Node from '@data-structure-algebra/doubly-linked-list/src/Node.js'

Base node class.

Params:

Name	Type	Attribute	Description
value	any		The value to hold.
prev	Node \| null		The value to hold.
next	Node \| null		The value to hold.

public concat(x: Node, z: Node, y: Node): Node source

import concat from '@data-structure-algebra/doubly-linked-list/src/concat.js'

Concatenate two input lists.

Params:

Name	Type	Attribute	Description
x	Node		First node of first input list (can be null).
z	Node		Last node of first input list (can be null).
y	Node		First node of second input list (can be null).

Return:

Node	First node of the output list (or null if empty).

public empty(): Node source

import empty from '@data-structure-algebra/doubly-linked-list/src/empty.js'

Return an empty list.

Return:

Node	The empty list.

public from(iterable: Iterable): Node source

import from from '@data-structure-algebra/doubly-linked-list/src/from.js'

Creates a list from an input iterable.

Params:

Name	Type	Attribute	Description
iterable	Iterable		The input iterable.

Return:

Node	First node of the newly created list (or null if empty list).

public * iter(first: Node): IterableIterator<Node> source

import iter from '@data-structure-algebra/doubly-linked-list/src/iter.js'

Generator of nodes in list in order.

Params:

Name	Type	Attribute	Description
first	Node		First node of the list (can be null).

Return:

IterableIterator<Node>

public last(first: Node): Node source

import last from '@data-structure-algebra/doubly-linked-list/src/last.js'

Returns the last node of a list.

Params:

Name	Type	Attribute	Description
first	Node		First node of the list.

Return:

Node	Last node of the list.

public len(x: Node): number source

import len from '@data-structure-algebra/doubly-linked-list/src/len.js'

Compute the length of a list (can be empty).

Params:

Name	Type	Attribute	Description
x	Node		First node of the input list (can be null).

Return:

number

The length of the input list.

public pop(x: Node): [Node, Node] source

import pop from '@data-structure-algebra/doubly-linked-list/src/pop.js'

Removes last Node from a list. Throws if input list is empty.

Params:

Name	Type	Attribute	Description
x	Node		Last node.

Return:

[Node, Node]

Last node of new list (possibly null) and removed node.

public push(x: Node, z: Node, value: any): Node source

import push from '@data-structure-algebra/doubly-linked-list/src/push.js'

Push value to list.

Params:

Name	Type	Attribute	Description
x	Node		First node of first input list (can be null).
z	Node		Last node of first input list (can be null).
value	any		Value to push.

Return:

Node	The node at the front of the list (new node if empty, input node otherwise).

public rotate_left(x: Node, z: Node, n: number): [Node, Node] source

import rotate_left from '@data-structure-algebra/doubly-linked-list/src/rotate_left.js'

Do nothing if x is empty or n is zero. Rotate left n steps if n is positive. Rotate right n steps if n is negative.

Params:

Name	Type	Attribute	Description
x	Node		The current first node.
z	Node		The current last node.
n	number

Return:

[Node, Node]

The new first and last node.

public rotate_right(x: Node, z: Node, n: number): [Node, Node] source

import rotate_right from '@data-structure-algebra/doubly-linked-list/src/rotate_right.js'

Do nothing if x is empty or n is zero. Rotate right n steps if n is positive. Rotate left n steps if n is negative.

Params:

Name	Type	Attribute	Description
x	Node		The current first node.
z	Node		The current last node.
n	number

Return:

[Node, Node]

The new first and last node.

public shift(x: Node): [Node, Node] source

import shift from '@data-structure-algebra/doubly-linked-list/src/shift.js'

Removes first Node from a list. Throws if input list is empty.

Params:

Name	Type	Attribute	Description
x	Node		First node .

Return:

[Node, Node]

New list (possibly null) and removed node.

public split(x: Node, z: Node): undefined[] source

import split from '@data-structure-algebra/doubly-linked-list/src/split.js'

Split a list at a Node.

Params:

Name	Type	Attribute	Description
x	Node		First node of the list.
z	Node		Node to split at.

Return:

undefined[]

public unshift(x: Node, value: any): Node source

import unshift from '@data-structure-algebra/doubly-linked-list/src/unshift.js'

Unshift value to list.

Params:

Name	Type	Attribute	Description
x	Node		First node of first input list (can be null).
value	any		Value to unshift.

Return:

Node	The node at the front of the list (hence, the new node).

public * values(first: Node): IterableIterator<any> source

import values from '@data-structure-algebra/doubly-linked-list/src/values.js'

Generator of nodes in list in order.

Params:

Name	Type	Attribute	Description
first	Node		First node of the list (can be null).

Return:

IterableIterator<any>

Static Private

private _concat(z: Node, y: Node) source

import _concat from '@data-structure-algebra/doubly-linked-list/src/_concat.js'

Concatenate two input lists.

Params:

Name	Type	Attribute	Description
z	Node		Last node of first input list.
y	Node		First node of second input list.

private _erase(x: Node, y: Node) source

import _erase from '@data-structure-algebra/doubly-linked-list/src/_erase.js'

Erase range [x, y) from list. Range cannot be empty.

Params:

Name	Type	Attribute	Description
x	Node		Inclusive beginning of range to erase.
y	Node		Exclusive end of range to erase.

private _extend(z: Node, iterable: Iterable): Node source

import _extend from '@data-structure-algebra/doubly-linked-list/src/_extend.js'

Extend a list with an iterable.

Params:

Name	Type	Attribute	Description
z	Node		The last node of the list to extend.
iterable	Iterable		The input iterable.

Return:

Node	Last node of the extended list.

private _insertAfter(x: Node, value: any): * source

import _insertAfter from '@data-structure-algebra/doubly-linked-list/src/_insertAfter.js'

_insertAfter.

Params:

Name	Type	Attribute	Description
x	Node
value	any

Return:

private _insertBefore(x: Node, value: any): * source

import _insertBefore from '@data-structure-algebra/doubly-linked-list/src/_insertBefore.js'

_insertBefore.

Params:

Name	Type	Attribute	Description
x	Node
value	any

Return:

private _insertBetween(x: Node, y: Node, value: any): * source

import _insertBetween from '@data-structure-algebra/doubly-linked-list/src/_insertBetween.js'

_insertBetween.

Params:

Name	Type	Attribute	Description
x	Node
y	Node
value	any

Return:

private * _iter(first: Node): IterableIterator<Node> source

import _iter from '@data-structure-algebra/doubly-linked-list/src/_iter.js'

Generator of nodes in list in order. You are allowed to edit the current node.

/!\ Modifying the next pointer of the current node will NOT change which node comes next in the iteration.

Params:

Name	Type	Attribute	Description
first	Node		First node of the list.

Return:

IterableIterator<Node>

Yields nodes of a list in order.

private * _iter_fast(first: Node): IterableIterator<Node> source

import _iter_fast from '@data-structure-algebra/doubly-linked-list/src/_iter_fast.js'

Generator of nodes in list in order. The list cannot be empty. You should not modify the current node's next pointer unless you know what you are doing.

/!\ Modifying the next pointer of the current node will change which node comes next in the iteration.

Params:

Name	Type	Attribute	Description
first	Node		First node of the list.

Return:

IterableIterator<Node>

Yields nodes of a list in order.

private _last(first: Node): Node source

import _last from '@data-structure-algebra/doubly-linked-list/src/_last.js'

Returns the last node of a list. The list cannot be empty.

Params:

Name	Type	Attribute	Description
first	Node		First node of the list.

Return:

Node	Last node of the list.

private _len(x: Node): number source

import _len from '@data-structure-algebra/doubly-linked-list/src/_len.js'

Compute the length of a non-empty list.

Params:

Name	Type	Attribute	Description
x	Node		First node of the input list.

Return:

number

The length of the input list.

private _pop(x: Node): Node source

import _pop from '@data-structure-algebra/doubly-linked-list/src/_pop.js'

Removes last Node from a non-empty list.

Params:

Name	Type	Attribute	Description
x	Node		Last node (not null). Cannot be the first node.

Return:

Node	Last node of new list (not null).

private _push(z: Node, value: any): Node source

import _push from '@data-structure-algebra/doubly-linked-list/src/_push.js'

Push value to list.

Params:

Name	Type	Attribute	Description
z	Node		Last node of first input list (can be null).
value	any		Value to push.

Return:

Node	The node at the front of the list (new node if empty, input node otherwise).

private _remove(x: Node) source

import _remove from '@data-structure-algebra/doubly-linked-list/src/_remove.js'

Removes input Node from its list. Cannot be first or last, use _shift or _pop instead.

/!\ Pointers in the extracted node are left unchanged. /!\ x will have dangling pointers after removal if not single element.

Params:

Name	Type	Attribute	Description
x	Node		Node to remove.

private _rotate_left(x: Node, z: Node, k: number): [Node, Node] source

import _rotate_left from '@data-structure-algebra/doubly-linked-list/src/_rotate_left.js'

Rotate list to the left k steps. The parameter k must be positive and smaller than the length of the list.

Params:

Name	Type	Attribute	Description
x	Node		The current first node.
z	Node		The current last node.
k	number		MUST be positive and smaller than the length of the list.

Return:

[Node, Node]

The new first and last nodes.

private _rotate_left_modulo(x: Node, z: Node, n: number, k: number): [Node, Node] source

import _rotate_left_modulo from '@data-structure-algebra/doubly-linked-list/src/_rotate_left_modulo.js'

Rotate non-empty list to the left n steps. The parameter n must be positive.

Params:

Name	Type	Attribute	Description
x	Node		The current first node.
z	Node		The current last node.
n	number		List length, MUST be positive.
k	number		MUST be positive.

Return:

[Node, Node]

The new first and last nodes.

private _rotate_left_unknown_length(x: Node, z: Node, k: number): [Node, Node] source

import _rotate_left_unknown_length from '@data-structure-algebra/doubly-linked-list/src/_rotate_left_unknown_length.js'

Rotate list to the right n steps. The parameter n must be positive.

Params:

Name	Type	Attribute	Description
x	Node		The current first node.
z	Node		The current last node.
k	number		MUST be positive.

Return:

[Node, Node]

The new first and last nodes.

private _rotate_right(x: Node, z: Node, k: number): [Node, Node] source

import _rotate_right from '@data-structure-algebra/doubly-linked-list/src/_rotate_right.js'

Rotate list to the right k steps. The parameter k must be positive and smaller than the length of the list.

Params:

Name	Type	Attribute	Description
x	Node		The current first node.
z	Node		The current last node.
k	number		MUST be positive and smaller than the length of the list.

Return:

[Node, Node]

The new first and last nodes.

private _rotate_right_modulo(x: Node, z: Node, n: number, k: number): [Node, Node] source

import _rotate_right_modulo from '@data-structure-algebra/doubly-linked-list/src/_rotate_right_modulo.js'

Rotate non-empty list to the right n steps. The parameter n must be positive.

Params:

Name	Type	Attribute	Description
x	Node		The current first node.
z	Node		The current last node.
n	number		List length, MUST be positive.
k	number		MUST be positive.

Return:

[Node, Node]

The new first and last nodes.

private _rotate_right_unknown_length(x: Node, z: Node, k: number): [Node, Node] source

import _rotate_right_unknown_length from '@data-structure-algebra/doubly-linked-list/src/_rotate_right_unknown_length.js'

Rotate list to the right n steps. The parameter n must be positive.

Params:

Name	Type	Attribute	Description
x	Node		The current first node.
z	Node		The current last node.
k	number		MUST be positive.

Return:

[Node, Node]

The new first and last nodes.

private _rotate_to(x: , y: , z: *) source

import _rotate_to from '@data-structure-algebra/doubly-linked-list/src/_rotate_to.js'

Params:

Name	Type	Attribute	Description
x	*
y	*
z	*

private _shift(x: Node): Node source

import _shift from '@data-structure-algebra/doubly-linked-list/src/_shift.js'

Removes first Node from a non-empty list.

Params:

Name	Type	Attribute	Description
x	Node		First node (not null). Cannot be the last node.

Return:

Node	New list (not null).

private _split(x: Node) source

import _split from '@data-structure-algebra/doubly-linked-list/src/_split.js'

Split a list at Node x.

/!\ The node to split at cannot be the first of the list.

Params:

Name	Type	Attribute	Description
x	Node		Node to split at.

private _unshift(x: Node, value: any): Node source

import _unshift from '@data-structure-algebra/doubly-linked-list/src/_unshift.js'

Unshift value to list.

Params:

Name	Type	Attribute	Description
x	Node		First node of first input list (can be null).
value	any		Value to unshift.

Return:

Node	The node at the front of the list (hence, the new node).