Intro
Last time, we learned how to push a new node to the end of our Singly Linked List.
Today, we learn how to pop something from the list. Pop means remove something from the end.
Current Code
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 > 0) {
this.tail.next = newNode;
} else {
this.head = newNode;
}
this.tail = newNode;
this.length += 1;
return newNode;
}
}
Thoughts
First, we should think about the constraints and possibilities:
If there is currently NO other node in the Singly Linked List (so it is currently empty):
- return
null, because we can't remove a node
If there is 1 node in the Singly Linked List:
- find the second to last node (it should become the new tail)
- set its
nexttonull - set it as
tail - decrease the Singly Linked List's
lengthby 1 - set the Singly Linked List's
headandtailtonull, because it is empty now - return the popped node
If there is more than 1 node in the Singly Linked List:
- find the second to last node (it should become the new tail)
- set its
nexttonull - set it as
tail - decrease the Singly Linked List's
lengthby 1 - return the popped node
Examples:
- 0 nodes: before: null (head & tail) => after: null (head & tail)
- 1 node: before: A (head & tail) => after: null (head & tail)
- 2 nodes: before: A (head) -> B (tail) => after: A (head & tail)
- n nodes: before: A (head) -> ... -> n-1 -> n (tail) => after: A (head) -> ... -> n-1 (tail)
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;
}
pop() {
// no node in the list, therefore return null
if (!this.length) {
return null;
} else {
/*
* find the second to last node (it should become the new tail):
* - set the current head as currentNode (we always have to start from the List's head node)
* - set the current head as secondToLastNode (we can't go back a node, therefore we have to save the second to last)
* - as long as the current node has a next node (so it is not the last node)
* - then set the current node to the second to last
* - then set the current node's `next` as the current node
*/
let currentNode = this.head;
let secondToLastNode = this.head;
while (currentNode.next) {
secondToLastNode = currentNode;
currentNode = currentNode.next;
}
// set the second to last node's `next` to `null` (the second to last should "cut" its connection to the next node)
secondToLastNode.next = null;
// set it as `tail`
this.tail = secondToLastNode;
// decrease the Singly Linked List's `length` by 1
this.length -= 1;
// if the Singly Linked List now is empty, set its `head` and `tail` to `null`
if (!this.length) {
this.head = null;
this.tail = null;
}
// return the popped node (found some lines above)
return currentNode;
}
}
}
Result
Let's have a look how to use the Singly Linked List pop method and its results.
const newSLL = new SinglyLinkedList();
newSLL.push("1");
newSLL.push("2");
console.log(newSLL);
/* SinglyLinkedList {
* length: 2,
* head: Node { value: '1', next: Node { value: '2', next: null } },
* tail: Node { value: '2', next: null }
* }
*/
console.log(newSLL.pop()); // Node { value: '2', next: null }
console.log(newSLL.pop()); // Node { value: '1', next: null }
console.log(newSLL.pop()); // null
console.log(newSLL); // SinglyLinkedList { length: 0, head: null, tail: null }
Next Part
We will implement how to add a node to the beginning of the Singly Linked List. If you want to be notified, subscribe :)
Top comments (0)