Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

@datastructures-js/linked-list

Package Overview
Dependencies
Maintainers
1
Versions
28
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

@datastructures-js/linked-list - npm Package Compare versions

Comparing version 4.0.0 to 5.0.0

DoublyLinkedList.md
LinkedList.md

13

CHANGELOG.md

@@ -8,3 +8,16 @@ # Changelog

## [Unreleased]
## [5.0.0] - 2021-04-12
### Changed
- insert/remove methods now all returns the inserted/removed nodes.
- `insertLast` in LinkedList now accepts a starting node as a second param, useful to insert a node at the end in O(1) runtime.
### Added
- `remove(node)` to DoublyLinkedList to remove any node in O(1) runtime.
- `hasNext`/`hasPrev` cleaner checks of connected nodes to Node classes.
### Fixed
- bug in removeEach method.
- improved README, splitted LinkedList/DoublyLinkedList readmes.
## [4.0.0] - 2021-02-16

@@ -11,0 +24,0 @@

2

package.json
{
"name": "@datastructures-js/linked-list",
"version": "4.0.0",
"version": "5.0.0",
"description": "a javascript implementation of LinkedList & DoublyLinkedList",

@@ -5,0 +5,0 @@ "main": "index.js",

672

README.md

@@ -9,674 +9,10 @@ # @datastrucures-js/linked-list

<table>
<tr>
<td><b>Linked List</b></td>
<td>
## [LinkedList](https://github.com/datastructures-js/linked-list/blob/development/LinkedList.md)
<img width="429" alt="Linked List" src="https://user-images.githubusercontent.com/6517308/35762715-5d00c9bc-0861-11e8-88f7-6e503a1fa3af.png">
</td>
</tr>
<tr>
<td><b>Doubly Linked List</b></td>
<td>
<img width="552" alt="Doubly Linked List" src="https://user-images.githubusercontent.com/6517308/35762752-19b17df4-0862-11e8-8ce3-f940d83dde51.png">
</td>
</tr>
</table>
# Table of Contents
* [Install](#install)
* [require](#require)
* [import](#import)
* [API](#api)
* [Construction](#construction)
* [.insertFirst(value)](#insertfirstvalue)
* [.insertLast(value)](#insertlastvalue)
* [.insertAt(position, value)](#insertatposition-value)
* [.forEach(cb)](#foreachcb)
* [.forEachReverse(cb)](#foreachreversecb)
* [.find(cb)](#findcb)
* [.filter(cb)](#filtercb)
* [.toArray()](#toarray)
* [.isEmpty()](#isempty)
* [.head()](#head)
* [.tail()](#tail)
* [.count()](#count)
* [.removeFirst()](#removefirst)
* [.removeLast()](#removelast)
* [.removeAt(position)](#removeatposition)
* [.removeEach(cb)](#removeeachcb)
* [.clear()](#clear)
* [LinkedListNode](#linkedlistnode)
* [DoublyLinkedListNode](#doublylinkedlistnode)
* [Build](#build)
* [License](#license)
## [DoublyLinkedList](https://github.com/datastructures-js/linked-list/blob/development/DoublyLinkedList.md)
## install
```sh
npm install --save @datastructures-js/linked-list
```
<img width="552" alt="Doubly Linked List" src="https://user-images.githubusercontent.com/6517308/35762752-19b17df4-0862-11e8-8ce3-f940d83dde51.png">
## require
```js
const {
LinkedList,
DoublyLinkedList,
} = require('@datastructures-js/linked-list');
// list node classes are also exported
const {
LinkedListNode,
DoublyLinkedListNode
} = require('@datastructures-js/linked-list');
```
## import
```js
import {
LinkedList,
DoublyLinkedList
} from '@datastructures-js/linked-list';
// list node classes are also exported
import {
LinkedListNode,
DoublyLinkedListNode
} from '@datastructures-js/linked-list';
```
## API
### Construction
```js
const linkedList = new LinkedList();
const doublyLinkedList = new DoublyLinkedList();
```
### .insertFirst(value)
inserts a node at the beginning of the list.
<table>
<tr>
<th align="center">params</th>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">value: any</td>
<td align="center">LinkedList | DoublyLinkedList</td>
<td align="center">O(1)</td>
</tr>
</table>
```js
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.
<table>
<tr>
<th align="center">params</th>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">value: any</td>
<td align="center">LinkedList | DoublyLinkedList</td>
<td>
LinkedList: O(n)
<br />
DoublyLinkedList: O(1)
</td>
</tr>
</table>
```js
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.
<table>
<tr>
<th align="center">params</th>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td>
position: number
<br />
value: any
</td>
<td align="center">LinkedList | DoublyLinkedList</td>
<td align="center">
O(n)
</td>
</tr>
</table>
```js
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.
<table>
<tr>
<th align="center">params</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">
cb: function
</td>
<td align="center">
O(n)
</td>
</tr>
</table>
```js
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.
<table>
<tr>
<th align="center">params</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">
cb: function
</td>
<td align="center">
O(n)
</td>
</tr>
</table>
```js
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.
<table>
<tr>
<th align="center">params</th>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">
cb: function
</td>
<td align="center">
LinkedListNode | DoublyLinkedListNode
</td>
<td align="center">
O(n)
</td>
</tr>
</table>
```js
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.
<table>
<tr>
<th align="center">params</th>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">
cb: function
</td>
<td align="center">
LinkedList | DoublyLinkedList
</td>
<td align="center">
O(n)
</td>
</tr>
</table>
```js
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.
<table>
<tr>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">
array
</td>
<td align="center">
O(n)
</td>
</tr>
</table>
```js
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.
<table>
<tr>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">
boolean
</td>
<td align="center">
O(1)
</td>
</tr>
</table>
```js
console.log(linkedList.isEmpty()); // false
console.log(doublyLinkedList.isEmpty()); // false
```
### .head()
returns the head node in the linked list.
<table>
<tr>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">
LinkedListNode | DoublyLinkedListNode
</td>
<td align="center">
O(1)
</td>
</tr>
</table>
```js
console.log(linkedList.head().getValue()); // 2
console.log(doublyLinkedList.head().getValue()); // 2
```
### .tail()
returns the tail node of the doubly linked list.
<table>
<tr>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">
DoublyLinkedListNode
</td>
<td align="center">
O(1)
</td>
</tr>
</table>
```js
console.log(doublyLinkedList.tail().getValue()); // 4
```
### .count()
returns the number of nodes in the linked list.
<table>
<tr>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">
number
</td>
<td align="center">
O(1)
</td>
</tr>
</table>
```js
console.log(linkedList.count()); // 5
console.log(doublyLinkedList.count()); // 5
```
### .removeFirst()
removes the first node in the list.
<table>
<tr>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">
LinkedListNode | DoublyLinkedListNode
</td>
<td align="center">
O(1)
</td>
</tr>
</table>
```js
linkedList.removeFirst();
doublyLinkedList.removeFirst();
```
### .removeLast()
removes and returns the last node in the list.
<table>
<tr>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">
LinkedListNode | DoublyLinkedListNode
</td>
<td>
LinkedList: O(n)
<br />
DoublyLinkedList: O(1)
</td>
</tr>
</table>
```js
linkedList.removeLast();
doublyLinkedList.removeLast();
```
### .removeAt(position)
removes and returns the node at a specific position. First (head) node is at position 0.
<table>
<tr>
<th align="center">params</th>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">
position: number
</td>
<td align="center">
LinkedListNode | DoublyLinkedListNode
</td>
<td align="center">
O(1)
</td>
</tr>
</table>
```js
linkedList.removeAt(1);
doublyLinkedList.removeAt(1);
```
### .removeEach(cb)
Loop on the linked list from beginning to end, removes the nodes that returns a list of the removed nodes.
<table>
<tr>
<th align="center">params</th>
<th align="center">return</th>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">
cb: function
</td>
<td align="center">
array&lt;LinkedListNode | DoublyLinkedListNode&gt;
</td>
<td align="center">
O(n)
</td>
</tr>
</table>
```js
linkedList.removeEach((node, position) => node.getValue() > 1);
console.log(linkedList.toArray()); // [1]
doublyLinkedList.removeEach((node, position) => node.getValue() > 1);
console.log(doublyLinkedList.toArray()); // [1]
```
### .clear()
clears the linked list.
<table>
<tr>
<th align="center">runtime</th>
</tr>
<tr>
<td align="center">
O(1)
</td>
</tr>
</table>
```js
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
#### new LinkedListNode(value, next)
<table>
<tr><th>params</th></tr>
<tr>
<td>
value: any
<br />
next: LinkedListNode
</td>
</tr>
</table>
#### .setValue(value)
sets the node's value.
<table>
<tr><th>params</th></tr>
<tr><td>value: any</td></tr>
</table>
#### .getValue()
returns the node's value.
<table>
<tr><th>return</th></tr>
<tr><td>any</td></tr>
</table>
#### .setNext(next)
sets the node's next connected node.
<table>
<tr><th align="center">params</th></tr>
<tr><td>next: LinkedListNode</td></tr>
</table>
#### .getNext()
returns the next connected node or null if it's the last node.
<table>
<tr><th>return</th></tr>
<tr><td>LinkedListNode</td></tr>
</table>
### DoublyLinkedListNode
#### new DoublyLinkedListNode(value, prev, next)
<table>
<tr><th>params</th></tr>
<tr>
<td>
value: any
<br />
prev: DoublyLinkedListNode
<br />
next: DoublyLinkedListNode
</td>
</tr>
</table>
#### .setValue(value)
sets the node's value.
<table>
<tr><th>params</th></tr>
<tr><td>value: any</td></tr>
</table>
#### .getValue()
returns the node's value.
<table>
<tr><th>return</th></tr>
<tr><td>any</td></tr>
</table>
#### .setPrev(prev)
sets the node's previous connected node.
<table>
<tr><th>params</th></tr>
<tr><td>prev: DoublyLinkedListNode</td></tr>
</table>
#### .getPrev()
returns the previous connected node or null if it's the first node.
<table>
<tr><th>return</th></tr>
<tr><td>DoublyLinkedListNode</td></tr>
</table>
#### .setNext(next)
sets the node's next connected node.
<table>
<tr><th>params</th></tr>
<tr><td>next: DoublyLinkedListNode</td></tr>
</table>
#### .getNext()
returns the next connected node or null if it's the last node.
<table>
<tr><th>return</th></tr>
<tr><td>DoublyLinkedListNode</td></tr>
</table>
## Build

@@ -683,0 +19,0 @@ ```

200

src/doublyLinkedList.js
/**
* datastructures-js/linked-list
* @license MIT

@@ -12,5 +13,2 @@ * @copyright 2020 Eyas Ranjous <eyas.ranjous@gmail.com>

class DoublyLinkedList {
/**
* Creates a doubly linked list.
*/
constructor() {

@@ -23,6 +21,6 @@ this._head = null;

/**
* Adds a node at the beginning of the linked list.
* Adds a node at the beginning of the list.
* @public
* @param {any} value
* @returns {DoublyLinkedList} - reference to this
* @returns {DoublyLinkedListNode}
*/

@@ -40,12 +38,11 @@ insertFirst(value) {

}
this._count += 1;
return this;
return newNode;
}
/**
* Adds a node at the end of the linked list.
* Adds a node at the end of the list.
* @public
* @param {any} value
* @returns {DoublyLinkedList} - reference to this
* @returns {DoublyLinkedListNode}
*/

@@ -63,3 +60,3 @@ insertLast(value) {

this._count += 1;
return this;
return newNode;
}

@@ -72,3 +69,3 @@

* @param {any} value
* @returns {DoublyLinkedList} - reference to this
* @returns {DoublyLinkedListNode}
*/

@@ -91,6 +88,6 @@ insertAt(position, value) {

let counter = 1;
let currentPosition = 1;
let prev = this._head;
while (counter < position) {
counter += 1;
while (currentPosition < position) {
currentPosition += 1;
prev = prev.getNext();

@@ -105,3 +102,3 @@ }

this._count += 1;
return this;
return newNode;
}

@@ -115,15 +112,14 @@

removeFirst() {
if (this._head === null) return null;
if (this.isEmpty()) return null;
const removed = this._head;
if (this._head.getNext() === null) {
const removedNode = this._head;
if (this._head.hasNext()) {
this._head = this._head.getNext();
this._head.setPrev(null);
} else {
this._head = null;
this._tail = null;
} else {
this._head = this._head.getNext();
this._head.setPrev(null);
}
this._count -= 1;
return removed.setNext(null).setPrev(null);
return removedNode.setNext(null);
}

@@ -137,15 +133,14 @@

removeLast() {
if (this._head === null) return null;
if (this.isEmpty()) return null;
const removed = this._tail;
if (this._head.getNext() === null) {
const removedNode = this._tail;
if (this._tail.hasPrev()) {
this._tail = this._tail.getPrev();
this._tail.setNext(null);
} else {
this._head = null;
this._tail = null;
} else {
this._tail = this._tail.getPrev();
this._tail.setNext(null);
}
this._count -= 1;
return removed.setNext(null).setPrev(null);
return removedNode.setPrev(null);
}

@@ -176,15 +171,38 @@

let counter = 1;
let prev = this._head;
while (counter < position) {
counter += 1;
prev = prev.getNext();
let currentPosition = 1;
let current = this._head.getNext();
while (currentPosition < position) {
currentPosition += 1;
current = current.getNext();
}
return this.remove(current);
}
const removed = prev.getNext();
prev.setNext(prev.getNext().getNext());
prev.getNext().setPrev(prev);
/**
* Removes a node from the list by its reference.
* @public
* @param {DoublyLinkedListNode} node
* @returns {DoublyLinkedListNode}
*/
remove(node) {
if (node && !(node instanceof DoublyLinkedListNode)) {
throw new Error('remove: expects a DoublyLinkedListNode node');
}
if (!node) {
return null;
}
if (!node.hasPrev()) {
return this.removeFirst();
}
if (!node.hasNext()) {
return this.removeLast();
}
node.getPrev().setNext(node.getNext());
node.getNext().setPrev(node.getPrev());
this._count -= 1;
return removed.setNext(null).setPrev(null);
return node.setPrev(null).setNext(null);
}

@@ -196,3 +214,3 @@

* @param {function} cb
* @returns {array} count of removed nodes
* @returns {number} number of removed nodes
*/

@@ -204,29 +222,17 @@ removeEach(cb) {

const removed = [];
let removedCount = 0;
let position = 0;
let prev = null;
let node = this._head;
while (node !== null) {
if (cb(node, position)) {
if (prev === null) {
removed.push(this.removeFirst());
} else if (prev.getNext() === null) {
removed.push(this.removeLast());
} else {
const removedNode = prev.getNext();
prev.setNext(prev.getNext().getNext());
if (prev.getNext() !== null) {
prev.getNext().setPrev(prev);
}
removed.push(removedNode.setNext(null).setPrev(null));
this._count -= 1;
}
let current = this._head;
while (current instanceof DoublyLinkedListNode) {
if (cb(current, position)) {
const next = current.getNext();
this.remove(current);
removedCount += 1;
current = next;
} else {
current = current.getNext();
}
position += 1;
prev = node;
node = node.getNext();
}
return removed;
return removedCount;
}

@@ -244,10 +250,9 @@

const forEachRecursive = (current, position = 0) => {
if (current === null) return;
let current = this._head;
let position = 0;
while (current instanceof DoublyLinkedListNode) {
cb(current, position);
forEachRecursive(current.getNext(), position + 1);
};
forEachRecursive(this._head);
position += 1;
current = current.getNext();
}
}

@@ -265,18 +270,16 @@

const forEachReverseRecursive = (current, position = this._count - 1) => {
if (current === null) return;
let current = this._tail;
let position = this._count - 1;
while (current instanceof DoublyLinkedListNode) {
cb(current, position);
forEachReverseRecursive(current.getPrev(), position - 1);
};
forEachReverseRecursive(this._tail);
position -= 1;
current = current.getPrev();
}
}
/**
* Finds a node in the list using a callback
* @public
* finds a node in the linked list using on a callback
* @param {function} cb
* @returns {DoublyLinkedListNode}
* @throws {Error} if cb is not a function
* @returns {DoublyLinkedListNode|null}
*/

@@ -288,18 +291,14 @@ find(cb) {

const findRecursive = (current) => {
// did not find the node
if (current === null) return null;
// found the node
if (cb(current)) return current;
// haven't found the node yet, check next
return findRecursive(current.getNext());
};
return findRecursive(this._head);
let current = this._head;
while (current instanceof DoublyLinkedListNode) {
if (cb(current)) {
return current;
}
current = current.getNext();
}
return null;
}
/**
* Filters the linked list based on a callback.
* Filters the list based on a callback.
* @public

@@ -315,8 +314,6 @@ * @param {function} cb

const result = new DoublyLinkedList();
let last = null;
this.forEach((node, position) => {
if (!cb(node, position)) return;
last = result.insertLast(node.getValue(), last);
result.insertLast(node.getValue());
});
return result;

@@ -326,2 +323,3 @@ }

/**
* Returns the head node.
* @public

@@ -335,2 +333,3 @@ * @returns {DoublyLinkedListNode}

/**
* Returns the tail node.
* @public

@@ -344,2 +343,3 @@ * @returns {DoublyLinkedListNode}

/**
* Returns the nodes count in the list.
* @public

@@ -353,2 +353,3 @@ * @returns {number}

/**
* Converts the doubly linked list into an array.
* @public

@@ -364,2 +365,3 @@ * @returns {array}

/**
* Checks if the list is empty.
* @public

@@ -373,3 +375,3 @@ * @returns {boolean}

/**
* Clears the linked list
* Clears the list
* @public

@@ -376,0 +378,0 @@ */

30

src/doublyLinkedListNode.js
/**
* @datastructures-js/linked-list
* datastructures-js/linked-list
* @copyright 2020 Eyas Ranjous <eyas.ranjous@gmail.com>

@@ -43,5 +43,9 @@ * @license MIT

* @param {DoublyLinkedListNode} [next]
* @returns {DoublyLinkedList}
*/
setNext(next) {
this._next = (next instanceof DoublyLinkedListNode) ? next : null;
if (next && !(next instanceof DoublyLinkedListNode)) {
throw new Error('setNext expects a DoublyLinkedListNode or null');
}
this._next = next || null;
return this;

@@ -60,6 +64,18 @@ }

* @public
* @returns {boolean}
*/
hasNext() {
return this._next instanceof DoublyLinkedListNode;
}
/**
* @public
* @param {DoublyLinkedListNode} [prev]
* @returns {DoublyLinkedList}
*/
setPrev(prev) {
this._prev = (prev instanceof DoublyLinkedListNode) ? prev : null;
if (prev && !(prev instanceof DoublyLinkedListNode)) {
throw new Error('setPrev expects a DoublyLinkedListNode or null');
}
this._prev = prev || null;
return this;

@@ -75,4 +91,12 @@ }

}
/**
* @public
* @returns {boolean}
*/
hasPrev() {
return this._prev instanceof DoublyLinkedListNode;
}
}
module.exports = DoublyLinkedListNode;

133

src/linkedList.js
/**
* datastructures-js/linked-list
* @license MIT

@@ -12,5 +13,2 @@ * @copyright 2020 Eyas Ranjous <eyas.ranjous@gmail.com>

class LinkedList {
/**
* Creates a linked list.
*/
constructor() {

@@ -22,6 +20,6 @@ this._head = null;

/**
* Adds a node at the beginning of the linked list.
* Adds a node at the beginning of the list.
* @public
* @param {any} value
* @returns {boolean}
* @returns {LinkedListNode}
*/

@@ -31,13 +29,13 @@ insertFirst(value) {

this._count += 1;
return this;
return this._head;
}
/**
* Adds a node at the end of the linked list.
* Adds a node at the end of the list.
* @public
* @param {any} value
* @param {LinkedListNode} [current] - the starting node
* @returns {boolean}
* @param {LinkedListNode} [startingNode]
* @returns {LinkedListNode}
*/
insertLast(value) {
insertLast(value, startingNode) {
if (this.isEmpty()) {

@@ -47,10 +45,14 @@ return this.insertFirst(value);

let current = this._head;
while (current.getNext() instanceof LinkedListNode) {
if (startingNode && !(startingNode instanceof LinkedListNode)) {
throw new Error('insertLast expects a LinkedListNode starting node');
}
let current = startingNode || this._head;
while (current.hasNext()) {
current = current.getNext();
}
current.setNext(new LinkedListNode(value));
current.setNext(new LinkedListNode(value, null));
this._count += 1;
return this;
return current.getNext();
}

@@ -63,3 +65,3 @@

* @param {any} value
* @returns {boolean}
* @returns {LinkedListNode}
*/

@@ -79,6 +81,6 @@ insertAt(position, value) {

let counter = 1;
let currentPosition = 1;
let prev = this._head;
while (counter < position) {
counter += 1;
while (currentPosition < position) {
currentPosition += 1;
prev = prev.getNext();

@@ -90,3 +92,3 @@ }

this._count += 1;
return this;
return prev.getNext();
}

@@ -109,14 +111,14 @@

/**
* Removes last node in the linked list.
* Removes the last node in the list.
* @public
* @param {LinkedListNode} [prev] - previous node
* @param {LinkedListNode} [current] - current node
* @returns {LinkedListNode|null}
*/
removeLast(prev = null, current = this._head) {
removeLast() {
if (this.isEmpty()) return null;
// not last node, move next
if (current.getNext() instanceof LinkedListNode) {
return this.removeLast(current, current.getNext());
let prev = null;
let current = this._head;
while (current.hasNext()) {
prev = current;
current = current.getNext();
}

@@ -129,14 +131,12 @@

// arrived to last node, remove it
const removed = prev.getNext();
prev.setNext(null);
this._count -= 1;
return removed.setNext(null);
return current;
}
/**
* Removes all nodes based on a callback condition.
* Removes all nodes based on a callback.
* @public
* @param {function} cb - callback should return true for removed nodes.
* @returns {array} removed nodes
* @param {function} cb
* @returns {number} number of removed nodes
*/

@@ -148,25 +148,22 @@ removeEach(cb) {

const removedNodes = [];
let removedCount = 0;
let position = 0;
let prev = null;
let current = this._head;
while (current instanceof LinkedListNode) {
if (cb(current, position)) {
let removed;
if (prev === null) {
removedNodes.push(this.removeFirst());
this.removeFirst();
} else {
removed = prev.getNext();
prev.setNext(prev.getNext().getNext());
this._count -= 1;
removedNodes.push(removed.setNext(null));
}
this._count -= 1;
removedCount += 1;
} else {
prev = current;
}
position += 1;
prev = current;
current = current.getNext();
}
return removedNodes;
return removedCount;
}

@@ -199,3 +196,2 @@

}
const removed = prev.getNext();

@@ -208,3 +204,3 @@ prev.setNext(prev.getNext().getNext());

/**
* Traverses the linked list from beginning to end.
* Traverses the list from beginning to end.
* @public

@@ -218,16 +214,15 @@ * @param {function} cb

const forEachRecursive = (current, position = 0) => {
if (current === null) return;
let current = this._head;
let position = 0;
while (current instanceof LinkedListNode) {
cb(current, position);
forEachRecursive(current.getNext(), position + 1);
};
forEachRecursive(this._head);
position += 1;
current = current.getNext();
}
}
/**
* Finds one node in the linked list based on a callback condition.
* Finds one node in the list based on a callback.
* @public
* @returns {LinkedListNode}
* @returns {LinkedListNode|null}
*/

@@ -239,18 +234,14 @@ find(cb) {

const findRecursive = (current) => {
// did not find the node
if (current === null) return null;
// found the node
if (cb(current)) return current;
// haven't found the node yet, check next
return findRecursive(current.getNext());
};
return findRecursive(this._head);
let current = this._head;
while (current instanceof LinkedListNode) {
if (cb(current)) {
return current;
}
current = current.getNext();
}
return null;
}
/**
* Filters the linked list based on a callback condition.
* Filters the list based on a callback.
* @public

@@ -267,3 +258,2 @@ * @param {function} cb - callback should return true for required nodes.

const result = new LinkedList();
this.forEach((node, position) => {

@@ -273,3 +263,2 @@ if (!cb(node, position)) return;

});
return result;

@@ -281,3 +270,3 @@ }

* @public
* @returns {LinkedListNode}
* @returns {LinkedListNode|null}
*/

@@ -289,3 +278,3 @@ head() {

/**
* Returns the nodes count in the linked list.
* Returns the nodes count in the list.
* @public

@@ -310,3 +299,3 @@ * @returns {number}

/**
* Checks if the linked list is empty.
* Checks if the list is empty.
* @public

@@ -320,3 +309,3 @@ * @returns {boolean}

/**
* Clears the linked list
* Clears the list
* @public

@@ -323,0 +312,0 @@ */

22

src/linkedListNode.js
/**
* datastructures-js/linked-list
* @license MIT

@@ -21,3 +22,3 @@ * @copyright 2020 Eyas Ranjous <eyas.ranjous@gmail.com>

* @param {any} value
* @returns {LinkedListNode} - this
* @returns {LinkedListNode}
*/

@@ -39,7 +40,10 @@ setValue(value) {

* @public
* @param {LinkedListNode} - [next]
* @returns {LinkedListNode} - this
* @param {LinkedListNode} [next]
* @returns {LinkedListNode}
*/
setNext(next) {
this._next = (next instanceof LinkedListNode) ? next : null;
if (next && !(next instanceof LinkedListNode)) {
throw new Error('setLeft expects a LinkedListNode or null');
}
this._next = next || null;
return this;

@@ -50,3 +54,3 @@ }

* @public
* @returns {LinkedListNode}
* @returns {LinkedListNode|null}
*/

@@ -56,4 +60,12 @@ getNext() {

}
/**
* @public
* @returns {boolean}
*/
hasNext() {
return this._next instanceof LinkedListNode;
}
}
module.exports = LinkedListNode;
SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc