-
-
Notifications
You must be signed in to change notification settings - Fork 0
SLL: pointers
Pointers point to nodes and provide some operations using their node as an anchor point. Singly linked list pointers are very important because they can track a previous node required for many O(1) operations.
This document describes the foundational classes and methods of the implementation of singly 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 SLL: lists document.
Legend for tables
-
API
-
options
- options object, which containsnextName
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
This module contains the implementation of pointer objects used with the hosted singly linked list.
import Ptr from 'list-toolkit/slist/ptr.js';
The same class is exported by SList module and as SList.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.
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) |
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.
Ptr
is exported as Ptr
and as the default export.