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.
| Linked List |
|
| Doubly Linked List |
|
Table of Contents
install
npm install --save @datastructures-js/linked-listrequire
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()); // nullLinkedListNode
.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 buildLicense
The MIT License. Full License is here