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:
- push to add some nodes to test the stuff
- shift to remove at the beginning of the List
- pop to remove at the end of the List
- get to 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 = this.length] {
return null;
} else {
let count = 0;
let currentNode = this.head;
while [count B -> Cwe want to remove B desired List: A -> C
Steps:
- find the node before B [=A]
- point A's next to B's next [=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 = this.length] {
return null;
} else {
let count = 0;
let currentNode = this.head;
while [count invalid]
if [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;
}
}
}
Enter fullscreen mode Exit fullscreen mode
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 }
// }
Enter fullscreen mode Exit fullscreen mode
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
- ???