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

@humanwhocodes/doubly-linked-list

Package Overview
Dependencies
Maintainers
1
Versions
4
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

@humanwhocodes/doubly-linked-list - npm Package Compare versions

Comparing version 2.0.0 to 2.0.1

252

doubly-linked-list.js

@@ -14,9 +14,9 @@ /**

/**
* Represents a single item in a DoublyLinkedList.
* @class DoublyLinkedListItem
* Represents a single node in a DoublyLinkedList.
* @class DoublyLinkedListNode
*/
class DoublyLinkedListItem {
class DoublyLinkedListNode {
/**
* Creates a new instance of DoublyLinkedListItem.
* Creates a new instance of DoublyLinkedListNode.
* @param {*} data The data to store in the node.

@@ -34,5 +34,5 @@ */

/**
* A pointer to the next item in the DoublyLinkedList.
* A pointer to the next node in the DoublyLinkedList.
* @property next
* @type ?DoublyLinkedListItem
* @type ?DoublyLinkedListNode
*/

@@ -42,5 +42,5 @@ this.next = null;

/**
* A pointer to the previous item in the DoublyLinkedList.
* A pointer to the previous node in the DoublyLinkedList.
* @property previous
* @type ?DoublyLinkedListItem
* @type ?DoublyLinkedListNode
*/

@@ -63,5 +63,5 @@ this.previous = null;

/**
* Pointer to first item in the list.
* Pointer to first node in the list.
* @property head
* @type ?DoublyLinkedListItem
* @type ?DoublyLinkedListNode
* @private

@@ -72,5 +72,5 @@ */

/**
* Pointer to last item in the list.
* Pointer to last node in the list.
* @property tail
* @type ?DoublyLinkedListItem
* @type ?DoublyLinkedListNode
* @private

@@ -82,4 +82,3 @@ */

/**
* Appends some data to the end of the list. This method traverses
* the existing list and places the data at the end in a new item.
* Appends some data to the end of the list.
* @param {*} data The data to add to the list.

@@ -91,16 +90,15 @@ * @returns {void}

/*
* Create a new list item object and store the data in it.
* This item will be added to the end of the existing list.
* Create a new list node object and store the data in it.
* This node will be added to the end of the existing list.
*/
const item = new DoublyLinkedListItem(data);
const newNode = new DoublyLinkedListNode(data);
//special case: no items in the list yet
// special case: no nodes in the list yet
if (this[head] === null) {
/*
* Because there are no items in the list, just set the
* `this[head]` and `this[tail]` pointers to the new item.
* Because there are no nodes in the list, just set the
* `this[head]` pointer to the new node.
*/
this[head] = item;
this[tail] = item;
this[head] = newNode;
} else {

@@ -110,12 +108,16 @@

* Unlike in a singly linked list, we have a direct reference to
* the last item in the list. Set the `next` pointer of the
* current last item to `item` in order to append the new data
* to the end of the list. Then, set `item.previous` to the current
* tail to ensure backwards tracking work. Last, reset `this[tail]`
* to `item` to ensure we are still tracking the last item correctly.
* the last node in the list. Set the `next` pointer of the
* current last node to `newNode` in order to append the new data
* to the end of the list. Then, set `newNode.previous` to the current
* tail to ensure backwards tracking work.
*/
this[tail].next = item;
item.previous = this[tail];
this[tail] = item;
this[tail].next = newNode;
newNode.previous = this[tail];
}
/*
* Last, reset `this[tail]` to `newNode` to ensure we are still
* tracking the last node correctly.
*/
this[tail] = newNode;
}

@@ -125,3 +127,3 @@

* Inserts some data into the middle of the list. This method traverses
* the existing list and places the data in a new item at a specific index.
* the existing list and places the data in a new node at a specific index.
* @param {*} data The data to add to the list.

@@ -135,8 +137,8 @@ * @param {int} index The zero-based index at which to insert the data.

/*
* Create a new list item object and store the data in it.
* This item will be inserted into the existing list.
* Create a new list node object and store the data in it.
* This node will be inserted into the existing list.
*/
const item = new DoublyLinkedListItem(data);
const newNode = new DoublyLinkedListNode(data);
// special case: no items in the list yet
// special case: no nodes in the list yet
if (this[head] === null) {

@@ -148,3 +150,3 @@ throw new RangeError(`Index ${index} does not exist in the list.`);

* Special case: if `index` is `0`, then no traversal is needed
* and we need to update `this[head]` to point to `item`.
* and we need to update `this[head]` to point to `newNode`.
*/

@@ -154,22 +156,22 @@ if (index === 0) {

/*
* Ensure the new item's `next` property is pointed to the current
* Ensure the new node's `next` property is pointed to the current
* head.
*/
item.next = this[head];
newNode.next = this[head];
/*
* The current head's `previous` property needs to point to the new
* item to ensure the list is traversable backwards.
* node to ensure the list is traversable backwards.
*/
this[head].previous = item;
this[head].previous = newNode;
/*
* Now it's safe to set `this[head]` to the new item, effectively
* making the new item the first item in the list.
* Now it's safe to set `this[head]` to the new node, effectively
* making the new node the first node in the list.
*/
this[head] = item;
this[head] = newNode;
} else {
/*
* The `current` variable is used to track the item that is being
* The `current` variable is used to track the node that is being
* used inside of the loop below. It starts out pointing to

@@ -188,4 +190,4 @@ * `this[head]` and is overwritten inside of the loop.

/*
* Traverse the list items using `next` pointers, and make
* sure to keep track of how many items have been visited. When
* Traverse the list nodes using `next` pointers, and make
* sure to keep track of how many nodes have been visited. When
* `i` is the same as `index`, it means we've found the location to

@@ -200,4 +202,4 @@ * insert the new data.

/*
* At this point, `current` is either the item to insert the new data
* before, or the last item in the list. The only way to tell is if
* At this point, `current` is either the node to insert the new data
* before, or the last node in the list. The only way to tell is if
* `i` is still less than `index`, that means the index is out of range

@@ -211,17 +213,17 @@ * and an error should be thrown.

/*
* If code continues to execute here, it means `current` is the item
* If code continues to execute here, it means `current` is the node
* to insert new data before.
*
* First, insert `item` after `current.previous` by updating
* `current.previous.next` and `item.previous`.
* First, insert `newNode` after `current.previous` by updating
* `current.previous.next` and `newNode.previous`.
*/
current.previous.next = item;
item.previous = current.previous;
current.previous.next = newNode;
newNode.previous = current.previous;
/*
* Next, insert `current` after `item` by updating `item.next` and
* Next, insert `current` after `newNode` by updating `newNode.next` and
* `current.previous`.
*/
item.next = current;
current.previous = item;
newNode.next = current;
current.previous = newNode;
}

@@ -232,3 +234,3 @@ }

* Inserts some data into the middle of the list. This method traverses
* the existing list and places the data in a new item after a specific index.
* the existing list and places the data in a new node after a specific index.
* @param {*} data The data to add to the list.

@@ -242,8 +244,8 @@ * @param {int} index The zero-based index after which to insert the data.

/*
* Create a new list item object and store the data in it.
* This item will be inserted into the existing list.
* Create a new list node object and store the data in it.
* This node will be inserted into the existing list.
*/
const item = new DoublyLinkedListItem(data);
const newNode = new DoublyLinkedListNode(data);
// special case: no items in the list yet
// special case: no nodes in the list yet
if (this[head] === null) {

@@ -254,3 +256,3 @@ throw new RangeError(`Index ${index} does not exist in the list.`);

/*
* The `current` variable is used to track the item that is being
* The `current` variable is used to track the node that is being
* used inside of the loop below. It starts out pointing to

@@ -269,4 +271,4 @@ * `this[head]` and is overwritten inside of the loop.

/*
* Traverse the list items similar to the `add()` method, but make
* sure to keep track of how many items have been visited and update
* Traverse the list nodes similar to the `add()` method, but make
* sure to keep track of how many nodes have been visited and update
* the `previous` pointer in addition to `current`. When

@@ -282,4 +284,4 @@ * `i` is the same as `index`, it means we've found the location to

/*
* At this point, `current` is either the item to insert the new data
* before, or the last item in the list. The only way to tell is if
* At this point, `current` is either the node to insert the new data
* before, or the last node in the list. The only way to tell is if
* `i` is still less than `index`, that means the index is out of range

@@ -293,3 +295,3 @@ * and an error should be thrown.

/*
* If code continues to execute here, it means `current` is the item
* If code continues to execute here, it means `current` is the node
* to insert new data after.

@@ -300,19 +302,19 @@ */

if (this[tail] === current) {
this[tail] = item;
this[tail] = newNode;
} else {
/*
* Otherwise, insert `item` before `current.next` by updating
* `current.next.previous` and `item.item`.
* Otherwise, insert `newNode` before `current.next` by updating
* `current.next.previous` and `newNode.node`.
*/
current.next.previous = item;
item.next = current.next;
current.next.previous = newNode;
newNode.next = current.next;
}
/*
* Next, insert `item` after `current` by updating `item.previous` and
* Next, insert `newNode` after `current` by updating `newNode.previous` and
* `current.next`.
*/
item.previous = current;
current.next = item;
newNode.previous = current;
current.next = newNode;
}

@@ -322,6 +324,6 @@

* Retrieves the data in the given position in the list.
* @param {int} index The zero-based index of the item whose data
* @param {int} index The zero-based index of the node whose data
* should be returned.
* @returns {*} The data in the "data" portion of the given item
* or undefined if the item doesn't exist.
* @returns {*} The data in the "data" portion of the given node
* or undefined if the node doesn't exist.
*/

@@ -334,3 +336,3 @@ get(index) {

/*
* The `current` variable is used to track the item that is being
* The `current` variable is used to track the node that is being
* used inside of the loop below. It starts out pointing to

@@ -349,7 +351,6 @@ * `this[head]` and is overwritten inside of the loop.

/*
* Traverse the list items similar to the `add()` method, but make
* sure to keep track of how many items have been visited and update
* the `previous` pointer in addition to `current`. When
* `i` is the same as `index`, it means we've found the location to
* insert the new data.
* Traverse the list nodes, but make sure to keep track of how many
* nodes have been visited and update the `previous` pointer in
* addition to `current`. When `i` is the same as `index`, it means
* we've found the location to insert the new data.
*/

@@ -364,3 +365,3 @@ while ((current !== null) && (i < index)) {

* end of the list. In that case, we return `undefined` to indicate
* that the item at `index` was not found. If `current` is not
* that the node at `index` was not found. If `current` is not
* `null`, then it's safe to return `current.data`.

@@ -383,3 +384,3 @@ */

/*
* The `current` variable is used to iterate over the list items.
* The `current` variable is used to iterate over the list nodes.
* It starts out pointing to the head and is overwritten inside

@@ -398,6 +399,6 @@ * of the loop below.

/*
* This loop checks each item in the list to see if it matches `data`.
* This loop checks each node in the list to see if it matches `data`.
* If a match is found, it returns `index` immediately, exiting the
* loop because there's no reason to keep searching. The search
* continues until there are no more items to search (when `current` is `null`).
* continues until there are no more nodes to search (when `current` is `null`).
*/

@@ -409,3 +410,3 @@ while (current !== null) {

// traverse to the next item in the list
// traverse to the next node in the list
current = current.next;

@@ -425,4 +426,4 @@

/**
* Removes the item from the given location in the list.
* @param {int} index The zero-based index of the item to remove.
* Removes the node from the given location in the list.
* @param {int} index The zero-based index of the node to remove.
* @returns {*} The data in the given position in the list.

@@ -433,26 +434,17 @@ * @throws {RangeError} If index is out of range.

// special case: no items in the list
if (this[head] === null) {
// special cases: no nodes in the list or `index` is negative
if ((this[head] === null) || (index < 0)) {
throw new RangeError(`Index ${index} does not exist in the list.`);
}
// special case: `index` is an invalid value
if (index < 0) {
throw new RangeError(`Index ${index} does not exist in the list.`);
}
// special case: removing the first node
if (index === 0) {
/*
* The `current` variable is used to iterate over the list items.
* It starts out pointing to the head and is overwritten inside
* of the loop below.
*/
let current = this[head];
// store the data from the current head
const data = this[head].data;
// special case: removing the first item
if (index === 0) {
// just replace the head with the next node in the list
this[head] = this[head].next;
// just replace the head with the next item in the list
this[head] = current.next;
// special case: there was only one item, so also reset `this[tail]`
// special case: there was only one node, so also reset `this[tail]`
if (this[head] === null) {

@@ -465,6 +457,14 @@ this[tail] = null;

// return the data at the previous head of the list
return current.data;
return data;
}
/*
* The `current` variable is used to iterate over the list nodes.
* It starts out pointing to the head and is overwritten inside
* of the loop below.
*/
let current = this[head];
/*
* The `i` variable is used to track how deep into the list we've

@@ -477,4 +477,4 @@ * gone. This is important because it's the only way to know when

/*
* Traverse the list items similar to the `add()` method, but make
* sure to keep track of how many items have been visited. When
* Traverse the list nodes similar to the `get()` method, but make
* sure to keep track of how many nodes have been visited. When
* `i` is the same as `index`, it means we've found the location to

@@ -485,3 +485,3 @@ * remove.

// traverse to the next item
// traverse to the next node
current = current.next;

@@ -494,3 +494,3 @@

/*
* If `current` isn't `null`, then that means we've found the item
* If `current` isn't `null`, then that means we've found the node
* to remove.

@@ -500,3 +500,3 @@ */

// skip over the item to remove
// skip over the node to remove
current.previous.next = current.next;

@@ -528,3 +528,3 @@

/**
* Removes all items from the list.
* Removes all nodes from the list.
* @returns {void}

@@ -540,4 +540,4 @@ */

/**
* Returns the number of items in the list.
* @returns {int} The number of items in the list.
* Returns the number of nodes in the list.
* @returns {int} The number of nodes in the list.
*/

@@ -552,3 +552,3 @@ get size() {

/*
* The `current` variable is used to iterate over the list items.
* The `current` variable is used to iterate over the list nodes.
* It starts out pointing to the head and is overwritten inside

@@ -560,3 +560,3 @@ * of the loop below.

/*
* The `count` variable is used to keep track of how many items have
* The `count` variable is used to keep track of how many nodes have
* been visited inside the loop below. This is important because this

@@ -569,3 +569,3 @@ * is the value to return from this method.

* As long as `current` is not `null`, that means we're not yet at the
* end of the list, so adding 1 to `count` and traverse to the next item.
* end of the list, so adding 1 to `count` and traverse to the next node.
*/

@@ -579,3 +579,3 @@ while (current !== null) {

* When `current` is `null`, the loop is exited at the value of `count`
* is the number of items that were counted in the loop.
* is the number of nodes that were counted in the loop.
*/

@@ -594,3 +594,3 @@ return count;

/**
* Create an iterator that returns each item in the list.
* Create an iterator that returns each node in the list.
* @returns {Iterator} An iterator on the list.

@@ -601,3 +601,3 @@ */

/*
* The `current` variable is used to iterate over the list items.
* The `current` variable is used to iterate over the list nodes.
* It starts out pointing to the head and is overwritten inside

@@ -619,3 +619,3 @@ * of the loop below.

/**
* Create an iterator that returns each item in the list in reverse order.
* Create an iterator that returns each node in the list in reverse order.
* @returns {Iterator} An iterator on the list.

@@ -626,3 +626,3 @@ */

/*
* The `current` variable is used to iterate over the list items.
* The `current` variable is used to iterate over the list nodes.
* It starts out pointing to the tail and is overwritten inside

@@ -629,0 +629,0 @@ * of the loop below.

2

package.json
{
"name": "@humanwhocodes/doubly-linked-list",
"version": "2.0.0",
"version": "2.0.1",
"description": "A doubly linked list implementation in JavaScript",

@@ -5,0 +5,0 @@ "main": "doubly-linked-list.js",

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