DLL: pointers

Pointers point to nodes and provide some operations using their node as an anchor point. Additionally, pointers can be used to organize a sophisticated traversal of the list if range-based iterators were deemed insufficient.

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 used by lists described in the DLL: lists 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/ptr.js

This module contains the implementation of pointer objects used with the hosted doubly linked list.

import Ptr from 'list-toolkit/list/ptr.js';

The same class is exported by List module and as List.Ptr. In most cases users do not need to use this module directly. Usually, pointers are created by the list methods, which are described in the Concepts: list API document.

Class Ptr

Ptr is based on PtrBase and inherits all its properties and methods.

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)

Ptr adds the following methods:

Member	Return Value	Description	O
constructor(list, node)	this	Create a new pointer to a node.	O(1)
isHead	boolean	Checks if the pointer points to the head node.	O(1)
clone()	ptr	Create a copy of the pointer.	O(1)
removeCurrent()	node	Remove the current node.	O(1)
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)
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)

Notes on properties and methods

removeCurrent() removes the current node and moves to the next node.

All addXXX() methods return a new pointer to the newly added node.

All insertXXX() methods return a new pointer to the first node of the inserted list. It can be null if the inserted list is empty.

Exports

Ptr is exported as Ptr and as the default export.