js-doublelinkedlist

JS DoubleLinkedList implementation

Install

$ npm install --save js-doublelinkedlist

Usage

import myModule from 'js-doublelinkedlist'

const list = new DoubleLinkedList()
list.add('data1');
list.add('data2');
list.pop().data === data2 // true
list.pop().data === data1 // true

API

Table of Contents

• Node
• DoubleLinkedList
  • first
  • last
  • ladd
  • lpop
  • removeFirst
  • radd
  • add
  • pop
  • rpop
  • removeLast
  • getAt
  • getDataAt
  • removeData
  • remove
  • removeAt
  • forEach
  • hasNode
  • has
  • empty
  • reset
  • swapDataAt
  • swapAt
  • swapData
  • swapData
  • swap
  • swapNodes
  • isNode
  • getDefaultNodeClass
  • getNodeClass

Node

Node element of our double linked list Contains a left pointer & right pointer as well as data property TODO: have a more consistent API (eg consistent return values & consitent names depending on return values being nodes or data)

Parameters

• data any data stored in the node that can be retrieved through linked list method
• $1 Object (optional, default {})
  • $1.left (optional, default null)
  • $1.right (optional, default null)
• pointers Object pointers object containing reference to left and right nodes (optional, default {})

DoubleLinkedList

DoubleLinkedList class adding node(radd, ladd): O(1) list length retrieval: O(1) - (unless lists' nodes modified outside of class) getting/removing nodes or nodes' data apart from head/tail (getAt, getDataAt, removeAt, find, findData...): O(n)

Parameters

• head (Node | Array<Node>) optional reference to head node (optional, default null)
• $1 Object (optional, default {})
  • $1.NodeClass (optional, default Node)
• param Object optional parameter object (optional, default {})

first

Gets the head of the list

Returns Node head (most left node) of the list

last

Gets the tail of the list

Returns Node tail (most right node) of the list

ladd

Add data to the left of the list Passed data is added into a new node which becomes the head of the list

Parameters

• data any
• otherDatas ...any
• optional ...any further datas to add. ladd will be called for each further data passed.

Returns Node new head (most left member) of the list

lpop

pops head (most left member) of the list The list's 2nd element (if exists) becomes the new head of the list since returned most left node is removed from list

Returns Node poped node

removeFirst

Remove first member (head) of the list alias to {link DoubleLinkedList~lpop}

Returns Node removed node

radd

Add data to the right of the list Passed data is added into a new node which becomes the tail of the list

Parameters

• data any
• otherDatas ...any
• optional ...any further datas to add. radd will be called for each further data passed.

Returns Node new tail (most right) node of the list

add

Sets passed data(s) into a new node and adds node to the right of the list alias to {link DoubleLinkedList~radd}

Parameters

• datas ...any
• data any (s) to be stored into the new node

Returns Node

pop

pop last member in the list alias to {link DoubleLinkedList~rpop}

Returns Node poped node

rpop

pops head (most right member) of the list The list's next to last node (if exists) becomes the new tail of the list since returned most right node is removed from list

Returns Node poped tail node

removeLast

Remove last member (tail) of the list alias to {link DoubleLinkedList~rpop}

Returns Node removed node

getAt

Retrieves the Node placed at specified index in the List Considering the list as an array with the head as the first element and tail its last, index 0 would return the head and index length - 1 would return the tail node

Parameters

• index any index within the list at which node should be retrieved

Returns Node node located at specified index. null if index is invalid

getDataAt

Retrieves the data of the node placed at specified index in the List see {link DoubleLinkedList~getAt} for retrieval of the node itself and not just its data

Parameters

• index any index within the list at which node data should be retrieved

Returns any data stored in the node placed at specified index

removeData

Removes any node in the list that contains the specified data Only removes in case of strict equality with specified data. See {link DoubleLinkedList~filterData}

Parameters

• data any

Returns Array<Node> array of the nodes removed from the list because their data matched method's data parameter

remove

Remove specified node within the list (if that node is indeed in the list)

Parameters

• node Node node to remove

removeAt

Remove the node at specified index in the list

Parameters

• index Number of the node to remove

forEach

execute fn callback on each node (same behaviour as Array.prototype.forEach)

Parameters

• fn function function that will be called for each node in the list

hasNode

Check if list contains a specific node

Parameters

• node
• data any

Returns Boolean true or false

has

Check if list contains specific data

Parameters

• data any

Returns Boolean true or false

empty

Empties the list (resets the head & tail to null and length to 0)

reset

recalculate the length of the linked list and re-set the tail (loops from the left to do this therefore) this normaly isn't necessary unless list's nodes left/right pointers were modified without using the DoubleLinkedList available methods

Returns Number difference between old length and recalculated length (negative number means new length > old length)

swapDataAt

swap nodes' data at indices indexa & indexb

Parameters

• indexa number
• indexb number

swapAt

swap nodes at indices indexa & indexb

Parameters

• indexa number
• indexb number

swapData

Swap two nodes' data within the list assigns each nodes' data property to the other one's

Parameters

• a Node node to swap
• b Node node to swap

swapData

Swap two nodes' data assigns each nodes' data property to the other one's

Parameters

• a Node node to swap
• b Node node to swap

swap

Swap two nodes' within the list basically swaps their respective left & right reference

Parameters

• a Node node to swap
• b Node node to swap

swapNodes

Swap two nodes basically swaps their respective left & right reference

Parameters

• a Node node to swap
• b Node node to swap

isNode

Returns whether or not the passed object can be considered a Node (has a right and left property)

Parameters

• obj Object Node object to be checked

Returns Boolean true or false

getDefaultNodeClass

Returns the default Node class used when adding new data into the list

Returns Node default node class

getNodeClass

Gets the Node class used in this DoubleLinkedList instance (defaulted to ${link Node~constructor} in the constructor)

Returns Class node class used in this instance

License

MIT © Guillaume Lebedel