Utilities: NT lists

This module provides utilities to inspect null-terminated (NT) lists and convert them to circular lists compatible with this toolkit and back.

Utilities will work with doubly linked lists (DLL) ans singly linked lists (SLL).

Legend for tables

• API
  • options - an optional options object, which contains nextName and prevName link names with default values "next" and "prev".
    • Only doubly linked lists use prevName.
  • head - the first node object of the list
  • node - a node object in the list
  • list - a returned object with two properties: head and tail. head is the first node of the list and tail is the last one.
• 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

nt-utils.js

This module is a collection of functions that work with null-terminated (NT) lists.

import {makeSListFromNTList} from 'list-toolkit/nt-utils.js';

The following functions are exported:

Function	Return Value	Description	O
isNTList(head, options)	boolean	Check if the list is an NT list.	O(n)
getNTListTail(head, options)	node	Get the last node of the NT list.	O(n)
getNTListHead(node, options)	node	Get the first node of the NT doubly linked list.	O(n)
getNTListLength(head, options)	number	Get the length of the NT list.	O(n)
makeListFromNTList(node, options)	list	Convert the NT list to a doubly linked list.	O(n)
makeSListFromNTList(head, options)	list	Convert the NT list to a singly linked list.	O(n)
makeNTListFromList(head, options)	list	Convert the DLL list to an NT list.	O(1)
makeNTListFromSListFast(head, options)	list	Convert the SLL list to a NT singly linked list.	O(1)
makeNTListFromSList(head, options)	list	Convert the SLL list to a NT singly linked list.	O(n)

isNTList() returns true if the list is terminated with null, if we follow the "next" links. If traversing the list the function comes back to the original head, which is normal for circular lists, it returns false. It can be used with doubly and singly linked NT lists.

getNTListTail() follows the "next" links and returns the last node in the NT list. It can be used with doubly and singly linked NT lists.

getNTListHead() follows the "prev" links and returns the first node in the doubly linked NT list. The idea of the function is that we have some middle node in the NT list and want to find the first node in the list it belongs to.

getNTListLength() returns the length of the NT list in number of nodes. It can be used with doubly and singly linked NT lists.

All makeXXX() functions do not copy nodes, but modify them in place. They return an object with this shape: {head, tail}.

All makeXXXFromNTList() functions create so called external headless lists (see Hosted lists vs. headless lists in the Backgrounder). Such lists can be used directly by ExtList and ExtSList, or they can be converted to hosted lists by List.fromExtList() (see Class List) or by SList.fromExtList() (see Class SList).

All makeNTListFromXXX() functions create NT lists from external headless DLL and SLL lists. They do not attempt to exclude a host node from the list nor exclude nodes from the existing lists nor update a possible list object in any way. If you want to convert the existing List or SList to an NT list use their method releaseNTList() instead.

makeNTListFromSListFast() is a faster version of makeNTListFromSList() (O(1) vs. O(n)). But it creates a different list: the first node of the circular list is used as the last node of the new NT list, and the next (after the first) node of the circular list is used as the first node of the new NT list.

makeNTListFromSList() finds the last node and creates the NT list from the head and the found last node. Finding the last node takes O(n) time.