New Case Study:See how Anthropic automated 95% of dependency reviews with Socket.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 1.0.6 to 2.0.0

CHANGELOG.md
src/doublyLinkedList.js
src/doublyLinkedListNode.js
src/linkedList.js
src/linkedListNode.js
test/doublyLinkedList.test.js
test/linkedList.test.js

265

index.js

@@ -1,263 +0,4 @@

/**
* datastructures-js/linked-list
* @copyright 2018 Eyas Ranjous <eyas.ranjous@gmail.com>
* @license MIT
*/
const LinkedList = require('./src/linkedList');
const DoublyLinkedList = require('./src/doublyLinkedList');
/**
* Linked List Node
* @function
*/
const node = (val, nex) => {
let value = val;
let next = nex;
/**
* @param {string|number} v
*/
const setValue = (v) => {
value = v;
};
/**
* @return {string|number}
*/
const getValue = () => value;
/**
* @param {object} - node
*/
const setNext = (n) => {
next = n;
};
/**
* @return {object} - node
*/
const getNext = () => next || null;
// linkedList node API
return {
setValue,
getValue,
setNext,
getNext
};
};
/**
* Linked List
* @function
*/
const linkedList = () => {
let headNode = null;
let nodesCount = 0;
/**
* @returns {object} - node
*/
const head = () => headNode;
/**
* @returns {number}
*/
const count = () => nodesCount;
/**
* @param {string|number} value
* @returns {object} - node
*/
const find = (value) => {
let current = headNode;
while (current !== null) {
if (current.getValue() === value) {
return current;
}
current = current.getNext();
}
return current;
};
/**
* @param {string|number} value
*/
const addFirst = (value) => {
if (headNode === null) {
headNode = node(value);
} else {
headNode = node(value, headNode);
}
nodesCount += 1;
};
/**
* @param {string|number} value
*/
const addLast = (value) => {
if (headNode === null) {
headNode = node(value);
} else {
let current = headNode;
while (current.getNext() !== null) {
current = current.getNext();
}
current.setNext(node(value));
}
nodesCount += 1;
};
/**
* adds a new node after an existing node
* @param {string|number} value
* @param {string|number} newValue
* @throws {Error}
*/
const addAfter = (value, newValue) => {
let current = headNode;
while (current !== null) {
if (current.getValue() === value) {
current.setNext(node(newValue, current.getNext()));
nodesCount += 1;
break;
} else {
current = current.getNext();
}
}
if (current === null) {
throw new Error(`node ${value} not found`);
}
};
/**
* @public
* adds a new node before an existing node
* @param {(string|number)} value
* @param {(string|number)} newValue
* @throws {Error}
*/
const addBefore = (value, newValue) => {
let prev = null;
let current = headNode;
while (current !== null) {
if (current.getValue() === value) {
if (prev === null) {
addFirst(newValue);
} else {
prev.setNext(node(newValue, current));
nodesCount += 1;
}
break;
} else {
prev = current;
current = current.getNext();
}
}
if (current === null) {
throw new Error(`node ${value} not found`);
}
};
/**
* removes the first node
*/
const removeFirst = () => {
if (headNode !== null) {
if (headNode.getNext() === null) {
headNode = null;
} else {
headNode = headNode.getNext();
}
nodesCount -= 1;
}
};
/**
* removes the last node
*/
const removeLast = () => {
let prev = null;
let current = headNode;
while (current.getNext() !== null) {
prev = current;
current = current.getNext();
}
if (prev === null) {
removeFirst();
} else {
prev.setNext(null);
nodesCount -= 1;
}
};
/**
* removes a node by its value
* @param {(string|number)} value
*/
const remove = (value) => {
let prev = null;
let current = headNode;
while (current !== null) {
if (current.getValue() === value) {
if (prev === null) {
removeFirst();
} else {
prev.setNext(current.getNext());
nodesCount -= 1;
}
break;
} else {
prev = current;
current = current.getNext();
}
}
};
/**
* traverse the linkedlist from a beginning to end
* @param {function} cb - called with node in the linked list
*/
const traverse = (cb) => {
let current = headNode;
while (current !== null) {
cb(current);
current = current.getNext();
}
};
/**
* @returns {array}
*/
const toArray = () => {
const arr = [];
traverse(n => arr.push(n.getValue()));
return arr;
};
/**
* clears the linked list
*/
const clear = () => {
headNode = null;
nodesCount = 0;
};
// linkedList API
return {
node,
head,
count,
find,
addFirst,
addLast,
addBefore,
addAfter,
remove,
removeFirst,
removeLast,
traverse,
toArray,
clear
};
};
module.exports = linkedList;
module.exports = { LinkedList, DoublyLinkedList };

