@datastructures-js/linked-list

@datastrucures-js/linked-list

a javascript implementation of LinkedList & DoublyLinkedList.

Linked List
Doubly Linked List

Table of Contents

• Install
• require
• import
• API
  • Construction
  • .insertFirst(value)
  • .insertLast(value)
  • .insertAt(value, position)
  • .forEach(cb)
  • .forEachReverse(cb)
  • .find(cb)
  • .filter(cb)
  • .toArray()
  • .isEmpty()
  • .head()
  • .tail()
  • .count()
  • .removeFirst()
  • .removeLast()
  • .removeAt(position)
  • .removeEach(cb)
  • .clear()
  • LinkedListNode
  • DoublyLinkedListNode
• Build
• License

install

npm install --save @datastructures-js/linked-list

require

const {
  LinkedListNode,
  LinkedList,
  DoublyLinkedListNode,
  DoublyLinkedList,
} = require('@datastructures-js/linked-list');

import

import {
  LinkedListNode,
  LinkedList,
  DoublyLinkedListNode,
  DoublyLinkedList
} from '@datastructures-js/linked-list';

API

Construction

const linkedList = new LinkedList();

const doublyLinkedList = new DoublyLinkedList();

.insertFirst(value)

inserts a node at the beginning of the list.

params	return	runtime
value: any	LinkedList | DoublyLinkedList	O(1)

console.log(linkedList.insertFirst(2).head().getValue()); // 2

console.log(linkedList.insertFirst(1).head().getValue()); // 1

.insertLast(value)

inserts a node at the end of the list.

params	return	runtime
value: any	LinkedList | DoublyLinkedList	LinkedList: O(n) DoublyLinkedList: O(1)

linkedList.insertLast(3);
const last1 = linkedList.insertLast(4).find(4);
console.log(last1.getValue()); // 4
console.log(last1.getNext()); // null

doublyLinkedList.insertLast(3);
const last2 = doublyLinkedList.insertLast(4).find(4);
console.log(last2.getValue()); // 4
console.log(last2.getPrev().getValue()); // 3

.insertAt(position, value)

inserts a node at specific position of the list. First (head) node is at position 0.

params	return	runtime
position: number value: any	LinkedList | DoublyLinkedList	O(n)

const node1 = linkedList.insertAt(2, 5).find(5); // node1.getValue() = 5

const node2 = doublyLinkedList.insertAt(2, 5).find(5); // node2.getValue() = 5

.forEach(cb)

Loop on the linked list from beginning to end, and pass each node to the callback.

params	runtime
cb: function	O(n)

linkedList.forEach((node, position) => console.log(node.getValue(), position));
/*
2 0
1 1
5 2
3 3
4 4
*/

doublyLinkedList.forEach((node, position) => console.log(node.getValue(), position));
/*
2 0
1 1
5 2
3 3
4 4
*/

.forEachReverse(cb)

Only in DoublyLinkedList. Loop on the doubly linked list from end to beginning, and pass each node to the callback.

params	runtime
cb: function	O(n)

doublyLinkedList.forEachReverse((node, position) => console.log(node.getValue(), position));
/*
4 4
3 3
5 2
1 1
2 0
*/

.find(cb)

returns the first node that return true from the callback or null if nothing found.

params	return	runtime
cb: function	LinkedListNode | DoublyLinkedListNode	O(n)

const node1 = linkedList.find((node) => node.getValue() === 5);
console.log(node1.getValue()); // 5
console.log(node1.getNext().getValue()); // 3

const node2 = doublyLinkedList.find((node) => node.getValue() === 5);
console.log(node2.getValue()); // 5
console.log(node2.getNext().getValue()); // 3
console.log(node2.getPrev().getValue()); // 1

.filter(cb)

returns a filtered linked list of all the nodes that returns true from the callback.

params	return	runtime
cb: function	LinkedList | DoublyLinkedList	O(n)

