DLL: lists

Simple hosted doubly linked lists are the main feature of the toolkit. They are simple to use yet versatile and efficient. List is used to link external objects in a list. It is possible to have the same object as a member of several lists with non-intersecting link names. In this scenario objects play role of nodes in the list and can be used to manipulate the list directly, e.g., define ranges, iterate, add/remove nodes, etc.

A value list can be used as an ordered container for arbitrary values.

This document describes the foundational classes and methods of the implementation of 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

list.js

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

import List from 'list-toolkit/list.js';

list/core.js

This module contains the core implementation of the hosted doubly linked list.

import List from 'list-toolkit/list/core.js';

Class List

List 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)
prevName	string/symbol	The name of the previous link.	O(1)
[nextName]	node	The next node.	O(1)
[prevName]	node	The previous node.	O(1)
isStandAlone()	boolean	Checks if the node is stand-alone.	O(1)

HeadNode reference

Member	Return Value	Description	O
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)

Pointer-related:

Member	Return Value	Description	O
frontPtr	ptr	The pointer to the first node.	O(1)
backPtr	ptr	The pointer to the last node.	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)
popBack()	node	Alias of popBackNode().	O(1)
popFrontNode()	node	Remove and return the first node or undefined if the list is empty.	O(1)
popBackNode()	node	Remove and return the last 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.	O(n * log(n))

Lists and ranges:

Member	Return Value	Description	O
releaseRawList()	node	Release the list as a headless list and return its first node.	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)
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
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
List.from(values, options)	list	create a list from an iterable	O(k)
List.fromRange(range, options)	list	create a list and append the range	O(1)
List.fromExtList(extList)	list	create a compatible list from a circular list	O(1)

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 push methods (pushXXX()) return a pointer to the inserted node. All pop methods (popXXX()) return the removed node, which is stand-alone (next/previous links point to itself). The same applies to removeNode(), which is similar to pop methods but operates on the specified node.

All append methods (appendXXX()) return a pointer to the first node of the appended 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.

releaseRawList() is a helper method that removes the head node (making the list empty) and returns the first node of a circular list. That list can be used by ExtList later. Additionally, it can be used by different libraries if necessary.

releaseNTList() is a helper method that removes the head node (making the list empty) and returns the rest as a null-terminated list. The list is returned as the {head, tail} pair with the first node as head and the last node as tail.

validateRange() is a helper method that checks if the range is compatible with the list and does not include the head of the list.

makeFromRange() is a helper method that creates a list and appends the range. The range must be compatible with the list. The range will be removed from its source list and moved to the new list.

List.fromExtList() is a helper method that creates a compatible list from a circular list. The source list will be cleared.

Exports

List is exported as List and as the default export.

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

value-list.js

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

import ValueList from 'list-toolkit/value-list.js';

list/value.js

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

import ValueList from 'list-toolkit/list/value.js';

Class ValueList

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

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)
popBack()	value	remove and return the last 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)
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()	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() 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 new value nodes and appends them to the new list.

Exports

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

Additionally, it exports ValueNode and it can be accessed as ValueList.ValueNode