DLL: external lists

External (headless) doubly linked lists for inspecting and manipulating externally defined circular lists.

Prerequisites: Backgrounder, Concepts: list API. Built on DLL: foundation.

Legend for tables

• API
  • options - options object, which contains nextName and prevName link names with default values "next" and "prev".
    • Only doubly linked lists use prevName.
  • node - a node object in the list
  • head - a node in the external list
  • list - a list object of the same type as the current list
  • ptr - a pointer to a node in the list
  • range - a range of nodes in the list
  • nodeOrPtr - a node or a pointer to a node
  • value - a value
  • values - an iterable that provides values
  • iterator - an Iterator instance or an object with an iterator/iterable protocol
• Complexity
  • O - complexity of an operation
  • O(1) - constant time
  • O(n) - linear time proportional to the list size
  • O(k) - linear time proportional to the list/range argument size

ext-list.js

User-facing module. Re-exports everything from list/ext.js; default export is ExtList.

import ExtList from 'list-toolkit/ext-list.js';

list/ext.js

Core implementation of the external headless doubly linked list.

import ExtList from 'list-toolkit/list/ext.js';

Class Ptr

Minimal pointer for ExtList, built on PtrBase.

PtrBase reference

Member	Return Value	Description	O
constructor(list, node, ListClass)	this	Create a new pointer to a node.	O(1)
list	list	The list it belongs to.	O(1)
node	node	The node it points to.	O(1)
nextNode	node	The next node.	O(1)
prevNode	node	The previous node.	O(1)
isPrevNodeValid()	truthy/falsy	Checks if prevNode is valid.	O(1)
next()	this	Move the pointer to the next node.	O(1)
prev()	this	Move the pointer to the previous node.	O(1)

Adds:

Member	Return Value	Description	O
constructor(list, node)	this	Create a new pointer to a node.	O(1)
clone()	this	Clone the pointer.	O(1)

Class ExtList

Based on ExtListBase; inherits all its properties and methods.

ExtListBase reference

Member	Return Value	Description	O
constructor(head, options)	this	Create a new listing optionally pointing to an external list.	O(1)
nextName	string/symbol	The name of the next property.	O(1)
prevName	string/symbol	The name of the previous property.	O(1)
head	node	The external list it points to or null if the list is empty.	O(1)
isNodeLike(node)	truthy/falsy	Checks if node is a node-like object.	O(1)
isCompatibleNames(options)	truthy/falsy	Checks if options have the same link names.	O(1)
isCompatible(list)	truthy/falsy	Checks if list is compatible with the list.	O(1)
isCompatiblePtr(ptr)	truthy/falsy	Checks if ptr is compatible with the list.	O(1)
isCompatibleRange(range)	truthy/falsy	Checks if range has the same link names.	O(1)
isEmpty	truthy/falsy	Checks if the list is empty.	O(1)
isOne	truthy/falsy	Checks if the list has only one node.	O(1)
isOneOrEmpty	truthy/falsy	Checks if the list has only one node or empty.	O(1)
front	node	The first node or null if the list is empty.	O(1)
back	node	The last node or null if the list is empty.	O(1)
range	range	The range of the list or null if the list is empty.	O(1)
getLength()	number	The length of the list or 0 if the list is empty.	O(n)
adoptNode(nodeOrPtr)	node	Adopt a node.	O(1)
adoptValue(value)	node	Adopt a value.	O(1)
normalizeNode(nodeOrPtr)	node	Normalize a node.	O(1)
normalizeRange(range)	range	Normalize a range.	O(1)
attach(head)	previous head	Attach the list to an external list.	O(1)
detach()	previous head	Detach the list from the external list and make it empty.	O(1)
next()	this	Move the pointer to the next node.	O(1)
prev()	this	Move the pointer to the previous node.	O(1)

Pointer-related:

Member	Return Value	Description	O
makePtr(node)	ptr	Create a new pointer from the list's node.	O(1)
makePtrFromPrev(prev)	ptr	Create a new pointer from its previous node.	O(1)

Remove nodes:

Member	Return Value	Description	O
removeCurrent()	node or null	Remove the current node and move forward.	O(1)
removeNode(nodeOrPtr)	node or null	Remove a node.	O(1)
removeBefore()	node or null	An alias for removeNodeBefore().	O(1)
removeNodeBefore()	node or null	Remove a node before the current one.	O(1)
removeAfter()	node or null	An alias for removeNodeAfter().	O(1)
removeNodeAfter()	node or null	Remove a node after the current one.	O(1)

