SLL: external lists

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

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

Legend for tables

• API
  • options - options object, which contains nextName link name with default value "next".
  • 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-slist.js

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

import ExtSList from 'list-toolkit/ext-slist.js';

slist/ext.js

Core implementation of the external headless singly linked list.

import ExtSList from 'list-toolkit/slist/ext.js';

Class Ptr

Minimal pointer for ExtSList, built on PtrBase.

PtrBase reference

Member	Return Value	Description	O
constructor(list, node, prev, 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)
syncPrev()	this	Sync the previous node.	O(n)

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 ExtSList

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)
head	node or null	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)
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)
getBack()	node	The last node or null 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)

Pointer-related:

Member	Return Value	Description	O
ptrRange	range	The range of the list or null if the list is empty.	O(1)
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
removeNode(ptr)	node or null	Remove a node.	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
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)
insertAfter(list)	ptr or null	Insert a list after the current node.	O(1)

Move a node:

Member	Return Value	Description	O
moveAfter(ptr)	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(ptrRange, drop = false)	this	Remove a range of nodes.	O(1)
removeRange(ptrRange, drop = true)	this	Remove and isolate a range of nodes.	O(k)
extractRange(ptrRange)	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)

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
ExtSList.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.

Unlike ExtList, ExtSList methods accept pointers (not bare nodes) because the previous node is required. Ensure isPrevNodeValid() is true before calling. Pointer ranges must also have a valid prevNode on the from pointer.

• 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 ExtSList sharing the same head (no node copying).

Exports

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

ext-value-slist.js

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

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

slist/ext-value.js

Value-based version of ExtSList.

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

Class ExtValueSList

Subclass of ExtSList 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)
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)
ExtValueSList.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

ExtValueSList is the default export. Also exports Ptr (same as ExtSList).