Intro
Last time, we learned how to add data to the end of our Doubly Linked List.
Today, we'll learn how to pop data from the end of our Doubly Linked List.
Starter Code
We start with the code from the last post, 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:
- return null
If the list has one node:
- save current tail (to return it later)
- set the head and the tail to null
- decrease length by 1
- return the old tail
All remaining cases:
- save current tail (to return it later)
- set the node before the current tail as the new tail
- remove the connection from the new tail to the old tail
- remove the connection from the old tail to the new tail
- decrease length by 1
- return old tail
Differences:
- we can see some duplication (save current tail, decrease length, return node)
Example: three nodes
// current list:
A <===> B <===> C (tail)
// desired list:
A <===> B (tail)
Steps:
// current list:
A <===> B <===> C (tail)
// set the node before the current tail as the new tail:
A <===> B (tail) <===> C
// remove the connection from the new tail to the old tail:
A <===> B (tail) <== C
// remove the connection from the old tail to the new tail:
A <===> B (tail) C (not connected to list anymore)
// desired list:
A <===> B (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;
}
pop() {
// if empty: return null
if (!this.length) {
return null;
} else {
// save current tail (to return it later)
const nodeToRemove = this.tail;
if (this.length === 1) {
// after removing the only node, there will be no head and tail
this.head = null;
this.tail = null;
} else {
// set the node before the current tail as the new tail
this.tail = this.tail.prev;
// remove the connection from the new tail to the old tail
this.tail.next = null;
// remove the connection from the old tail to the new tail
nodeToRemove.prev = null;
}
// decrease length by 1
this.length -= 1;
// return old tail
return nodeToRemove;
}
}
}
Result
Let's have a look how to use the Doubly Linked List's pop method and its results.
// create new list and add three nodes
const newDLL = new DoublyLinkedList();
newDLL.push("A");
newDLL.push("B");
newDLL.push("C");
console.log(newDLL);
// DoublyLinkedList {
// length: 3,
// head: <ref *1> Node {
// value: 'A',
// prev: null,
// next: Node { value: 'B', prev: [Circular *1], next: [Node] }
// },
// tail: <ref *2> Node {
// value: 'C',
// prev: Node { value: 'B', prev: [Node], next: [Circular *2] },
// next: null
// }
// }
console.log(newDLL.pop());
// Node { value: 'C', prev: null, next: null }
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
// }
// }
Next Part
We will implement our next method for the Doubly Linked List: unshift / add data to the beginning.
If you want to get notified, subscribe!
Top comments (0)