Intro
Last time, we learned how to unshift / add data to the beginning of our Doubly Linked List.
Today, we'll learn how to shift / remove data from the beginning of our Doubly Linked List.
Starter Code
We start with code that has the push method, because to remove data, we first have to add data.
class Node {
constructor(value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.length = 0;
this.head = null;
this.tail = null;
}
push(value) {
const newNode = new Node(value);
if (!this.length) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
this.length += 1;
return newNode;
}
}
Thoughts
First, we should think about the constraints and possibilities:
If the list is empty:
- we can't remove data from an empty list, therefore we return
null
If the list has 1 element:
- set head as nodeToRemove
- after removing the only element, the list will be empty, so
headandtailshould benull - decrease length by 1
- return nodeToRemove
All remaining cases:
- set head as nodeToRemove
- the node after the nodeToRemove should become the new head
- remove both connections from the new head to the old head (our nodeToRemove)
- decrease length by 1
- return nodeToRemove
Differences:
- we can see some duplication (set head as nodeToRemove, decrease length, return nodeToRemove)
Example:
// current list:
A (head) <===> B (tail)
// desired list:
B (head & tail)
Steps:
// current list:
A (head) <===> B (tail)
// the node after the nodeToRemove should become the new head
A <===> B (head & tail)
// remove both connections from the new head to the old head (our nodeToRemove)
A B (head & tail)
// desired list:
B (head & tail)
=> list after last step equals the desired list
Implementation (Short)
class Node {
constructor(value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.length = 0;
this.head = null;
this.tail = null;
}
push(value) {
const newNode = new Node(value);
if (!this.length) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
this.length += 1;
return newNode;
}
shift() {
// we can't remove data from an empty list
if (!this.length) {
return null;
}
// set head as nodeToRemove
const nodeToRemove = this.head;
if (this.length === 1) {
// after removing the only element, the list will be empty, so `head` and `tail` should be `null`
this.head = null;
this.tail = null;
} else {
// the node after the nodeToRemove should become the new head
this.head = nodeToRemove.next;
// remove both connections from the new head to the old head (= nodeToRemove)
this.head.prev = null;
nodeToRemove.next = null;
}
// decrease length by 1
this.length -= 1;
// return nodeToRemove
return nodeToRemove;
}
}
Result
Let's have a look how to use the Doubly Linked List's shift method and its results.
const newDLL = new DoublyLinkedList();
newDLL.push("A");
newDLL.push("B");
// should show two nodes
console.log(newDLL);
// DoublyLinkedList {
// length: 2,
// head: <ref *1> Node {
// value: 'A',
// prev: null,
// next: Node { value: 'B', prev: [Circular *1], next: null }
// },
// tail: <ref *2> Node {
// value: 'B',
// prev: <ref *1> Node {
// value: 'A',
// prev: null,
// next: [Circular *2]
// },
// next: null
// }
// }
// should show node with value A
console.log(newDLL.shift());
// Node { value: 'A', prev: null, next: null }
// should show one node left, B
console.log(newDLL);
// DoublyLinkedList {
// length: 1,
// head: Node { value: 'B', prev: null, next: null },
// tail: Node { value: 'B', prev: null, next: null }
// }
Next Part
We will implement our next method for the Doubly Linked List: get / get a specific node by its index.
If you want to get notified, subscribe!
Top comments (0)