Intro
Last time, we learned how to pop / remove data from end of our Doubly Linked List.
Today, we'll learn how to unshift / add data to the beginning of our Doubly Linked List.
Starter Code
We start with the setup code.
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;
}
}
Thoughts
First, we should think about the constraints and possibilities:
If the list is empty:
- create a new node
- set the new node as the new head and tail
- increase length by 1
- return the new node
All remaining cases:
- create a new node
- set new node's next to current head
- set the current head's prev to new node
- set list's head to new node
- increase length by 1
- return the new node
Differences:
- we can see some duplication (create node, increase length, return node)
Example: three nodes
// current list:
A (head) <===> B (tail)
// desired list:
0 (head) <===> A <===> B (tail)
Steps:
// current list:
A (head) <===> B (tail)
// set new node's next to current head
0 ==> A (head) <===> B (tail)
// set the current head's prev to new node
0 <===> A (head) <===> B (tail)
// set list's head to new node
0 (head) <===> A <===> B (tail)
// desired list:
0 (head) <===> 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;
}
unshift(value) {
// create new node
const newNode = new Node(value);
// if list is empty: set head and tail to new node
if (!this.length) {
this.head = newNode;
this.tail = newNode;
} else {
// set new node's next to current head
newNode.next = this.head;
// set the current head's prev to new node
this.head.prev = newNode;
// set list's head to new node
this.head = newNode;
}
// increase length by 1
this.length += 1;
// return new node
return newNode;
}
}
Result
Let's have a look how to use the Doubly Linked List's unshift method and its results.
const newDLL = new DoublyLinkedList();
newDLL.push("A");
// should be a list with one node
console.log(newDLL);
// DoublyLinkedList {
// length: 1,
// head: Node { value: 'A', prev: null, next: null },
// tail: Node { value: 'A', prev: null, next: null }
// }
// should be the new node
console.log(newDLL.unshift("0"));
// <ref *1> Node {
// value: '0',
// prev: null,
// next: Node { value: 'A', prev: [Circular *1], next: null }
// }
// should be a list with two nodes, node with value 0 at the beginning
console.log(newDLL);
// DoublyLinkedList {
// length: 2,
// head: <ref *1> Node {
// value: '0',
// prev: null,
// next: Node { value: 'A', prev: [Circular *1], next: null }
// },
// tail: <ref *2> Node {
// value: 'A',
// prev: <ref *1> Node {
// value: '0',
// prev: null,
// next: [Circular *2]
// },
// next: null
// }
// }
Next Part
We will implement our next method for the Doubly Linked List: shift / remove data from the beginning.
If you want to get notified, subscribe!
Top comments (0)