You can see the previous post, Singly Linked List here.
Welcome back! The next data structure we will look at is the Doubly Linked List. This is very similar to the Singly Linked List, except every node has another pointer, previous, which points to the node ahead of it. This adds the ability to work backwards in our list, as opposed to only be able to move forward with next. Let's take a look at the methods.
push
We will add a node to the end of the list. If this is the first node added, it will become the head and the tail. Otherwise, point the current tail's next to be the new node, point the new node's previous to the tail and make the new node the tail.
push(value: ValueType): DoublyLinkedList {
const node = new Node(value);
if (this.length === 0) {
this.head = node;
} else {
this.tail!.next = node;
node.previous = this.tail;
}
this.tail = node;
this.length++;
return this;
}
pop
Remove the node at the end of the list and return its value. This will work much like the pop method on a singly linked list, but we do need to be careful about previous. We can grab the tail, set its previous node to be the new tail, set the new tail's next to null. Also be sure to set the previous of the old tail to null and return its value.
pop(): ValueType | undefined {
if (this.length === 0) {
return undefined;
}
const removedTail = this.tail;
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
this.tail = removedTail!.previous;
this.tail!.next = null;
removedTail!.previous = null;
}
this.length--;
return removedTail!.value;
}
shift
Here we want to remove the head of the list and return its value. Be sure to set the head's next node as the new head, and set its previous to null. Set the old head's next to null and return its value. If there are no nodes in the list when it is called, we will return undefined. If the head was the only node in the list, set the head and tail of the list to null.
shift(): ValueType | undefined {
if (this.length === 0) {
return undefined;
}
const removedHead = this.head;
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
this.head = removedHead!.next;
this.head!.previous = null;
removedHead!.next = null;
}
this.length--;
return removedHead!.value;
}
unshift
This method will add a node to the beginning of the list. If the list is empty, we can just set the head and tail to be the new node. Otherwise, we will set the previous of the current list head to be the new node, set the new node as the head, and set its next to be the old head.
unshift(value: ValueType): DoublyLinkedList {
const node = new Node(value);
if (this.length === 0) {
this.head = node;
this.tail = node;
} else {
this.head!.previous = node;
node.next = this.head;
this.head = node;
}
this.length++;
return this;
}
get
I think this method really shines compared to its singly linked list counterpart. In the singly linked list we could only loop from the head; but not that we have previous pointers, we can decided to loop from the tail. We can do this by finding the middle of the list (length divided by 2), and pick our start point based on the index we are looking for. Typically, if the index is less than the midpoint, we should start from the head (counting up and using next), and if the index is greater than the midpoint, we should start from the tail(counting down and using previous). If the index is out of the range, we will return null.
get(index: number): NodeType | null {
if ( index < 0 || index >= this.length) {
return null;
}
const middle = Math.floor(this.length / 2);
let currentNode = null;
if (index <= middle) {
currentNode = this.head;
let i = 0;
while(i !== index) {
currentNode = currentNode!.next;
i++;
}
} else {
currentNode = this.tail;
let i = this.length - 1;
while(i !== index) {
currentNode = currentNode!.previous;
i--;
}
}
return currentNode;
}
set
Here we can use our get method again, set the value of the node retrieved and return true. If the node is not found by get, we cannot set a value, so we will return false.
set(index: number, value: ValueType): boolean {
const node = this.get(index);
if (node !== null) {
node!.value = value;
return true;
}
return false;
}
insert
With insert we want to insert a node at a given index, so we can reuse our get method here as well. There are a few edge cases though. If the given index is less than 0 or greater than the length, we will return false. If the index is 0, we can use our unshift method; and if the index is equal to the length, we can use push. Otherwise, use the get method to get the node at index - 1 (previous node), set the new node's next to previous node's next. Set new node's next previous to be the new node. Set previous node's next to be the new node, and set the new node's previous to be previous node. Return true.
insert(index: number, value: ValueType): boolean {
if (index < 0 || index > this.length) {
return false;
} else if (index === 0) {
this.unshift(value);
} else if (index === this.length) {
this.push(value);
} else {
const prevNode = this.get(index - 1);
const node = new Node(value);
node!.next = prevNode!.next;
prevNode!.next!.previous = node;
node!.previous = prevNode;
prevNode!.next = node;
this.length++;
}
return true;
}
remove
Here we want to remove a node at a given index. The edge cases for remove are similar to insert. If the index is less than 0, or the index is greater than or equal to the length, return undefined. We can also reuse some of our other methods. If the index is 0, use shift, if the index is length - 1, use pop. Otherwise, use the get method to retrieve the item to be removed. On the removed node's previous node, update its next to be the removed node's next, and update the removed node's next previous to be the removed node's previous. Set the next and previous on the removed node to be null, then return its value.
remove(index: number): ValueType | undefined {
if (index < 0 || index >= this.length) {
return undefined;
} else if (index === 0) {
return this.shift();
} else if (index === this.length - 1) {
return this.pop();
} else {
const node = this.get(index);
node!.previous!.next = node!.next;
node!.next!.previous = node!.previous;
this.length--;
return node!.value;
}
}
reverse
Let's reverse a doubly linked list in place! First, save the head and tail into variables respectively (I used currentNode and tail). Loop through the list. On each iteration, get the current node's next and save it in a variable, set the current node's next to the current node's previous, set the current node's previous to next, then, set the current node to next. After the loop, set the tail for the head, and the head to tail (the one we stored before the loop). Return the list.
reverse(): DoublyLinkedList {
let currentNode = this.head;
let tail = this.tail;
while (currentNode !== null) {
const next = currentNode!.next;
currentNode!.next = currentNode!.previous;
currentNode!.previous = next;
currentNode = next;
}
this.tail = this.head;
this.head = tail;
return this;
}
And there we have it, another list that works very similarly to the singly linked list, but with the added power of being able to move forwards and backwards within it. You can see al the code in the repo.
Ok, that's it for doubly linked list, in the next post we will look at stacks and queues.