DLL: 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) doubly 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 DLL: foundation document.

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

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

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

list/ext.js

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

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

Class Ptr

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

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 ExtList

ExtList 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)
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()	this or null	Remove the current node and move forward.	O(1)
removeNode(nodeOrPtr)	this or null	Remove a node.	O(1)
removeBefore()	this or null	An alias for removeNodeBefore().	O(1)
removeNodeBefore()	this or null	Remove a node before the current one.	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
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.	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

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

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 ExtList object with the same head. It does not copy any nodes.

Exports

ExtList is exported as ExtList and as the default export.

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

ext-value-list.js

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

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

list/ext-value.js

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

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

Class ExtValueList

Essentially, ExtValueList is a subclass of ExtList that provides niceties for value-based lists. On top of ExtList, ExtValueList 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)
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() 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 ExtList object with the same head. It does not copy any nodes. Use makeFrom(list) if want to duplicate value nodes.

Exports

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