Intro
Last time, we learned how to insert a new node at any a specific index.
Today, we learn how to remove a node at any specific index.
Current Code
We start with code that has push, shift, pop and get, because we can reuse these methods:
-
pushto add some nodes to test the stuff -
shiftto remove at the beginning of the List -
popto remove at the end of the List -
getto get a specific node
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.length = 0;
this.head = null;
this.tail = null;
}
push(value) {
const newNode = new Node(value);
if (!this.length) {
this.head = newNode;
} else {
this.tail.next = newNode;
}
this.tail = newNode;
this.length += 1;
return newNode;
}
shift() {
if (!this.length) {
return null;
} else {
const nodeToRemove = this.head;
this.head = this.head.next;
this.length -= 1;
if (!this.length) {
this.tail = null;
}
return nodeToRemove;
}
}
pop() {
if (!this.tail) {
return null;
} else {
let currentNode = this.head;
let preTail = this.head;
while (currentNode.next) {
preTail = currentNode;
currentNode = currentNode.next;
}
this.tail = preTail;
this.tail.next = null;
this.length -= 1;
if (!this.length) {
this.head = null;
this.tail = null;
}
return currentNode;
}
}
get(index) {
if (index < 0 || index >= this.length) {
return null;
} else {
let count = 0;
let currentNode = this.head;
while (count < index) {
currentNode = currentNode.next;
count += 1;
}
return currentNode;
}
}
}
Thoughts
First, we should think about the constraints and possibilities:
If we want to remove a node "outside" the List (index is less than 0 or greater than or equal to the length of the current List):
- return null
If we want to remove a node from the beginning of the List (index is 0):
- we can use our
shiftmethod
If we want to remove a node from the end of the List (index is length - 1):
- we can use our
popmethod
All remaining cases:
- find the node before the nodeToRemove
- set the found node's
nextas the nodeToRemove - set the nodeToRemove's
nextas thenextof the node before nodeToRemove
Example:
- current List: A -> B -> C
- we want to remove
B - desired List: A -> C
Steps:
- find the node before
B(=A) - point
A'snexttoB'snext(=C)
Implementation (Short version, DRY)
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.length = 0;
this.head = null;
this.tail = null;
}
push(value) {
const newNode = new Node(value);
if (!this.length) {
this.head = newNode;
} else {
this.tail.next = newNode;
}
this.tail = newNode;
this.length += 1;
return newNode;
}
shift() {
if (!this.length) {
return null;
} else {
const nodeToRemove = this.head;
this.head = this.head.next;
this.length -= 1;
if (!this.length) {
this.tail = null;
}
return nodeToRemove;
}
}
pop() {
if (!this.tail) {
return null;
} else {
let currentNode = this.head;
let preTail = this.head;
while (currentNode.next) {
preTail = currentNode;
currentNode = currentNode.next;
}
this.tail = preTail;
this.tail.next = null;
this.length -= 1;
if (!this.length) {
this.head = null;
this.tail = null;
}
return currentNode;
}
}
get(index) {
if (index < 0 || index >= this.length) {
return null;
} else {
let count = 0;
let currentNode = this.head;
while (count < index) {
currentNode = currentNode.next;
count += 1;
}
return currentNode;
}
}
remove(index) {
// remove a node "outside" the List (=> invalid)
if (index < 0 || index >= this.length) {
return null;
} else if (index === 0) {
// remove a node from the beginning of the List
return this.shift();
} else if (index === this.length - 1) {
// remove a node from the end of the List
return this.pop();
} else {
// find the node before the nodeToRemove
const preNodeToRemove = this.get(index - 1);
// we want to return the removed node later
const nodeToRemove = preNodeToRemove.next;
// set the node after the node to remove (=C) as the new node after the node before the node to remove (=A)
preNodeToRemove.next = nodeToRemove.next; // from A -> B -> C to A -> C
// decrease the List's length by 1
this.length -= 1;
// return the new node
return nodeToRemove;
}
}
}
Result
Let's have a look how to use the Singly Linked List's remove method and its results.
const newSLL = new SinglyLinkedList();
newSLL.push("A");
newSLL.push("B");
newSLL.push("C");
console.log(newSLL);
// SinglyLinkedList {
// length: 3,
// head: Node { value: 'A', next: Node { value: 'B', next: [Node] } },
// tail: Node { value: 'C', next: null }
// }
console.log(newSLL.remove(1));
// Node { value: 'B', next: Node { value: 'C', next: null } }
console.log(newSLL);
// SinglyLinkedList {
// length: 2,
// head: Node { value: 'A', next: Node { value: 'C', next: null } },
// tail: Node { value: 'C', next: null }
// }
Conclusion
We did it. Our Singly Linked List can do a lot of stuff.
If you want to learn something new, here are some ideas:
- Write your own implementation of the methods
- Add checks to prevent wrong user inputs (e.g. text as index)
- Write a test suite
- Add a graphical user interface
- ???
Top comments (0)