SLL: external lists

The external lists are used mostly to inspect and manipulate externally defined circular lists. It is assumed that all external nodes are heterogeneous.

This document describes the implementation of external (headless) singly linked lists. Make sure to familiarize yourself with the Backgrounder and Concepts: list API first. Facilities that described here are built on top of the SLL: foundation document.

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

This is a user-facing module. It exposes all exports from slist/ext.js (see below) and the ExtSList class as the default export.

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

slist/ext.js

This module contains the core implementation of the external headless singly linked list.

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

Class Ptr

Ptr is a pointer to a node in a list. This class is used only by ExtSList. It is the minimal implementation of a pointer on top of 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)

It inherits all properties and methods from PtrBase and implements the following methods:

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

ExtSList is based on ExtListBase and inherits all their 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)	this or null	Remove a node.	O(1)
removeAfter()	this or null	An alias for removeNodeAfter().	O(1)
removeNodeAfter()	this 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.	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

All node-based methods do not copy nodes. All nodes are modified in-place to manipulate their position in the list.

There is a slight difference between ExtList and ExtSList methods: the former methods accept nodes, while the latter methods accept pointers. The reason is that pointers can supply prevNode, which is required for an underlying algorithm. Before calling such methods make sure that isPrevNodeValid() returns true.

The same goes for methods that take pointer ranges: they should have a pointer with a valid prevNode property as the from property.

If a node was referenced by a pointer, it will continue to point to the node but its list property will be set to the current list.

All "add" methods (addXXX()) return a pointer to the inserted node. All "remove" methods (removeXXX()) return the removed node, which is stand-alone (next/previous links point to itself).

All insert methods (insertXXX()) return a pointer to the first node of the inserted list. The source lists are modified and will be empty.

Some removal methods (clear(), removeRange()) take an optional drop parameter, which is false by default. If drop is true, the removed nodes will be dropped. It means that all nodes will be removed and made stand-alone. It makes them directly usable with compatible lists, but requires a linear time.

clone() creates a new ExtSList object with the same head. It does not copy any nodes.

Exports

ExtSList is exported as ExtSList and as the default export.

Its pointer class is exported as Ptr and assigned as a static property, which can be accessed as ExtSList.Ptr.

ext-value-slist.js

This is a user-facing module. It exposes all exports from slist/ext-value.js (see below) and the ExtValueSList class as the default export.

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

slist/ext-value.js

This module contains the implementation of the value-based version of ExtSList.

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

Class ExtValueSList

Essentially, ExtValueSList is a subclass of ExtSList that provides niceties for value-based lists. On top of ExtSList, ExtValueSList provides/overrides the following:

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() is a helper method that converts a value to a node. Usually it creates a new node using ValueNode. If the value is already a ValueNode instance, it will try to reuse it, e.g., it should be stand-alone.

clone() creates a new ExtSList object with the same head. It does not copy any nodes. Use makeFrom(list) if want to duplicate value nodes.

Exports

ExtValueSList is exported as ExtValueSList and as the default export. It exports Ptr the same way as ExtSList. See details above.