@datastructures-js/linked-list

@datastrucures-js/linked-list

a javascript implementation of LinkedList & DoublyLinkedList.

Linked List
Doubly Linked List

Table of Contents

• Install
• API
  • require
  • import
  • 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

API

require

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

import

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

Construction

Example

const linkedList = new LinkedList();

const doublyLinkedList = new DoublyLinkedList();

.insertFirst(value)

inserts a node at the beginning of the list.

params
name	type
value	object

return	decsription
LinkedList	LinkedListNode	the inserted node
DoublyLinkedList	DoublyLinkedListNode

runtime
O(1)

Example

linkedList.insertFirst(1);
const head1 = linkedList.insertFirst(2);
console.log(head1.getValue()); // 2

doublyLinkedList.insertFirst(1);
const head2 = doublyLinkedList.insertFirst(2);
console.log(head2.getValue()); // 2

.insertLast(value)

inserts a node at the end of the list.

params
name	type
value	object

return	decsription
LinkedList	LinkedListNode	the inserted node
DoublyLinkedList	DoublyLinkedListNode

runtime
LinkedList	O(n)
DoublyLinkedList	O(1)

Example

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

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

.insertAt(value, position)

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

params
name	type
value	object
position	number

return	description
LinkedList	LinkedListNode	the inserted node
DoublyLinkedList	DoublyLinkedListNode

runtime
O(n)

Example

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

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

.forEach(cb)

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

params
name	type
cb	function

runtime
O(n)

Example

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

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

.forEachReverse(cb)

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

params
name	type
cb	function

runtime
O(n)

Example

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

.find(cb)

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

params
name	type
cb	function

return	description
LinkedList	LinkedListNode	the first found node
DoublyLinkedList	DoublyLinkedListNode

runtime
O(n)

Example

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 list of all the nodes that returns true from the callback.

params
name	type
cb	function

return
LinkedList	LinkedListNode
DoublyLinkedList	DoublyLinkedListNode

runtime
O(n)

Example

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

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

.toArray()

converts the linked list into an array.

return
array

runtime
O(n)

Example

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
boolean

runtime
O(1)

Example

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

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

.head()

returns the head node in the linked list.

return
LinkedList	LinkedListNode
DoublyLinkedList	DoublyLinkedListNode

runtime
O(1)

Example

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

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

.tail()

returns the tail node of the doubly linked list.

return
DoublyLinkedListNode

runtime
O(1)

Example

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

.count()

returns the number of nodes in the linked list.

return
number

runtime
O(1)

Example

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

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

.removeFirst()

removes the first (head) node of the list.

return	description
boolean	true if a node has been removed

runtime
O(1)

Example

linkedList.removeFirst(); // true

doublyLinkedList.removeFirst(); // true

.removeLast()

removes the last node from the list.

return	description
boolean	true if a node has been removed

runtime
LinkedList	O(n)
DoublyLinkedList	O(1)

Example

linkedList.removeLast(); // true

doublyLinkedList.removeLast(); // true

.removeAt(position)

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

params
name	type
position	number

return	description
boolean	true if a node has been removed

runtime
O(n)

Example

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
name	type
cb	function

return	description
number	number of removed nodes

runtime
O(n)

Example

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

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

.clear()

remove all nodes in the linked list.

runtime
O(1)

Example

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

.getValue()

returns the node's value.

return
object

.getNext()

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

return
LinkedListNode

DoublyLinkedListNode

.getValue()

returns the node's value.

return
object

.getPrev()

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

return
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

[2.0.3] - 2020-04-04

Added

.isEmpty() method for LinkedList & DoublyLinkedList.

Fixed

• README & jsdocs