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

Comparing version 6.0.0 to 6.1.0

CHANGELOG.md

@@ -8,2 +8,7 @@ # Changelog
 ## [Unreleased]
+## [6.1.0] - 2023-05-28
+### Added
+- `insertBefore` to add a node before an existing node in the DoublyLinkedList.
+- `insertAfter` to add a node after an existing node in the DoublyLinkedList.
+
 ## [6.0.0] - 2023-03-20
@@ -10,0 +15,0 @@ ### Changed

DoublyLinkedList.md

@@ -11,2 +11,4 @@ # DoublyLinkedList
   * [insertLast](#insertlast)
+  * [insertBefore](#insertbefore)
+  * [insertAfter](#insertafter)
   * [insertAt](#insertat)
@@ -123,2 +125,20 @@ * [forEach](#foreach)
 
+### insertBefore
+inserts a node before an existing node in O(1) runtime and returns the inserted node.
+
+```js
+const n23 = points.find((p) => p.x === 2 && p.y === 3);
+const inserted = points.insertBefore(new Point(-1, -2), n23); // insert (-1,-2) before (2,3)
+console.log(inserted.getNext().toString()); // (2,3)
+```
+
+### insertAfter
+inserts a node after an existing node in O(1) runtime and returns the inserted node.
+
+```js
+const n34 = points.find((p) => p.x === 3 && p.y === 4);
+const inserted = points.insertAfter(new Point(-6, -7), n34); // insert (-6,-7) before (3,4)
+console.log(inserted.getPrev().toString()); // (3,4)
+```
+
 ### insertAt
@@ -152,4 +172,6 @@ inserts a node at a specific position of the list in O(n) runtime. First (head) node is at position 0.
 (1,2)
+(-1,-2)
 (2,3)
 (3,4)
+(-6,-7)
 (4,5)
@@ -180,4 +202,6 @@ (5,6)
 (4,5)
+(-6,-7)
 (3,4)
 (2,3)
+(-1,-2)
 (1,2)
@@ -243,6 +267,7 @@ (0,1)
 ```js
-console.log(doublyLinkedList.toArray().map(n => n.getValue())); // [1, 2, 5, 3, 4, 5]
+console.log(doublyLinkedList.toArray().map(n => n.getValue()));
+// [1, 2, 5, 3, 4, 5]
 
 console.log(points.toArray().map(p => p.toString()));
-// ['(0,1)', '(1,2)', '(2,3)', '(3,4)', '(4,5)', '(5,6)']
+// ['(0,1)', '(1,2)', '(-1,-2)', '(2,3)','(3,4)', '(-6,-7)', '(4,5)', '(5,6)']
 ```
@@ -249,0 +274,0 @@

package.json

 {
   "name": "@datastructures-js/linked-list",
-  "version": "6.0.0",
+  "version": "6.1.0",
   "description": "a javascript implementation of LinkedList & DoublyLinkedList",
@@ -5,0 +5,0 @@ "main": "index.js",

src/doublyLinkedList.d.ts

@@ -5,5 +5,7 @@ import { DoublyLinkedListNode } from './doublyLinkedListNode';
   constructor();
-  insertFirst(value: T): DoublyLinkedListNode;
-  insertLast(value: T): DoublyLinkedListNode;
-  insertAt(position: number, value: T): DoublyLinkedListNode;
+  insertFirst(value: T | DoublyLinkedListNode): DoublyLinkedListNode;
+  insertLast(value: T | DoublyLinkedListNode): DoublyLinkedListNode;
+  insertAt(position: number, value: T | DoublyLinkedListNode): DoublyLinkedListNode;
+  insertBefore(value: T | DoublyLinkedListNode, node?: DoublyLinkedListNode): DoublyLinkedListNode;
+  insertAfter(value: T | DoublyLinkedListNode, node?: DoublyLinkedListNode): DoublyLinkedListNode;
   removeFirst(): DoublyLinkedListNode;
@@ -25,3 +27,3 @@ removeLast(): DoublyLinkedListNode;
   clear(): void;
-  static fromArray<T>(values: T[]): DoublyLinkedList<T>;
+  static fromArray<T>(values: T[] | DoublyLinkedListNode[]): DoublyLinkedList<T>;
 }

src/doublyLinkedList.js

@@ -22,3 +22,3 @@ /**
    * @public
-   * @param {any} value
+   * @param {T | DoublyLinkedListNode} value
    * @returns {DoublyLinkedListNode}
@@ -47,3 +47,3 @@ */
    * @public
-   * @param {any} value
+   * @param {T | DoublyLinkedListNode} value
    * @returns {DoublyLinkedListNode}
@@ -73,3 +73,3 @@ */
    * @param {number} position
-   * @param {any} value
+   * @param {T | DoublyLinkedListNode} value
    * @returns {DoublyLinkedListNode}
@@ -113,2 +113,66 @@ */
   /**
+   * Adds a node before an existing node.
+   * @public
+   * @param {T | DoublyLinkedListNode} value
+   * @param {DoublyLinkedListNode} existingNode
+   * @returns {DoublyLinkedListNode}
+   */
+  insertBefore(value, existingNode) {
+    if (!existingNode) {
+      return this.insertLast(value);
+    }
+
+    if (existingNode === this._head) {
+      return this.insertFirst(value);
+    }
+
+    let newNode = value;
+    if (!(newNode instanceof DoublyLinkedListNode)) {
+      newNode = new DoublyLinkedListNode(value);
+    }
+
+    newNode.setNext(existingNode);
+    newNode.setPrev(existingNode.getPrev());
+
+    newNode.getNext().setPrev(newNode);
+    newNode.getPrev().setNext(newNode);
+
+    this._count += 1;
+
+    return newNode;
+  }
+
+  /**
+   * Adds a node after an existing node.
+   * @public
+   * @param {T | DoublyLinkedListNode} value
+   * @param {DoublyLinkedListNode} existingNode
+   * @returns {DoublyLinkedListNode}
+   */
+  insertAfter(value, existingNode) {
+    if (!existingNode) {
+      return this.insertFirst(value);
+    }
+
+    if (existingNode === this._tail) {
+      return this.insertLast(value);
+    }
+
+    let newNode = value;
+    if (!(newNode instanceof DoublyLinkedListNode)) {
+      newNode = new DoublyLinkedListNode(value);
+    }
+
+    newNode.setPrev(existingNode);
+    newNode.setNext(existingNode.getNext());
+
+    newNode.getNext().setPrev(newNode);
+    newNode.getPrev().setNext(newNode);
+
+    this._count += 1;
+
+    return newNode;
+  }
+
+  /**
    * Removes the head node.
@@ -115,0 +179,0 @@ * @public

src/linkedList.d.ts

@@ -5,5 +5,5 @@ import { LinkedListNode } from './linkedListNode';
   constructor();
-  insertFirst(value: T): LinkedListNode;
-  insertLast(value: T): LinkedListNode;
-  insertAt(position: number, value: T): LinkedListNode;
+  insertFirst(value: T | LinkedListNode): LinkedListNode;
+  insertLast(value: T | LinkedListNode): LinkedListNode;
+  insertAt(position: number, value: T | LinkedListNode): LinkedListNode;
   removeFirst(): LinkedListNode;
@@ -21,3 +21,3 @@ removeLast(): LinkedListNode;
   clear(): void;
-  static fromArray<T>(values: T[]): LinkedList<T>;
+  static fromArray<T>(values: T[] | LinkedListNode[]): LinkedList<T>;
 }

src/linkedList.js

@@ -21,3 +21,3 @@ /**
    * @public
-   * @param {any} value
+   * @param {T | LinkedListNode} value
    * @returns {LinkedListNode}
@@ -39,3 +39,3 @@ */
    * @public
-   * @param {any} value
+   * @param {T | LinkedListNode} value
    * @param {LinkedListNode} [startingNode]
@@ -71,3 +71,3 @@ * @returns {LinkedListNode}
    * @param {number} position
-   * @param {any} value
+   * @param {T | LinkedListNode} value
    * @returns {LinkedListNode}
@@ -74,0 +74,0 @@ */

No alert changes

Improved metrics

Total package byte prevSize

46430

increased by6.61%

Lines of code

995

increased by5.51%

No dependency changes