Package Exports

@datastructures-js/linked-list

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (@datastructures-js/linked-list) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

@datastrucures-js/linked-list

a javascript implementation of LinkedList & DoublyLinkedList.

Install
API
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}

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.

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

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.

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

@datastructures-js/linked-list