JavaScript Data Structures: Linked Lists (pt. 3)
Last week, I discussed how to implement the most common/typical linked list — the singly linked list. This week, I’ll be going over how to implement another version of a linked list — the doubly linked list. Then, I’ll be going over a popular algorithm problem utilizing a singly linked list, disguised as a doubly linked list!
Implementing a Doubly Linked List Node
Similar to a singly linked list node, a node in a doubly linked list contains both a data value and a next value. However, they also contain a previous value, pointing to the data previous to the current node in the list. The previous value will also point to null, like the next value, because at time of initialization of a node, you do not know what comes previously or directly after.
class DoublyLinkedListNode {
constructor(data) {
this.data = data;
this.next = null;
this.prev = null;
}
}Implementing a list is the same as a singly linked list, so I won’t be going over it again. However, to get a list initialized, there are a few steps you have to take.
// creating the first node - the head; initialize linked list
let node1 = new DoublyLinkedListNode(1);
let doublyList = new LinkedList(node1); // the head will be node1// creating a second node
let node2 = new DoublyLinkedListNode(2);
node1.next = node2; // sets the 'next' val of node1 to node2
node2.prev = node1; // sets the 'prev' val of node2 to node1// creating a third node; the tail in this example
let node3 = new DoublyLinkedListNode(3);
node2.next = node3; // sets the 'next' val of node2 to node3
node3.prev = node2; // sets the 'prev' val of node3 to node2
Reversing a Linked List
This LeetCode challenge is a common Linked List problem. The challenge asks: “Given the head of a singly linked list, reverse the list, and return the head of the reversed list.”
To start, we will basically be mimicking a doubly linked list using the singly linked list. We’ll keep track of each value by initializing a current, next, and previous pointer.
The current will be set as the head of the linked list and be used to keep track of what node we’re currently on. The next will initially be set to null but will keep track of the next node. The previous will also initially be null as singly linked lists do not have a previous pointer but will keep track of the previous node to the current node.
Then, we will iterate through each node to traverse the list. During this iteration, we will be doing the following things:
- Set next to current.next — this will store the next node of the current node
- Set current.next equal to previous — this will allow us to start the reversing process and change next of current.
- Set previous to current — this will move the previous node forward
- Set current equal to next — this will then move the current step forward
Then, we will repeat these four steps during each iteration.
Finally, once the iteration of the list is complete, we will then have to return the head of the list — however, because we reversed the list, the head is now the last node, so we will actually have to return previous.
var reverseList = function(head) {
let previous = next = null;
let current = head; while (current !== null) {
next = current.next
current.next = previous
previous = current
current = next
} return previous
};
I found this graphic from this blog post that helped me understand this challenge that visually goes through each step so you can better see what is happening in each step.
And there you have it! It’s a bit complicating at first, but the graphic really helped me understand what is going on in each step.
Again, here are some LeetCode challenges to try regarding linked lists (from easy → medium → hard):
