Intro
Last time, we learned how to insert a new node at a specific index.
Today, we'll learn how to remove a node at a specific index.
Starter Code
We start with code that has the push, shift, pop and get method,
because we can reuse them.
class Node {
constructor(value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.length = 0;
this.head = null;
this.tail = null;
}
push(value) {
const newNode = new Node(value);
if (!this.length) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
this.length += 1;
return newNode;
}
shift() {
if (!this.length) {
return null;
}
const nodeToRemove = this.head;
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
this.head = nodeToRemove.next;
this.head.prev = null;
nodeToRemove.next = null;
}
this.length -= 1;
return nodeToRemove;
}
pop() {
if (!this.length) {
return null;
} else {
const nodeToRemove = this.tail;
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
this.tail = this.tail.prev;
this.tail.next = null;
nodeToRemove.prev = null;
}
this.length -= 1;
return nodeToRemove;
}
}
get(index) {
if (!this.length || index < 0 || index >= this.length) {
return null;
} else {
let currentNode;
if (index < this.length / 2) {
let counter = 0;
currentNode = this.head;
while (counter < index) {
currentNode = currentNode.next;
counter += 1;
}
} else {
let counter = this.length - 1;
currentNode = this.tail;
while (counter > index) {
currentNode = currentNode.prev;
counter -= 1;
}
}
return currentNode;
}
}
}
Thoughts
First, we should think about the constraints and possibilities:
If the index is invalid (list is empty, index less than 0, greater than or equal to the list's length):
- return null
If we want to remove the first node (index equals 0):
- use the
shiftmethod to add the data
If we want to remove the last node (index equals length minus 1):
- use the
popmethod to add the data
All remaining cases:
- store the node we want to remove, the node before it and the node after it
- remove the connections from the node to remove to other nodes
- update the connections from the node before the node to remove
- update the connections from the node after the node to remove
- decrease length by 1
- return node
Example
// current list:
A <===> B <===> C
// desired list:
A <===> C
Steps:
// current list:
A <===> B <===> C
// remove the connections from the node to remove to other nodes
A ==> B <== C
// update the connections from the node before the node to remove
A ==> C // A.next to C instead of B
B <== C // C.prev to B, still
// update the connections from the node after the node to remove
A <===> C // finally, C.prev to A instead of B
// desired list:
A <===> C
=> list after last step equals the desired list
Implementation (Short)
class Node {
constructor(value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.length = 0;
this.head = null;
this.tail = null;
}
push(value) {
const newNode = new Node(value);
if (!this.length) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
this.length += 1;
return newNode;
}
shift() {
if (!this.length) {
return null;
}
const nodeToRemove = this.head;
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
this.head = nodeToRemove.next;
this.head.prev = null;
nodeToRemove.next = null;
}
this.length -= 1;
return nodeToRemove;
}
pop() {
if (!this.length) {
return null;
} else {
const nodeToRemove = this.tail;
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
this.tail = this.tail.prev;
this.tail.next = null;
nodeToRemove.prev = null;
}
this.length -= 1;
return nodeToRemove;
}
}
get(index) {
if (!this.length || index < 0 || index >= this.length) {
return null;
} else {
let currentNode;
if (index < this.length / 2) {
let counter = 0;
currentNode = this.head;
while (counter < index) {
currentNode = currentNode.next;
counter += 1;
}
} else {
let counter = this.length - 1;
currentNode = this.tail;
while (counter > index) {
currentNode = currentNode.prev;
counter -= 1;
}
}
return currentNode;
}
}
remove(index) {
// if the index is invalid, return null
if (!this.length || index < 0 || index >= this.length) {
return null;
} else if (index === 0) {
// if we want to remove the first node
return this.shift();
} else if (index === this.length - 1) {
// if we want to remove the last node
return this.pop();
} else {
// store the node we want to remove, the node before it and the node after it
const nodeToRemove = this.get(index);
const prevNodeToRemove = nodeToRemove.prev;
const nextNodeToRemove = nodeToRemove.next;
// remove the connections from the node to remove to other nodes
nodeToRemove.prev = null;
nodeToRemove.next = null;
// update the connections from the node before the node to remove
prevNodeToRemove.next = nextNodeToRemove;
// update the connections from the node after the node to remove
nextNodeToRemove.prev = prevNodeToRemove;
// decrease length by 1
this.length -= 1;
// return node
return nodeToRemove;
}
}
}
Result
Let's have a look how to use the Doubly Linked List's remove method and its results.
const newDLL = new DoublyLinkedList();
newDLL.push("new 0");
newDLL.push("new 1");
newDLL.push("new 2");
// should be a list with 3 nodes
console.log(newDLL);
// DoublyLinkedList {
// length: 3,
// head: <ref *1> Node {
// value: 'new 0',
// prev: null,
// next: Node { value: 'new 1', prev: [Circular *1], next: [Node] }
// },
// tail: <ref *2> Node {
// value: 'new 2',
// prev: Node { value: 'new 1', prev: [Node], next: [Circular *2] },
// next: null
// }
// }
// index invalid
console.log(newDLL.remove(-1));
// null
// index invalid
console.log(newDLL.remove(5));
// null
// should be new 0
console.log(newDLL.remove(0));
// Node { value: 'new 0', prev: null, next: null }
// should be new 2 (we deleted new 0)
console.log(newDLL.remove(1));
// Node { value: 'new 2', prev: null, next: null }
// should be a list with 1 node (we deleted 2 nodes from the initial 3 node list)
console.log(newDLL);
// DoublyLinkedList {
// length: 1,
// head: Node { value: 'new 1', prev: null, next: null },
// tail: Node { value: 'new 1', prev: null, next: null }
// }
Next Part
We will do a small recap of our Doubly Linked List.
If you want to get notified, subscribe!
Top comments (0)