Additions and insertions:

Member	Return Value	Description	O
addBefore(value)	ptr	Add a new value node before the current node.	O(1)
addNodeBefore(node)	ptr	Add a new node before the current node.	O(1)
add(value)	ptr	An alias for addAfter().	O(1)
addAfter(value)	ptr	Add a new value node after the current node.	O(1)
addNodeAfter(node)	ptr	Add a new node after the current node.	O(1)
insertBefore(list)	ptr or null	Insert a list before the current node.	O(1)
insertAfter(list)	ptr or null	Insert a list after the current node.	O(1)

Move a node:

Member	Return Value	Description	O
moveBefore(nodeOrPtr)	ptr	Move a node before the current one.	O(1)
moveAfter(nodeOrPtr)	ptr	Move a node after the current one.	O(1)

Clear, remove, extract:

Member	Return Value	Description	O
clear(drop = false)	this	Clear the list.	O(1)
clear(drop = true)	this	Clear the list and drop the nodes.	O(n)
removeRange(range, drop = false)	this	Remove a range of nodes.	O(1)
removeRange(range, drop = true)	this	Remove and isolate a range of nodes.	O(k)
extractRange(range)	list	Extract a range of nodes.	O(1)
extractBy(condition)	list	Extract nodes by a condition.	O(n)

Specialized in-place algorithms:

Member	Return Value	Description	O
reverse()	this	Reverse the list.	O(n)
sort(lessFn)	this	Sort the list — stable natural merge sort, O(n) on sorted input, O(log n) auxiliary space.	_O(n _ log(n))*

Iterators:

Member	Return Value	Description	O
[Symbol.iterator]()	iterator	the default node iterator for the whole list	O(1)
getIterator(range)	iterator	an alias of getNodeIterator(range)	O(1)
getNodeIterator(range)	iterator	create a node iterator with an optional range	O(1)
getPtrIterator(range)	iterator	create a pointer iterator with an optional range	O(1)
getReverseIterator(range)	iterator	an alias of getReverseNodeIterator(range)	O(1)
getReverseNodeIterator(range)	iterator	create a reverse node iterator with an optional range	O(1)
getReversePtrIterator(range)	iterator	create a reverse pointer iterator with an optional range	O(1)

Meta helpers:

Member	Return Value	Description	O
clone()	list	clone the list	O(1)
make()	list	create a compatible empty list	O(1)
makeFrom(values)	list	create a compatible list from an iterable	O(k)

Static methods:

Member	Return Value	Description	O
ExtList.from(values, options)	list	create a list from an iterable	O(k)

Notes on properties and methods

Nodes are modified in place — never copied. Pointers remain valid; list is updated.

• addXXX() — returns a pointer to the inserted node.
• removeXXX() — returns the removed stand-alone node.
• insertXXX() — returns a pointer to the first inserted node; source list becomes empty.
• clear() / removeRange() — optional drop (default false); when true, removed nodes are made stand-alone.
• clone() — new ExtList sharing the same head (no node copying).

Exports

ExtList is the default export. Ptr is also exported and accessible as ExtList.Ptr.

ext-value-list.js

User-facing module. Re-exports everything from list/ext-value.js; default export is ExtValueList.

import ExtValueList from 'list-toolkit/ext-value-list.js';

list/ext-value.js

Value-based version of ExtList.

import ExtValueList from 'list-toolkit/list/ext-value.js';

Class ExtValueList

Subclass of ExtList for value-based lists. Overrides/adds:

Member	Return Value	Description	O
adoptValue(value)	node	create a node from a value	O(1)
[Symbol.iterator]()	iterator	the default value iterator for the whole list	O(1)
getIterator(range)	iterator	an alias of getValueIterator(range)	O(1)
getValueIterator(range)	iterator	create a value iterator with an optional range	O(1)
getReverseIterator(range)	iterator	an alias of getReverseValueIterator(range)	O(1)
getReverseValueIterator(range)	iterator	create a reverse value iterator with an optional range	O(1)
clone()	list	clone the list	O(1)
make()	list	create a compatible empty list	O(1)
makeFrom(values)	list	create a compatible list from an iterable	O(k)
ExtValueList.from(values, options)	list	create a list from an iterable	O(k)

Notes on properties and methods

adoptValue() wraps a value in a new ValueNode. Reuses an existing ValueNode if stand-alone.

clone() shares the same head (no node copying). Use makeFrom(list) to duplicate value nodes.

Exports

ExtValueList is the default export. Also exports Ptr (same as ExtList).