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
head
as 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
tail
tonull
, because the List is empty now - return the
nodeToRemove
If there is more than 1 node in the Singly Linked List:
- set the current
head
as 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