SLL: lists

Hosted singly linked lists. SList links external objects via a configurable next-link property; the same object can belong to multiple lists with non-overlapping link names. ValueSList wraps arbitrary values.

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

slist.js

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

import SList from 'list-toolkit/slist.js';

slist/core.js

Core implementation of the hosted singly linked list.

import SList from 'list-toolkit/slist/core.js';

Class SList

SList is based on HeadNode, which is based on Node, and inherits all their properties and methods.

Node reference

Member	Return Value	Description	O
constructor(options)	this	Creates a new node.	O(1)
nextName	string/symbol	The name of the next link.	O(1)
[nextName]	node	The next node.	O(1)
isStandAlone	boolean	Getter — true when the node is stand-alone.	O(1)

HeadNode reference

Member	Return Value	Description	O
last	node	The last node.	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 has the same link names.	O(1)
isCompatiblePtr(ptr)	truthy/falsy	Checks if ptr has the same link names.	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)
head	list	The list itself.	O(1)
front	node	The first node.	O(1)
back	node	The last node.	O(1)
range	range	The list range from the first to the last node or null if the list is empty.	O(1)
getLength()	number	The number of nodes in the list.	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)
syncLast()	this	Sync the last node.	O(n)

Pointer-related:

Member	Return Value	Description	O
frontPtr	ptr	The pointer to the first node.	O(1)
ptrRange	range or null	The range of the list.	O(1)
makePtr(node)	ptr	Create a new pointer from the list's node.	O(1)
makePtrFromPrev(prev)	ptr	Create a new pointer from the previous node.	O(1)

Push/pop:

Member	Return Value	Description	O
push(value)	ptr	Alias of pushFront(value).	O(1)
pushFront(value)	ptr	Add a value to the front of the list.	O(1)
pushBack(value)	ptr	Add a value to the back of the list.	O(1)
pushFrontNode(nodeOrPtr)	ptr	Add a node to the front of the list.	O(1)
pushBackNode(nodeOrPtr)	ptr	Add a node to the back of the list.	O(1)
pop()	node	Alias of popFront().	O(1)
popFront()	node	Alias of popFrontNode().	O(1)
popFrontNode()	node	Remove and return the first node or undefined if the list is empty.	O(1)

Append:

Member	Return Value	Description	O
append(list)	ptr	Alias of appendBack(list).	O(1)
appendFront(list)	ptr	Add a list to the front of the list.	O(1)
appendBack(list)	ptr	Add a list to the back of the list.	O(1)

Move a node:

Member	Return Value	Description	O
moveToFront(nodeOrPtr)	ptr	Move a node to the front of the list.	O(1)
moveToBack(nodeOrPtr)	ptr	Move a node to the back of the list.	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)
removeNode(nodeOrPtr)	node	Remove a node.	O(1)
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))*
insertSorted(value, lessFn)	Ptr	Insert a value into a sorted list at its position (after equal nodes).	O(n)
mergeSorted(list, lessFn)	this	Merge a sorted list into this sorted list; stable; drains the argument.	O(n + m)

Lists and ranges:

Member	Return Value	Description	O
releaseRawList()	node or null	Release the list as a headless list and return its first node or null if the list is empty.	O(1)
releaseAsPtrRange()	ptrRange or null	Release the list as a pointer range or null if the list is empty.	O(1)
releaseNTList()	{head, tail}	Release the list as a null-terminated list and return its head and tail.	O(1)
validateRange(range)	boolean	Validate a range.	O(1)

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
make()	list	create a compatible empty list	O(1)
makeFrom(values)	list	create a compatible list from an iterable	O(k)
makeFromRange(range)	list	create a compatible list and append the range	O(1)

Static methods:

Member	Return Value	Description	O
SList.from(values, options)	list	create a list from an iterable	O(k)
SList.fromPtrRange(ptrRange, options)	list	create a list and append the range	O(1)
SList.fromExtList(extList)	list	create a compatible list from a circular list	O(1)

Notes on properties and methods

Nodes are modified in place — never copied. Existing pointers continue to reference the node; list is updated to the current list.

• pushXXX() — returns a pointer to the inserted node.
• popXXX() / removeNode() — returns the removed stand-alone node (next link points to itself).
• appendXXX() — returns a pointer to the first appended node; source list becomes empty.
• clear() / removeRange() — optional drop (default false); when true, removed nodes are made stand-alone.
• releaseRawList() — empties the list and returns the first node of the resulting headless circular list (usable by ExtSList).
• releaseNTList() — empties the list and returns {head, tail} of a null-terminated list.
• validateRange(range) — checks compatibility and ensures the range excludes the head.
• makeFromRange(range) — creates a new list by moving a node range from its source. Requires range.list (SLL has no back-pointer; the source list is walked to derive prevFrom).
• SList.fromPtrRange(ptrRange, options) — static counterpart that takes a pointer range; the Ptr's prevNode removes the need for a walk.
• SList.fromRange(range, options) — static counterpart that takes a node range with range.list.
• SList.fromExtList(extList) — creates a hosted list from a headless circular list; source is cleared. By contract the result is rotated by one — it starts at the headless list's head.next and the old head lands last: that is what makes the conversion O(1) (an order-faithful copy would need an O(n) walk to find the ring's back — use getBack() when order matters, as ExtSList.sort() does).

Exports

SList is exported as SList and as the default export.

Its pointer class is exported as Ptr and it can be accessed as SList.Ptr.

value-slist.js

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

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

slist/value.js

Value-based version of SList.

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

Class ValueSList

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

Member	Return Value	Description	O
pop()	value	an alias of popFront()	O(1)
popFront()	value	remove and return the first node value or undefined if the list is empty	O(1)
adoptValue(value)	node	converts a value to a node	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()	a copy of the list	O(n)
make()	a new compatible empty list	O(1)
makeFrom(values)	a new compatible list with the specified values	O(n)

Notes on properties and methods

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

clone() creates new ValueNode copies.

Exports

ValueSList is the default export. Also exports Ptr (same as SList) and ValueNode (accessible as ValueSList.ValueNode).