Intro
Last time, we learned to enqueue a node to the end of the Queue.
Today, we learn how to dequeue / remove a new node from the start of the Queue.
Starter Code ▶️
We start with the code with the enqueue method.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Queue {
constructor() {
this.length = 0;
this.start = null;
this.end = null;
}
enqueue(value) {
const newNode = new Node(value);
if (!this.length) {
this.start = newNode;
this.end = newNode;
} else {
this.end.next = newNode;
this.end = newNode;
}
this.length += 1;
return newNode;
}
}
Thoughts 💭
First, we should think about the constraints and possibilities:
If the Queue is empty:
- we can't remove a node
If the Queue has one node:
- set the current start as the node to remove
- set the node after the start as the new start
- set the next node of the node to remove to null
- set the end to null
- decrease the queue's length by 1
- return the node to remove
All remaining cases:
- set the current start as the node to remove
- set the node after the start as the new start
- set the next node of the node to remove to null
- decrease the queue's length by 1
- return the node to remove
Differences:
- we only have to change the end of the queue when we start with one node, because then there is no end left, because the queue will be empty
Example
// current queue:
A (start) ==> B (end)
// desired queue:
B (start, end)
Steps:
// current queue:
A (start) ==> B (end)
// set the node after the start as the new start
A ==> B (start, end)
// set the next node of the node to remove to null
A B (start, end)
// desired queue:
B (start, end)
✅
Implementation 📝
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Queue {
constructor() {
this.length = 0;
this.start = null;
this.end = null;
}
enqueue(value) {
const newNode = new Node(value);
if (!this.length) {
this.start = newNode;
this.end = newNode;
} else {
this.end.next = newNode;
this.end = newNode;
}
this.length += 1;
return newNode;
}
dequeue() {
if (!this.length) {
return null;
} else {
// set the current start as the node to remove
const nodeToRemove = this.start;
// set the node after the start as the new start
this.start = this.start.next;
// set the next node of the node to remove to null
nodeToRemove.next = null;
// set the end to null, if the queue will be empty after removing
if (this.length === 1) {
this.end = null;
}
// decrease the queue's length by 1
this.length -= 1;
// return the node to remove
return nodeToRemove;
}
}
}
Result
Let's have a look how to use the dequeue method and its results.
const newQueue = new Queue();
newQueue.enqueue("new A");
newQueue.enqueue("new B");
// queue with 2 nodes
console.log(newQueue);
// Queue {
// length: 2,
// start: Node { value: 'new A', next: Node { value: 'new B', next: null } },
// end: Node { value: 'new B', next: null }
// }
// remove the start, "new A"
console.log(newQueue.dequeue());
// Node { value: 'new A', next: null }
// 1 node should be left, "new B"
console.log(newQueue);
// Queue {
// length: 1,
// start: Node { value: 'new B', next: null },
// end: Node { value: 'new B', next: null }
// }
// remove the start, "new B"
console.log(newQueue.dequeue());
// Node { value: 'new B', next: null }
// queue should be empty
console.log(newQueue);
// Queue { length: 0, start: null, end: null }
✅
Next Part ➡️
We will do a small recap of our Queue.
Don't miss interesting stuff, subscribe!
Questions ❔
- If we would implement the Queue by using an Array, how would we dequeue the start node?
Top comments (0)