Intro
Last time, we learned how to unshift / add something to the beginning of our Singly Linked List.
Today, we learn how to shift something from the list. Shift means remove something from the beginning.
Current Code
We start with the code after we added push(), because we want to keep the code as simple as possible to understand. We need push() to add some nodes to the List.
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 anything from the beginning of the Singly Linked list
If there is 1 node in the Singly Linked List:
- set the current
headas the node we want to remove (nodeToRemove) - set the the 2nd node as the new
head - decrease the List's length by 1
- set the
tailtonull, because the List is empty now - return the
nodeToRemove
If there is more than 1 node in the Singly Linked List:
- set the current
headas the node we want to remove (nodeToRemove) - set the the 2nd node as the new
head - decrease the List's length by 1
- return the
nodeToRemove
Examples:
- 0 nodes: before: null (head & tail) => after: null (head & tail) (couldn't remove anything)
- 1 node: before: A (head & tail) => after: null (head & tail)
- n nodes: before: A (head) -> B -> ... -> n (tail) => after: B (head) -> ... -> n (tail)
Differences:
- there is only one difference: an additional step if there's only 1 node in the List
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() {
// we can't remove anything from an empty List
if (!this.length) {
return null;
} else {
// set the current `head` as the node we want to remove (`nodeToRemove`)
const nodeToRemove = this.head;
// set the 2nd node as the new `head`
this.head = this.head.next;
// decrease the List's length by 1
this.length -= 1;
// if the List is empty now, there isn't a tail anymore
if (!this.length) {
this.tail = null;
}
// return the `nodeToRemove`
return nodeToRemove;
}
}
}
Result
Let's have a look how to use the Singly Linked List shift method and its results.
const newSLL = new SinglyLinkedList();
// we can't remove from an empty list
console.log(newSLL.shift());
// add one node and remove it
newSLL.push("1st node");
console.log(newSLL.shift()); // Node { value: '1st node', next: null }
console.log(newSLL); // SinglyLinkedList { length: 0, head: null, tail: null }
// add two nodes and remove the first
newSLL.push("new 1st node");
newSLL.push("2nd node");
console.log(newSLL);
// SinglyLinkedList {
// length: 2,
// head: Node {
// value: 'new 1st node',
// next: Node { value: '2nd node', next: null }
// },
// tail: Node { value: '2nd node', next: null }
// }
console.log(newSLL.shift());
// Node {
// value: 'new 1st node',
// next: Node { value: '2nd node', next: null }
// }
console.log(newSLL);
// SinglyLinkedList {
// length: 1,
// head: Node { value: '2nd node', next: null },
// tail: Node { value: '2nd node', next: null }
// }
Next Part
We will implement how to get a specific node by its index. If you want to be notified, subscribe :)
Questions:
- Any ideas how to improve the post or code?
- Any specific questions?
Top comments (2)
Thanks for your work, just one thing I see which I find unnecessary is the else block after even though you are already returning above.
Been following along with this as I really needed a refresher on my data structures which I skipped / barely implemented all those years ago at uni!
Implemented a demo her using closures / functions rather than classes, for people to browse a live version of the code: runkit.com/ortonomy/linkedlist-v1