SLL: pointers

SLL pointers track the previous node, enabling O(1) insert/remove operations that would otherwise be impossible.

Prerequisites: Backgrounder, Concepts: list API. Used by SLL: lists.

Legend for tables

• API
  • options - options object, which contains nextName link name with default value "next".
  • 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

slist/ptr.js

Pointer implementation for hosted singly linked lists.

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

Also exported by SList as SList.Ptr. Typically created via list methods rather than imported directly.

Class Ptr

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

PtrBase reference

Member	Return Value	Description	O
constructor(list, node, prev, 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)
syncPrev()	this	Sync the previous node.	O(n)

Ptr adds the following methods:

Member	Return Value	Description	O
constructor(list, node, prev)	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 advances to the next. addXXX() returns a pointer to the new node. insertXXX() returns a pointer to the first inserted node (or null if the list was empty).

Exports

Ptr is exported as Ptr and as the default export.