Concepts: external list API

Conceptual API for external (headless) lists.

Concepts

ExtList, ExtSList, ExtValueList, and ExtValueSList manipulate external circular lists without a sentinel head node. They are pointer-like and can reference any node in the list.

Multiple external list objects may point to the same list or node, subject to the same invalidation rules as pointers. See Concepts: pointers.

Generic inspection API

Modelled after Concepts: list API.

Method	Description	Complexity	ExtList	ExtSList
constructor(head = null, options)	create a new list	O(1)	✔	✔
isNodeLike(node)	check if a node is compatible with this list	O(1)	✔	✔
isCompatible(list)	check if a list is compatible with this list	O(1)	✔	✔
isCompatibleNames(options)	check if two lists have compatible link names	O(1)	✔	✔
isCompatiblePtr(ptr)	check if a pointer is compatible with this list	O(1)	✔	✔
isCompatibleRange(range)	check if a range is compatible with this list	O(1)	✔	✔
isEmpty	check if the list is empty	O(1)	✔	✔
isOne	check if the list has only one node	O(1)	✔	✔
isOneOrEmpty	check if the list has only one node or it is empty	O(1)	✔	✔
head	actual pointer to a list node or null	O(1)	✔	✔
front	get the first node (an alias to head)	O(1)	✔	✔
back	get the last node	O(1)	✔	✔
range	get the range of the list	O(1)	✔	✔
ptrRange	get the pointer range of the list	O(1)		✔
getLength()	get the length of the list	O(n)	✔	✔

head, front, back, range, and ptrRange return null when unattached. The list is empty iff head is null.

Head manipulation API

Method	Description	Complexity	ExtList	ExtSList
attach(head)	attach an external circular list	O(1)	✔	✔
detach()	detach the list	O(1)	✔	✔

Helper methods API

Modelled after Concepts: list API.

Method	Description	Complexity	ExtList	ExtSList
makePtr(node)	create a new pointer	O(1)	✔	✔
makePtrFromPrev(prev)	create a new pointer from its previous node	O(1)	✔	✔
adoptNode(node)	adopt a node	O(1)	✔	✔
adoptValue(value)	adopt a value by creating a value node	O(1)	✔	✔
normalizeNode(node)	normalize a node	O(1)	✔	✔
normalizeRange(range)	normalize a range	O(1)	✔	✔
normalizePtrRange(range)	normalize a pointer range	O(1)		✔
syncPrev()	synchronize the reference of the previous node	O(n)		✔

Pointer-like API

Modelled after Concepts: pointers.

Method	Description	Complexity	ExtList	ExtSList
isPrevNodeValid()	return a boolean value indicating whether the previous node is available	O(1)	✔	✔
next()	move the pointer to the next node	O(1)	✔	✔
prev()	move the pointer to the previous node	O(1)	✔	✔
removeCurrent()	remove the node the pointer points to	O(1)	✔	✔
addBefore(value)	insert a value/node before the current one	O(1)	✔	✔
addAfter(value)	insert a value/node after the current one	O(1)	✔	✔
addNodeBefore(node)	insert a node before the current one	O(1)	✔	✔
addNodeAfter(node)	insert a node after the current one	O(1)	✔	✔
insertBefore(extList)	insert a compatible list before the current node	O(1)	✔	✔
insertAfter(extList)	insert a compatible list after the current node	O(1)	✔	✔

Additional pointer-like API

Method	Description	Complexity	ExtList	ExtSList
removeNodeBefore(node)	remove a node before the current one	O(1)		✔
removeNodeAfter(node)	remove a node after the current one	O(1)	✔	✔
moveBefore(node)	move a node before the current one	O(1)	✔	✔
moveAfter(node)	move a node after the current one	O(1)	✔	✔

List-like API

Modelled after Concepts: list API.

Method	Description	Complexity	ExtList	ExtSList
clear()	clear the list	O(1)	✔	✔
clear(true)	clear the list and isolate nodes	O(n)	✔	✔
removeNode(node)	remove a node	O(1)	✔	✔*
removeRange(range)	remove a range	O(1)	✔	✔*
removeRange(range, true)	remove a range and isolate nodes	O(k)	✔	✔*
extractRange(range)	extract a range	O(1)	✔	✔*
extractBy(condition)	extract nodes by a condition	O(n)	✔	✔
reverse()	reverse the list	O(n)	✔	✔
sort(lessFn)	sort the list (stable)	O(n log n)	✔	✔

ExtSList implements some methods with a different signature (marked with an asterisk) — SLL needs the previous node, which a pointer carries but a bare node doesn't:

ExtList	ExtSList
removeNode(node)	removeNode(ptr)
removeRange(range, drop)	removeRange(ptrRange, drop)
extractRange(range)	extractRange(ptrRange)

Iteration API

Modelled after Concepts: list API.

Method	Description	Complexity	ExtList	ExtSList
[Symbol.iterator]()	get a default iterator	O(1)	✔	✔
getIterator(range = {})	get an iterator	O(1)	✔	✔
getNodeIterator(range = {})	get a node iterator	O(1)	✔	✔
getPtrIterator(range = {})	get a pointer iterator	O(1)	✔	✔
getReverseIterator(range = {})	get a reverse iterator	O(1)	✔
getReverseNodeIterator(range = {})	get a reverse node iterator	O(1)	✔
getReversePtrIterator(range = {})	get a reverse pointer iterator	O(1)	✔

Value-based iteration (getValueIterator, getReverseValueIterator) lives on ExtValueList / ExtValueSList — see Concepts: value list API.

Meta helpers API

Modelled after Concepts: list API.

Method	Description	Complexity	ExtList	ExtSList
clone()	clone the list	O(n)	✔	✔
make()	make a new compatible list	O(1)	✔	✔
makeFrom(values)	make a new compatible list from an iterable	O(n)	✔	✔
makeFromRange(range)	make a new compatible list from a range	O(1)	✔	✔

Static helpers API

Modelled after Concepts: list API.

Method	Description	Complexity	ExtList	ExtSList
from(values, options)	make a new list from an iterable	O(n)	✔	✔
fromRange(range, options)	make a new list from a range	O(1)	✔	✔