@datastructures-js/linked-list

@datastrucures-js/linked-list

a javascript implementation for LinkedList & DoublyLinkedList.

Table of Contents

• Install
• API
  • require
  • import
  • Creating a List
  • .insertFirst(value)
  • .insertLast(value)
  • .insertAt(value, position)
  • .forEach(cb)
  • .forEachReverse(cb)
  • .find(cb)
  • .filter(cb)
  • .toArray()
  • .head()
  • .tail()
  • .count()
  • .removeFirst()
  • .removeLast()
  • .removeAt(position)
  • .removeEach(cb)
  • .clear()
• 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';

Create a list

const linkedList = new LinkedList();

const doublyLinkedList = new DoublyLinkedList();

.insertFirst(value)

inserts a node at the beginning of the list.

runtime	params	return
O(1)	value: {object}	in LinkedList: {LinkedListNode} in DoublyLinkedList: {DoublyLinkedListNode}

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

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

.insertLast(value)

inserts a node at the end of the list.

runtime	params	return
in LinkedList: O(n) in DoublyLinkedList: O(1)	value: {object}	in LinkedList: {LinkedListNde} in DoublyLinkedList: {DoublyLinkedListNode}

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

let last2 = doublyLinkedList.insertLast(3); // last2.getValue() = 3
last2 = doublyLinkedList.insertLast(4); // last2.getValue() = 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.

runtime	params	return
in LinkedList: O(n) in DoublyLinkedList: O(n)	value: {object} position: {number}	in LinkedList: {LinkedListNode} in DoublyLinkedList: {DoublyLinkedListNode}

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.

runtime	params
O(n)	cb: {function(node)}

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.

runtime	params
O(n)	cb: {function(node)}

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

.find(cb)

returns the first node that returns true from the callback.

runtime	params	return
O(n)	cb: {function(node)}	in LinkedList: {LinkedListNode} in DoublyLinkedList: {DoublyLinkedListNode}

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.

runtime	params	return
O(n)	cb: {function(node)}	in LinkedList: {LinkedList} in DoublyLinkedList: {DoublyLinkedList}

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.

runtime	return
O(n)	{array}

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

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

.head()

returns the head node in the linked list.

runtime	return
O(1)	in LinkedList: {LinkedListNode} in DoublyLinkedList: {DoublyLinkedListNode}

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

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

.tail()

Only in DoublyLinkedList. returns the tail node in the doubly linked list

runtime	return
O(1)	{DoublyLinkedListNode}

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

.count()

returns the number of nodes in the linked list.

runtime	return
O(1)	{number}

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

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

.removeFirst()

removes the first (head) node of the list.

runtime	return
O(1)	{boolean}

linkedList.removeFirst(); // true

doublyLinkedList.removeFirst(); // true

.removeLast()

removes the last node from the list.

runtime	return
in LinkedList: O(n) in DoublyLinkedList: O(1)	{boolean}

linkedList.removeLast(); // true

doublyLinkedList.removeLast(); // true

.removeAt(position)

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

runtime	params	return
O(n)	position: {number}	{boolean}

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.

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

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)

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

Build

grunt build

License

The MIT License. Full License is here

Changelog

[2.0.0] - 2020-03-22

Changed

• New release for LinkedList & DoublyLinkedList