Linked List

ES6 Linked List for NodeJS

A Linked List, is a collection of elements whose order / sequence is not determined by physical placement in memory, but rather by each element which points to either the next or previous element.

Table of contents

• Linked List
  • Installation Instructions
  • API
    • LinkedList
      • Parameters
      • clear
      • length
      • setHead
        • Parameters
      • getHead
      • setTail
        • Parameters
      • getTail
      • prepend
        • Parameters
        • Examples
      • prependAll
        • Parameters
      • append
        • Parameters
        • Examples
      • appendAll
        • Parameters
        • Examples
      • forward
        • Examples
      • reverse
        • Examples
      • find
        • Parameters
        • Examples
    • LinkedList~LinkedListPredicate
      • Parameters
    • LinkedList~SurroundingNodes
      • Properties
    • Node~NodeOption
      • Properties
    • Node
      • Parameters
      • getData
      • setData
        • Parameters
      • getNext
      • setNext
        • Parameters
      • getPrev
      • setPrev
        • Parameters
  • Example Usage
  • Deployment Steps
  • License

Installation Instructions

npm install @psenger/linked-list --save

or

yarn add @psenger/linked-list

API

LinkedList

Linked List - Constructed with either a Data Object ( which will be wrapped with a Node ) or a Node with data in it already. Alternatively, you can construct the Linked List with no parameters.

Parameters

• data (Node | Object | undefined | null) Node, an Object as the data, undefined or null. (optional, default null)

clear

Clear all out the values. Resetting the Linked List.

length

Determine the length of the linked List. The Linked List can be altered by means outside the control of the LinkedList Object, thereby bypassing the any functions on this object. Therefore, the length is calculated by iterating over every value in the list. Which can be expensive to execute if the list is large.

Returns number the length

setHead

Set the head, to either a new value, which will be encapsulated as a new Node, or by passing a Node. Either way, the Node's next and previous values will be modified and the value or node that is passed becomes the new head. Consequently, passing either null or undefined, will result in clearing the entire linked list.

Parameters

• newHead (Object | Node | null | undefined) the new head, supporting either a Node, or data.

getHead

Get the Head of this Linked List.

Returns (null | Node) The head, or null.

setTail

Set the tail, to either a new value, which will be encapsulated as a new Node, or a pass a Node. Either way, the Node's next and previous values will be modified and the value or node that is passed becomes the new tail. Consequently, passing either null or undefined, will result in clearing the entire linked list.

Parameters

• newTail (Object | Node | null | undefined) the new tail, supporting either a Node, or data.

getTail

get the Tail of this Linked List

Returns (null | Node) The tail, or null.

prepend

Prepend a new Node or Data to the head. Warning, passing null will clear the Linked List.

Parameters

• data (Object | Node | null | undefined) passing either a Node or data, null will reset the Linked List.

Examples

const ll = new LinkedList();
const nn = new Node();
nn.setData('C')
ll.prepend('A').prepend(new Node({data:'B'})).prepend(nn)
for ( let node of ll.forward ) {
  console.log(node.getData());
}
console.log( 'length =', ll.getSize() );
ll.append( null )
console.log( 'length =', ll.getSize() );
> C
> B
> A
> length = 3
> length = 0

Returns LinkedList A reference to this object allowing chaining.

prependAll

Prepend all the values from left to right of the iterator passed in.

Parameters

• values Iterable Iterable values to prepend to the tail, can be either data or a Node

Returns LinkedList A reference to this object allowing chaining.

append

Append a new Node or Data to the tail. Warning, passing null will clear the Linked List.

Parameters

• data (Object | Node | null | undefined) passing either a Node or data, null will reset the Linked List.

Examples

const ll = new LinkedList();
const nn = new Node();
nn.setData('C')
ll.append('A').append(new Node({data:'B'})).append(nn)
for ( let node of ll.forward ) {
   console.log(node.getData());
}
console.log( 'length =', ll.getSize() );
ll.append( null )
console.log( 'length =', ll.getSize() );
> A
> B
> C
> length = 3
> length = 0

Returns LinkedList A reference to this object allowing chaining.

appendAll

Append all the values from left to right of the iterator passed in.

Parameters

• values Iterable Iterable values to append to the beginning, can be either data or a Node

Examples

const ll = new LinkedList();
const nn = new Node();
nn.setData('C')
ll
.appendAll([
  'A',
  new Node({data: 'B'})
])
.appendAll([
  nn
])
for (let node of ll.forward) {
  console.log(' > ', node.getData());
}
> A
> B
> C

Returns LinkedList A reference to this object allowing chaining.

forward

A Forward iterator through the Linked List

Examples

let ll = new LinkedList();
ll.appendAll(['A','B','E','F'])
for ( let node of ll.reverse ) {
   console.log(node.getData());
}
> F
> E
> B
> A
ll.clear();
ll.appendAll([1,2,3,4])
const y = Array.from( ll.forward, node => node.getData() ).filter( v => v % 2 === 0 )
console.log(y);
> [ 2, 4 ]