const filterLinkedList = linkedList.filter((node, position) => node.getValue() > 2);
filterLinkedList.forEach((node) => console.log(node.getValue()));
/*
5
3
4
*/

const filteredDoublyLinkedList = doublyLinkedList.filter((node, position) => node.getValue() > 2);
filteredDoublyLinkedList.forEach((node) => console.log(node.getValue()));
/*
5
3
4
*/

.toArray()

converts the linked list into an array.

return	runtime
array	O(n)

console.log(linkedList.toArray()); // [2, 1, 5, 3, 4]

console.log(doublyLinkedList.toArray()); // [2, 1, 5, 3, 4]

.isEmpty()

checks if the linked list is empty.

return	runtime
boolean	O(1)

console.log(linkedList.isEmpty()); // false

console.log(doublyLinkedList.isEmpty()); // false

.head()

returns the head node in the linked list.

return	runtime
LinkedListNode | DoublyLinkedListNode	O(1)

console.log(linkedList.head().getValue()); // 2

console.log(doublyLinkedList.head().getValue()); // 2

.tail()

returns the tail node of the doubly linked list.

return	runtime
DoublyLinkedListNode	O(1)

console.log(doublyLinkedList.tail().getValue()); // 4

.count()

returns the number of nodes in the linked list.

return	runtime
number	O(1)

console.log(linkedList.count()); // 5

console.log(doublyLinkedList.count()); // 5

.removeFirst()

removes the first node in the list.

return	runtime
boolean	O(1)

linkedList.removeFirst(); // true

doublyLinkedList.removeFirst(); // true

.removeLast()

removes the last node in the list.

return	runtime
boolean	LinkedList: O(n) DoublyLinkedList: O(1)

linkedList.removeLast(); // true

doublyLinkedList.removeLast(); // true

.removeAt(position)

removes a node at a specific position. First (head) node is at position 0.

params	return	runtime
position: number	boolean	O(1)

linkedList.removeAt(1); // true

doublyLinkedList.removeAt(1); // true

.removeEach(cb)

Loop on the linked list from beginning to end, removes the nodes that returns true from the callback.

params	return	runtime
cb: function	number (number of removed nodes)	O(n)

linkedList.removeEach((node, position) => node.getValue() > 1); // 1
console.log(linkedList.toArray()); // [1]

doublyLinkedList.removeEach((node, position) => node.getValue() > 1); // 1
console.log(doublyLinkedList.toArray()); // [1]

.clear()

clears the linked list.

runtime
O(1)

linkedList.clear();
console.log(linkedList.count()); // 0
console.log(linkedList.head()); // null

doublyLinkedList.clear();
console.log(linkedList.count()); // 0
console.log(doublyLinkedList.head()); // null
console.log(doublyLinkedList.tail()); // null

LinkedListNode

.setValue(value)

sets the node's value.

params
value: any

.getValue()

returns the node's value.

return
any

.setNext(next)

sets the node's next connected node.

params
next: LinkedListNode

.getNext()

returns the next connected node or null if it's the last node.

return
LinkedListNode

DoublyLinkedListNode

.setValue(value)

sets the node's value.

params
value: any

.getValue()

returns the node's value.

return
any

.setPrev(prev)

sets the node's previous connected node.

params
prev: DoublyLinkedListNode

.getPrev()

returns the previous connected node or null if it's the first node.

return
DoublyLinkedListNode

.setNext(next)

sets the node's next connected node.

params
next: DoublyLinkedListNode

.getNext()

returns the next connected node or null if it's the last node.

return
DoublyLinkedListNode

Build

grunt build

License

The MIT License. Full License is here

Changelog

[3.0.0] - 2020-12-30

Changed

• .insertAt(position, value) position now comes first then value.
• .insert* methods now returns a this reference so it can be chained.
• .forEach(cb) callback now gets called with node and position (starting from 0);
• .forEachReverse(cb) callback now gets called with node and position (starting from size -1);
• LinkedListNode & DoublyLinkedListNode classes are now exported in index.

Fixed

• jsdoc
• readme