16

package.json
{
"name": "@datastructures-js/linked-list",
"version": "1.0.6",
"version": "2.0.0",
"description": "linked list implementation in javascript",

@@ -25,13 +25,13 @@ "main": "index.js",

"devDependencies": {
"chai": "^4.1.2",
"eslint": "^4.19.1",
"eslint-config-airbnb-base": "^12.1.0",
"eslint-plugin-import": "^2.12.0",
"grunt-eslint": "^20.2.0",
"grunt": "^1.0.1",
"chai": "^4.2.0",
"eslint": "^6.7.2",
"eslint-config-airbnb-base": "^14.0.0",
"eslint-plugin-import": "^2.19.1",
"grunt": "^1.0.4",
"grunt-eslint": "^22.0.0",
"grunt-mocha-istanbul": "^5.0.2",
"grunt-mocha-test": "^0.13.3",
"istanbul": "^0.4.5",
"mocha": "^5.0.0"
"mocha": "^6.2.2"
}
}

557

README.md

@@ -7,10 +7,36 @@ # @datastrucures-js/linked-list

node's data type: **number**, **string**, **boolean**, **null**, **undefined**.
a javascript implementation for LinkedList & DoublyLinkedList.
<img width="429" alt="Linked List" src="https://user-images.githubusercontent.com/6517308/35762715-5d00c9bc-0861-11e8-88f7-6e503a1fa3af.png">
## Usage
```js
const linkedListFn = require('@datastructures-js/linked-list');
const linkedList = linkedListFn();
<img width="552" alt="dll" src="https://user-images.githubusercontent.com/6517308/35762752-19b17df4-0862-11e8-8ce3-f940d83dde51.png">
# Table of Contents
* [Install](#install)
* [API](#api)
* [require](#require)
* [import](#import)
* [Creating a List](#create-a-list)
* [.insertFirst(value)](#insertfirstvalue)
* [.insertLast(value)](#insertlastvalue)
* [.insertAt(value, position)](#insertatvalue-position)
* [.forEach(cb)](#foreachcb)
* [.forEachReverse(cb)](#foreachreversecb)
* [.find(cb)](#findcb)
* [.filter(cb)](#filtercb)
* [.toArray()](#toarray)
* [.head()](#head)
* [.tail()](#tail)
* [.count()](#count)
* [.removeFirst()](#removefirst)
* [.removeLast()](#removelast)
* [.removeAt(position)](#removeatposition)
* [.removeEach(cb)](#removeeachcb)
* [.clear()](#clear)
* [Build](#build)
* [License](#license)
## install
```sh
npm install --save @datastructures-js/linked-list
```

@@ -20,127 +46,488 @@

**.node(value)**
### require
```js
const { LinkedList, DoublyLinkedList } = require('@datastructures-js/linked-list');
```
creates a linked list node with a given value. The node object exposes the following functions:
### import
```js
import { LinkedList, DoublyLinkedList } from '@datastructures-js/linked-list';
```
* **.setNext(node)** sets the next linkedListNode object.
* **.getNext()** gets the next linkedListNode object.
* **.setValue(value)** sets the value of the node.
* **.getValue() gets** the value of the node
### Create a list
```js
const linkedList = new LinkedList();
```javascript
const n = linkedList.node('new_node');
console.log(n.getValue()); // new_node
const doublyLinkedList = new DoublyLinkedList();
```
**.addFirst(value)**
### .insertFirst(value)
inserts a node at the beginning of the list.
adds a node of the given value at the beginning of the list.
```javascript
linkedList.addFirst('n1');
<table>
<tr>
<th>runtime</th>
<th>params</th>
<th>return</th>
</tr>
<tr>
<td>O(1)</td>
<td>
value: {object}
</td>
<td>
in LinkedList: {LinkedListNode}
<br/><br/>
in DoublyLinkedList: {DoublyLinkedListNode}
</td>
</tr>
</table>
```js
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
```
**.addLast(value)**
### .insertLast(value)
inserts a node at the end of the list.
adds a node of the given value at the end of the list.
```javascript
linkedList.addLast('n4');
<table>
<tr>
<th>runtime</th>
<th>params</th>
<th>return</th>
</tr>
<tr>
<td>
in LinkedList: O(n)
<br/><br />
in DoublyLinkedList: O(1)
</td>
<td>
value: {object}
</td>
<td>
in LinkedList: {LinkedListNde}
<br/><br/>
in DoublyLinkedList: {DoublyLinkedListNode}
</td>
</tr>
</table>
```js
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
```
**.addAfter(value, newValue)**
### .insertAt(value, position)
inserts a node at specific position of the list. First (head) node is at position 0.
adds a node with a given value after an existing value's node.
```javascript
try {
linkedList.addAfter('n1', 'n2');
linkedList.addAfter('n33', 'n3');
}
catch (e) {
console.log(e.message); // node n33 not found
}
<table>
<tr>
<th>runtime</th>
<th>params</th>
<th>return</th>
</tr>
<tr>
<td>
in LinkedList: O(n)
<br/><br />
in DoublyLinkedList: O(n)
</td>
<td>
value: {object}
<br /><br />
position: {number}
</td>
<td>
in LinkedList: {LinkedListNode}
<br/><br/>
in DoublyLinkedList: {DoublyLinkedListNode}
</td>
</tr>
</table>
```js
const node1 = linkedList.insertAt(5, 2); // node1.getValue() = 5
const node2 = doublyLinkedList.insertAt(5, 2); // node2.getValue() = 5
```
**.addBefore(value, newValue)**
### .forEach(cb)
Loop on the linked list from beginning to end, and pass each node to the callback.
adds a node with a given value before an existing value's node.
```javascript
try {
linkedList.addBefore('n4', 'n3');
linkedList.addBefore('n33', 'n3');
}
catch (e) {
console.log(e.message); // node n33 not found
}
<table>
<tr>
<th>runtime</th>
<th>params</th>
</tr>
<tr>
<td>
O(n)
</td>
<td>
cb: {function(node)}
</td>
</tr>
</table>
```js
linkedList.forEach((node) => console.log(node.getValue()));
/*
2
1
5
3
4
*/
doublyLinkedList.forEach((node) => console.log(node.getValue()));
/*
2
1
5
3
4
*/
```
**.find(value)**
finds a node by its value and returns a linked list node object.
### .forEachReverse(cb)
Only in DoublyLinkedList. Loop on the doubly linked list from end to beginning, and pass each node to the callback.
```javascript
const n3 = linkedList.find('n3');
console.log(n3.getValue()); // n3
console.log(n3.getNext().getValue()); // n4
<table>
<tr>
<th>runtime</th>
<th>params</th>
</tr>
<tr>
<td>
O(n)
</td>
<td>
cb: {function(node)}
</td>
</tr>
</table>
```js
doublyLinkedList.forEachReverse((node) => console.log(node.getValue()));
/*
4
3
5
1
2
*/
```
**.head()**
### .find(cb)
returns the first node that returns true from the callback.
returns the first linkedListNode object in the list.
```javascript
const head = linkedList.head();
console.log(head.getValue()); // n1
<table>
<tr>
<th>runtime</th>
<th>params</th>
<th>return</th>
</tr>
<tr>
<td>
O(n)
</td>
<td>
cb: {function(node)}
</td>
<td>
in LinkedList: {LinkedListNode}
<br/><br/>
in DoublyLinkedList: {DoublyLinkedListNode}
</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
```
**.traverse(cb)**
### .filter(cb)
returns a filtered linked list of all the nodes that returns true from the callback.
traverse the linked list and calls cb for each node
```javascript
linkedList.traverse((n) => { console.log(n.getValue()); });
// n1
// n2
// n3
// n4
<table>
<tr>
<th>runtime</th>
<th>params</th>
<th>return</th>
</tr>
<tr>
<td>
O(n)
</td>
<td>
cb: {function(node)}
</td>
<td>
in LinkedList: {LinkedList}
<br/><br/>
in DoublyLinkedList: {DoublyLinkedList}
</td>
</tr>
</table>
```js
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
*/
```
**.remove(value)**
### .toArray()
converts the linked list into an array.
remove the value's node - if exists - from the list.
```javascript
linkedList.remove('n3');
<table>
<tr>
<th>runtime</th>
<th>return</th>
</tr>
<tr>
<td>
O(n)
</td>
<td>
{array}
</td>
</tr>
</table>
```js
console.log(linkedList.toArray()); // [2, 1, 5, 3, 4]
console.log(doublyLinkedList.toArray()); // [2, 1, 5, 3, 4]
```
**.removeFirst()**
### .head()
returns the head node in the linked list.
removes the first node in the list.
```javascript
linkedList.removeFirst(); // n1 removed
<table>
<tr>
<th>runtime</th>
<th>return</th>
</tr>
<tr>
<td>
O(1)
</td>
<td>
in LinkedList: {LinkedListNode}
<br/><br/>
in DoublyLinkedList: {DoublyLinkedListNode}
</td>
</tr>
</table>
```js
console.log(linkedList.head().getValue()); // 2
console.log(doublyLinkedList.head().getValue()); // 2
```
**.removeLast()**
### .tail()
Only in DoublyLinkedList. returns the tail node in the doubly linked list
removes the last node in the list.
```javascript
linkedList.removeLast(); // n4 removed
<table>
<tr>
<th>runtime</th>
<th>return</th>
</tr>
<tr>
<td>
O(1)
</td>
<td>
{DoublyLinkedListNode}
</td>
</tr>
</table>
```js
console.log(doublyLinkedList.tail().getValue()); // 4
```
**.toArray()**
### .count()
returns the number of nodes in the linked list.
converts the linkedList to an array
```javascript
console.log(linkedList.toArray());
// ['n1', 'n2', 'n3', 'n4']
<table>
<tr>
<th>runtime</th>
<th>return</th>
</tr>
<tr>
<td>
O(1)
</td>
<td>
{number}
</td>
</tr>
</table>
```js
console.log(linkedList.count()); // 5
console.log(doublyLinkedList.count()); // 5
```
**.count()**
### .removeFirst()
removes the first (head) node of the list.
returns nodes' count in the list.
```javascript
console.log(linkedList.count()); // 1
<table>
<tr>
<th>runtime</th>
<th>return</th>
</tr>
<tr>
<td>O(1)</td>
<td>{boolean}</td>
</tr>
</table>
```js
linkedList.removeFirst(); // true
doublyLinkedList.removeFirst(); // true
```
**.clear()**
### .removeLast()
removes the last node from the list.
removes all nodes from the list.
```javascript
<table>
<tr>
<th>runtime</th>
<th>return</th>
</tr>
<tr>
<td>
in LinkedList: O(n)
<br/><br />
in DoublyLinkedList: O(1)
</td>
<td>{boolean}</td>
</tr>
</table>
```js
linkedList.removeLast(); // true
doublyLinkedList.removeLast(); // true
```
### .removeAt(position)
removes a node at a specific position. First (head) node is at position 0.
<table>
<tr>
<th>runtime</th>
<th>params</th>
<th>return</th>
</tr>
<tr>
<td>
O(n)
</td>
<td>
position: {number}
</td>
<td>
{boolean}
</td>
</tr>
</table>
```js
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.
<table>
<tr>
<th>runtime</th>
<th>params</th>
<th>return</th>
</tr>
<tr>
<td>
O(n)
</td>
<td>
cb: {function(node)}
</td>
<td>
{number} number of removed nodes
</td>
</tr>
</table>
```js
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.
<table>
<tr>
<th>runtime</th>
</tr>
<tr>
<td>
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
```

@@ -147,0 +534,0 @@ 

.npmignore
LICENSE

Sorry, the diff of this file is not supported yet

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