connective-tissue

connective-tissue

connective-tissue is a collection of linked list and ring data structures implemented in and for JavaScript. The structures in this library follow the specifications of their classical counterparts; they are well-tested and optimal implementations of:

• singly linked list
• doubly linked list *
• header linked list *
• circular singly linked list
• circular doubly linked list

*work in progress

Installation

npm install connective-tissue

OR

yarn add connective-tissue

Supported Environments

connective-tissue currently supports UMD, CommonJS (node versions >= 10), and ESM build-targets

API Reference

Modules

Atomics

Classes

CircularDoublyLinkedList

CircularSinglyLinkedList

Atomics

• Atomics
  • .Node
    • new Node(value)
  • .ForwardNode
    • new ForwardNode(value)
  • .Sentinel
    • new Sentinel()

Atomics.Node

new Node(value)

Implements a bi-directional node

Node implements as a member a pointer to the list to which it belongs

Param	Type
value	any

Atomics.ForwardNode

new ForwardNode(value)

Implements a uni-directional (forward) node

ForwardNode implements as a member a pointer to the list to which it belongs

Param	Type
value	any

Atomics.Sentinel

new Sentinel()

Implements a ring data structure for terminating a bi-directional list

CircularDoublyLinkedList

• CircularDoublyLinkedList
  • new CircularDoublyLinkedList()
  • instance
    • .sentinel
    • .length
    • .size() ⇒ number
    • .next(node) ⇒ Node | null
    • .prev(node) ⇒ Node | null
    • .head() ⇒ Node | null
    • .tail() ⇒ Node | null
    • .insert(node, at) ⇒ Node
    • .remove(node) ⇒ Node
    • .pop(node) ⇒ Node
    • .move(node, at) ⇒ Node
    • .pushFront(value) ⇒ Node
    • .pushBack(value) ⇒ Node
    • .insertBefore(value, mark) ⇒ Node
    • .insertAfter(value, mark) ⇒ Node
    • .moveToFront(node) ⇒ Node
    • .moveToBack(node) ⇒ Node
    • .moveBefore(node, mark) ⇒ Node
    • .moveAfter(node, mark) ⇒ Node
    • .insertValue(value, at) ⇒ Node
    • .pushBackList(other)
    • .pushFrontList(other)
  • static
    • .create() ⇒ CircularDoublyLinkedList

new CircularDoublyLinkedList()

Implements a circular doubly linked list as a ring, such that the sentinel node is both the next node of the tail, and the previous node of the head

circularDoublyLinkedList.sentinel

The sentinel terminator node

Properties

Type
Sentinel

circularDoublyLinkedList.length

The list length, sans the sentinel terminator

Properties

Type
number

circularDoublyLinkedList.size() ⇒ number

The current size of the list, sans the sentinel node

circularDoublyLinkedList.next(node) ⇒ Node | null

Returns the next list node, if extant; else, null

Param	Type
node	Node

circularDoublyLinkedList.prev(node) ⇒ Node | null

Returns the previous list node, if extant; else, null

Param	Type
node	Node

circularDoublyLinkedList.head() ⇒ Node | null

Returns the head node of the list or null if the list is empty

circularDoublyLinkedList.tail() ⇒ Node | null

Returns the tail node of the list or null if the list is empty

circularDoublyLinkedList.insert(node, at) ⇒ Node

Insert a new node after a given node at

Param	Type
node	Node
at	Node

circularDoublyLinkedList.remove(node) ⇒ Node

Remove a given node from the list

Returns: Node - The removed node

Param	Type
node	Node

circularDoublyLinkedList.pop(node) ⇒ Node

Remove the last node from the list

Returns: Node - The removed node

Param	Type
node	Node

circularDoublyLinkedList.move(node, at) ⇒ Node

Move given node to at

Param	Type
node	Node
at	Node

circularDoublyLinkedList.pushFront(value) ⇒ Node

Push a new node with value value to the front of the list

Param	Type
value	any

circularDoublyLinkedList.pushBack(value) ⇒ Node

Push a new node with value value to the back of the list

Param	Type
value	any

circularDoublyLinkedList.insertBefore(value, mark) ⇒ Node

Insert a new node with value value immediately before mark

If mark is not an element of the list, the list is not modified

mark must not be null

Param	Type
value	any
mark	Node

circularDoublyLinkedList.insertAfter(value, mark) ⇒ Node

Insert a new node with value value immediately after mark

If mark is not an element of the list, the list is not modified

mark must not be null

Param	Type
value	any
mark	Node

circularDoublyLinkedList.moveToFront(node) ⇒ Node

Move a node to the front of the list

If the given node is not an element of the list, the list is not modified

The given node must not be null

Param	Type
node	Node

circularDoublyLinkedList.moveToBack(node) ⇒ Node

Move a node to the back of the list

If the given node is not an element of the list, the list is not modified

The given node must not be null

Param	Type
node	Node

