Utilities: lists

This module provides a few helpful utilities that can be used with different implementations of lists.

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
  • list - a list object
  • ptr - a pointer to a node in the list
  • value - a value
  • values - an iterable that provides values
  • condition - a function that accepts a node and returns a boolean
  • adapter - a returned object with just enough properties to use as a list by some utilities
• 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-utils.js

This module is a collection of functions implementing common list operations.

import {pushValuesFront, pushValuesBack} from 'list-toolkit/list-utils.js';

The following functions are exported:

Function	Return value	Description	O
isValidList(list)	boolean	Check if the DLL list is valid.	O(n)
isValidSList(list)	boolean	Check if the SLL list is valid.	O(n)
pushValuesFront(list, values)	list	Add values to the front of the list sequentially.	O(k)
pushValuesBack(list, values)	list	Add values to the back of the list sequentially.	O(k)
appendValuesFront(list, values)	list	Add values to the front of the list in the given sequence.	O(k)
appendValuesBack(list, values)	list	Add values to the back of the list in the given sequence.	O(k)
addValuesBefore(ptr, values)	ptr	Add values before the pointer sequentially.	O(k)
addValuesAfter(ptr, values)	ptr	Add values after the pointer sequentially.	O(k)
insertValuesBefore(ptr, values)	ptr	Insert values before the pointer in the given sequence.	O(k)
insertValuesAfter(ptr, values)	ptr	Insert values after the pointer in the given sequence.	O(k)
findNodeBy(list, condition)	node or null	Find the first node that satisfies the condition.	O(n)
findPtrBy(list, condition)	ptr or null	Find the first pointer that satisfies the condition.	O(n)
removeNodeBy(list, condition)	node or null	Remove the first node that satisfies the condition.	O(n)
backPusher(ExtListClass, options)	adapter	Create a back pusher.	O(1)
frontPusher(ExtListClass, options)	adapter	Create a front pusher.	O(1)

isValidList() iterates over the list until it reaches the end. While doing so it checks that the next and prev pointers point correctly. If the list is invalid it returns false. Otherwise it returns true.

isValidSList() iterates over the list until it reaches the end. While doing so it checks that the next pointer is valid (not null or undefined). If the list is invalid it returns false. Otherwise it returns true.

pushValuesFront() and pushValuesBack() add values to the front or back of the list. Logically they can be seen as pushing values from the iterable to the list sequentially. Note that pushValuesFront() effectively adds the values in reverse order.

appendValuesFront() and appendValuesBack() add values as logical lists to the front or back of the list.

For generic iterable appendValuesFront() creates an array, then adds it to the list in the correct order. That makes it different from pushValuesFront().

appendValuesBack() and pushValuesBack() are logically the same but the former can be more efficient if the underlying list supports it.

addValuesBefore() and addValuesAfter() add values before or after the pointer. They are pointer-specific equivalents of pushValuesBack() and pushValuesFront() respectively. Note that addValuesAfter() effectively adds the values in reverse order just like pushValuesFront().

insertValuesBefore() and insertValuesAfter() insert values before or after the pointer. They are pointer-specific equivalents of appendValuesBack() and appendValuesFront().

insertValuesBefore() and addValuesBefore() are logically the same but the former can be more efficient if the underlying list supports it.

findNodeBy() and findPtrBy() find the first node the condition. If condition(node) returns true then that node or its pointer is returned. Otherwise null is returned.

removeNodeBy() removes the first node that satisfies the condition. If condition(node) returns true then that node is removed and returned. Otherwise null is returned.

backPusher() and frontPusher() create a back or front pusher object that can be used to push values to the list in the correct order, e.g., with pushValuesFront() or pushValuesBack(). It allows to push nodes to external headless lists using standard operations of the hosted lists.

The returned object has the following properties:

• nextName - name of the next link
• prevName - name of the previous link (optional, SLL does not use it)
• releaseList() - returns the external list of ExtListClass, clears the internal list

backPusher() exposes the pushBackNode(node) method that adds a node to the back of the internal list.

frontPusher() exposes the pushFrontNode(node) method that adds a node to the front of the internal list.

Exports

All documented functions are exported by their names.