-
-
Notifications
You must be signed in to change notification settings - Fork 0
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 containsnextName
andprevName
link names with default values"next"
and"prev"
.- Only doubly linked lists use
prevName
.
- Only doubly linked lists use
-
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
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';
This module contains the core implementation of the external headless doubly linked list.
import ExtList from 'list-toolkit/list/ext.js';
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) |
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) |
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.
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
.
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';
This module contains the implementation of the value-based version of ExtList
.
import ExtValueList from 'list-toolkit/list/ext-value.js';
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) |
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.
ExtValueList
is exported as ExtValueList
and as the default export.
It exports Ptr
the same way as ExtList
. See details above.