circularDoublyLinkedList.moveBefore(node, mark) ⇒ Node

Move a given node to its new position before mark

If either the given node or mark are not an element of the list, or node == mark, the list is not modified

Both the node and mark must not be null

Param	Type
node	Node
mark	Node

circularDoublyLinkedList.moveAfter(node, mark) ⇒ Node

Move a given node to its new position after mark

If either the given node or mark are not an element of the list, or node == mark, the list is not modified

Both the node and mark must not be null

Param	Type
node	Node
mark	Node

circularDoublyLinkedList.insertValue(value, at) ⇒ Node

Convenience for inserting a given value into a new node after a given node at

Param	Type
value	any
at	Node

circularDoublyLinkedList.pushBackList(other)

Insert a copy of another list at the back of the caller list

The lists may be the same, but must not be null

Param	Type
other	CircularDoublyLinkedList

circularDoublyLinkedList.pushFrontList(other)

Insert a copy of another list at the front of the caller list

The lists may be the same, but must not be null

Param	Type
other	CircularDoublyLinkedList

CircularDoublyLinkedList.create() ⇒ CircularDoublyLinkedList

Instantiate an empty circular doubly linked list

CircularSinglyLinkedList

• CircularSinglyLinkedList
  • new CircularSinglyLinkedList()
  • instance
    • .head
    • .length
    • .size() ⇒ number
    • .next(node) ⇒ Node | null
    • .prev(node) ⇒ Node | null
    • .remove(node) ⇒ Node | null
    • .pop(node) ⇒ Node | null
    • .moveAfter(node, mark) ⇒ ForwardNode
    • .moveBefore(node, mark) ⇒ ForwardNode
    • .pushFront(value) ⇒ ForwardNode
    • .pushBack(value) ⇒ ForwardNode
    • .insertAfter(value, mark) ⇒ ForwardNode | null
    • .insertBefore(value, mark) ⇒ ForwardNode | null
    • .pushBackList(other)
    • .pushFrontList(other)
  • static
    • .create() ⇒ CircularSinglyLinkedList

new CircularSinglyLinkedList()

Implements a circular singular (linear) linked list

circularSinglyLinkedList.head

The head node; implemented internally as a ring

Properties

Type
ForwardNode

circularSinglyLinkedList.length

The current size of the list

Properties

Type
number

circularSinglyLinkedList.size() ⇒ number

The current size of the list

circularSinglyLinkedList.next(node) ⇒ Node | null

Returns the next list node, if extant; else, null

Param	Type
node	ForwardNode

circularSinglyLinkedList.prev(node) ⇒ Node | null

Returns the previous list node, if extant; else, null

Param	Type
node	ForwardNode

circularSinglyLinkedList.remove(node) ⇒ Node | null

Remove a given node from the list

Returns: Node | null - The removed node

Param	Type
node	ForwardNode

circularSinglyLinkedList.pop(node) ⇒ Node | null

Remove the last node from the list

Returns: Node | null - The removed node

Param	Type
node	ForwardNode

circularSinglyLinkedList.moveAfter(node, mark) ⇒ ForwardNode

Move a given node to its new position after mark

If either the given node or mark are not an element of the list; node == mark; or mark.next == node, the list is not modified

Both the node and mark must not be null

Param	Type
node	ForwardNode
mark	ForwardNode

circularSinglyLinkedList.moveBefore(node, mark) ⇒ ForwardNode

Move a given node to its new position before mark

If either the given node or mark are not an element of the list; node == mark; or node.next == mark, the list is not modified

Both the node and mark must not be null

Param	Type
node	ForwardNode
mark	ForwardNode

circularSinglyLinkedList.pushFront(value) ⇒ ForwardNode

Push a new node with value value to the front of the list

Param	Type
value	any

circularSinglyLinkedList.pushBack(value) ⇒ ForwardNode

Push a new node with value value to the back of the list

Param	Type
value	any

circularSinglyLinkedList.insertAfter(value, mark) ⇒ ForwardNode | null

Insert a new node with value value immediately after mark

If mark is not an element of the list, the list is not modified

mark must not be null

Param	Type
value	any
mark	ForwardNode

circularSinglyLinkedList.insertBefore(value, mark) ⇒ ForwardNode | null

Insert a new node with value value immediately before mark

If mark is not an element of the list, the list is not modified

mark must not be null

Param	Type
value	any
mark	ForwardNode

circularSinglyLinkedList.pushBackList(other)

Insert a copy of another list at the back of the caller list

The lists may be the same, but must not be null

Param	Type
other	CircularSinglyLinkedList

circularSinglyLinkedList.pushFrontList(other)

Insert a copy of another list at the front of the caller list

The lists may be the same, but must not be null

Param	Type
other	CircularSinglyLinkedList

CircularSinglyLinkedList.create() ⇒ CircularSinglyLinkedList

Instantiate an empty circular singly linked list