digital-chain

A linked list implementation

API

Table of Contents

• LinkedList
  • length
  • push
    • Parameters
  • pushAll
    • Parameters
  • pop
  • unshift
    • Parameters
  • unshiftAll
    • Parameters
  • shift
  • remove
    • Parameters
  • swap
    • Parameters
  • sort
    • Parameters
  • nodes
  • values
  • iterator
  • iterator
  • reverseIterator
  • findFirst
    • Parameters
  • findAll
    • Parameters
  • findFirstBy
    • Parameters
  • findAllBy
    • Parameters
  • nodeIterator
• EntryIterator
  • Parameters
• ValueIterator
  • Parameters
• NodeIterator
  • Parameters
• ListNode
  • Parameters

LinkedList

a doubly linked list

length

returns the current length of the list

push

push an item to the tail of this list

Parameters

• item Variant any kind of item can be pushed

Returns ListNode the node wrapping the item, nodes can be used in methods such as remove()

pushAll

push all the items at the tail of the list the following are equivalent:

list.pushAll(1, 2, 3)
list.pushAll([1, 2], 3)
list.pushAll([1, 2, 3])

to push an array as a single item use .push(arr)

Parameters

• args ...[Variant] an array or just arguments to be pushed to the list

Returns Array<ListNode>

pop

remove the tail of this list, if the list has more than 1 node in it, the previous node will become the new tail of the list

Returns Variant the data from the removed tail node or undefined if the list was empty

unshift

insert an item at the head of this list

Parameters

• item Variant any kind of item can be inserted

Returns ListNode

unshiftAll

insert all the items at the head of the list the following are all equivalent:

   list.unshiftAll(1, 2, 3)
   list.unshiftAll([1, 2], 3)
   list.unshiftAll([1, 2, 3])

to push an array as a single item use .push(arr)

Parameters

• args ...[Variant] an array or just arguments to be pushed to the list

Returns Array<ListNode>

shift

remove the head of this list, if the list has more than 1 node in it, the next node will become the new head of the list

Returns Variant the data from the removed head node or undefined if the list was empty

remove

Remove a node from the list

Parameters

• node ListNode the node to remove

Returns Variant the data contained in the removed node

swap

swap the positions of node A and node B inside the list

this method will throw an error if one or more of the arguments is not a Node or not a member of this list

Parameters

• nodeA ListNode
• nodeB ListNode

Returns Boolean returns true if a swap did occur

sort

sort the list

the default sorting comparator is:

function defaultComparator(a, b) {
 if (b > a) return -1
 if (b < a) return 1
 
 return 0
}

Parameters

• comparator function (Node, Node)? override the default comparator with a custom one.

nodes

An ES6 iterator of the nodes in this list, starting from the head

for (let node of list.nodes()) {
	console.log(node.data, node.next)
}

Returns NodeIterator

values

An ES6 iterator of the values in this list, starting from the head

for (let value of list.values()) {
	console.log(value)
}

Returns ValueIterator

iterator

An ES6 iterator of the value and nodes in this list, starting from the head

for (let [data, node] of list) {
	console.log(data === node.data)
}

Returns EntryIterator

iterator

A functional iterator over the values in the list, prefer the new ES6 iteration methods over this

reverseIterator

An ES6 iterator of the value and nodes in this list, starting from the tail

Returns EntryIterator

findFirst

find the first occurrence of this piece of data in the list, equality test is performed using ===

Parameters

• data Variant data to find

Returns ListNode the first node that contains this data

findAll

find all the occurrences of this piece of data in the list, equality test is performed using === this will traverse the entire list

Parameters

• data Variant data to find

Returns Array<ListNode> an array of nodes that contain this data

findFirstBy

finds the first node in the list where the predicate function returns true

Parameters

• predicate function (Variant) a function that returns true for nodes that should be included in the search results

Returns ListNode the first node that was found

findAllBy

finds the all the nodes in the list where the predicate function returns true

Parameters

• predicate function (Variant) a function that returns true for nodes that should be included in the search results

Returns Array<ListNode> an array of nodes that were found

nodeIterator

A functional iterator over the nodes in the list, prefer the new ES6 iteration methods over this

EntryIterator

Implements iteration over the list's entries (pairs of value + it's hosting node). This iterator is the only iterator that can change it's direction, the others are provided for convenience and only iterate from head to tail.

const list = new LinkedList()
 	
// iterate from head to tail
for (const [value, node] of list) { ... } 		

// iterate from tail to head
for (const [value, node] of list.reverseIterator()) { ... } 		

Parameters

• list
• direction

ValueIterator

Extends EntryIterator

Implements iteration over the list's values.

 const list = new LinkedList()
 	
 // iterate from head to tail
 for (const value of list.values()) { ... } 		

Parameters

• list

NodeIterator

Extends EntryIterator

Implements iteration over the list's nodes.

 const list = new LinkedList()
 	
 // iterate from head to tail
 for (const node of list.nodes()) { ... } 		

Parameters

• list

ListNode

a node in the list

Parameters

• data
• parent

Extension

This implemenation uses several internal classes for iteration and for "hosting" values.

EntryIterator, ValueIterator, NodeIterator and ListNode

These classes can be customized via inheritance:

const LinkedList = require('digital-chain')

class MyEntryIterator extends LinkedList.EntryIterator {}
class MyValueIterator extends LinkedList.ValueIterator {}
class MyNodeIterator extends LinkedList.NodeIterator {}
class MyListNode extends LinkedList.ListNode {}

These new classes can then be incorporated into the linked list's by overriding their respective factory methods:

class MyLinkedList extends LinkedList {
    _newEntryIterator(list, direction) {
        return new MyEntryIterator(list, direction) // direction constants are LinkedList.FROM_HEAD or LinkedList.FROM_TAIL
    }

    _newValueIterator(list) {
        return new MyValueIterator(list)
    }

    _newNodeIterator(list) {
        return new MyNodeIterator(list)
    }

    _newListNode(data, parent) {
        return new MyListNode(data, parent)
    }
}

// of course this can also be done to an existing instance:

const customList = new LinkedList()
customList._newEntryIterator = (list, direction) => new MyEntryIterator(list, direction)

docs

documentation readme index.js --section=API