reverse

A Reverse iterator through the Linked List

Examples

const ll = new LinkedList();
ll.appendAll(['A','B','E','F'])
for ( let node of ll.reverse ) {
   console.log(node.getData());
}
> F
> E
> B
> A
ll.clear();
ll.appendAll([1,2,3,4])
const y = Array.from( ll.reverse, node => node.getData() ).filter( v => v % 2 === 0 )
console.log(y);
> [ 4, 2 ]

find

Find provides a call back that can be used to select nodes from the Linked List.

Parameters

• predicate LinkedList~LinkedListPredicate

• options Object (optional, default {iterator:this.forward,once:true})

  • options.iterator Iterator The iterator to use, defaults to forward. (optional, default this.forward)
  • options.once Boolean Indicates if the iteration is to halt if found once. (optional, default true)

Examples

const ll = new LinkedList();
const evenCallBack = (cn,pn,nn,iteration,hitCount,linkedList) => cn.getData() % 2 === 0;
ll.appendAll([1,2,3,4])
const results = ll.find(evenCallBack,{once:false}).map(({currentNode})=>currentNode?.getData());
console.log('Even values=', results);
// Even values= [ 2, 4 ]
ll.clear();
const findIt = (value) => (cn,pn,nn,iteration,hitCount,linkedList) => cn.getData() === value;
ll.appendAll(['A','B', 'C','D']) // insert Z between B and C
const [ { previousNode, currentNode, nextNode } ] = ll.find(findIt('B'),{once:true});
console.log('previousNode', previousNode?.getData());
// previousNode A
console.log('currentNode', currentNode?.getData());
// currentNode B
console.log('nextNode', nextNode?.getData());
// nextNode C
const newNode = new Node();
newNode.setData('Z');
currentNode?.setNext( newNode );
nextNode?.setPrev( newNode );
newNode.setPrev( currentNode );
newNode.setNext( nextNode );
console.log('---- Forward ----');
for ( let node of ll.forward ) {
   console.log(node.getData());
}
// ---- Forward ----
// A
// B
// Z
// C
// D
console.log('---- Reverse ----');
for ( let node of ll.reverse ) {
   console.log(node.getData());
}
// ---- Reverse ----
// D
// C
// Z
// B
// A

Returns Array<LinkedList~SurroundingNodes> matching nodes

LinkedList~LinkedListPredicate

Callback, used by find to predicate nodes, in the Linked List.

Type: Function

Parameters

• currentNode (null | Node) The current Node
• previousNode (null | Node) The previous Node
• nextNode (null | Node) The next Node
• iteration number Iteration number
• hitCount number A running count of all the evaluated predicates that matched true.
• scope LinkedList The LinkedList Object.

Returns boolean true indicates a match and will collect matching node(s)

LinkedList~SurroundingNodes

Type: Object

Properties

• previousNode (null | Node) previous node
• currentNode (null | Node) current node
• nextNode (null | Node) next node

Node~NodeOption

A Node constructor option object

Type: Object

Properties

• data (Object | null) Any kind of data you want to store.
• next (Node | null) Next node
• prev (Node | null) Previous node

Node

Node, the internal class used within the linked list to assist in linking elements.

Parameters

• props Node~NodeOption the Options to pass to the constructor (optional, default {data:null,next:null,prev:null})

  • props.data (Object | null) the data to store (optional, default null)
  • props.next (Node | null) the next node, or null (optional, default null)
  • props.prev (Node | null) the previous node, or null (optional, default null)

getData

Get the data from this node, which can be what ever you want.

Returns (any | null) the data stored here.

setData

Set the data in this node.

Parameters

• data (any | null) the data to store.

getNext

Get the next node, null indicates that it is the end.

Returns (Node | null) the next node.

setNext

Set the next node, null indicates the end.

Parameters

• node (Node | null) the next node.

getPrev

Get the previous node. The value null indicate the end has been reached.

Returns (Node | null) the previous node.

setPrev

Set the previous node, null indicates the end.

Parameters

• node (Node | null) the previous node.

Example Usage

const LinkedList = require('./LinkedList');

const ll = new LinkedList();
ll.append('A').append('B').append('C')
for (let node of ll.forward) {
  console.log(node.getData());
}
console.log('head=',ll.getHead().getData());
console.log('tail=',ll.getTail().getData());

Deployment Steps

These are notes for deploying to NPM. I used npmrc to manage my NPM identities (npm i npmrc -g to install ). Then I created a new profile called public with (npmrc -c public) and then switch to it with npmrc public.

• create a pull request from dev to main
• check out main
• npm version patch -m "message here" or minor
• npm publish --access public
• Then switch to dev branch
• And then merge main into dev and push dev to origin

License

MIT License

Copyright (c) 2021 Philip A Senger

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

MIT © psenger