Implement a doubly linked list in TypeScript
In a doubly linked list each node in the list stores the contents of the node and a pointer or reference to the next and the previous nodes in the list. It is one of the simplest way to store a collection of items.
In this lesson we cover how to create a doubly linked list data structure and how to use its strengths to implement an O(1) FIFO queue + O(1) LIFO stack. We also demonstrate why one would use it over a singly linked list. We also cover how to approach authoring such data structures.
[00:01] Here, we have a singly linked list with a First-In-First-Out dequeue method. Now, let's go ahead and add a Last-In-First-Out pop operation. Like dequeue, it will return T or undefined. Purely care if we have a tail, and we load the value from the current tail. Now, we have to update the tail to be the second last item in the linked list.
[00:30] To find that in this singly linked list, we would need to start from the head to be arrive at the node whose next is the current tail. However, such an implementation would be O(n), and we want an O(1) algorithm for the pop method.
[00:48] There is a data structure called doubly linked list that will make it preview to figure out the second last node. That is the node previous to the current tail. Instead of just value and next, we also keep track of any previous node against each node.
[01:06] Of course, for the head the previous will be undefined and for the tail, next will be undefined. Let's make this node description concrete and define a doubly linked list node. We are going to declare it as a generic interface that holds a value, and potentially the next as well as the previous nodes.
[01:31] You will have to add a very slight additional maintenance for this new prev node reference. On at, you will create a doubly linked list node, and therefore also initialize the previous value to be undefined when you create this new node.
[01:49] Additionally if you have a current tail, we continue to update the next pointer. Now, we also update the previous pointer for this new node. The modifications to the dequeue operation are equally simple. After dequeuing the current head, if you get a new head value, you simply need to clear the previous reference.
[02:12] Now with these simple modifications in place, let's revisit adding a Last-In-First-Out pop operation. After grabbing the value from the current tail, we simply update the tail to point to the current tail's previous node.
[02:28] If the tail will be no more, we also clear the head. Otherwise, we update this new tail to have no next, essentially popping the whole tail. Finally, we return the value we write from the whole tail. It is worth mentioning that as long as you understand what a node means in your data structure, and appreciate the fact that you need to maintain value, previous, and next members, we don't need to memorize the code bodies.
[02:57] An interesting fact in this doubly linked list is that a pop method is actually a straight copy of the dequeue operation, and the simple change of a head to tail, previous to next, and next to previous.
[03:12] The main advantage of using a doubly linked list is that, any operations that require constant next imprev reference manipulations can be implemented with O(1) time complexity. In this example, it allowed us to implement a FIFO queue and a LIFO stack operation in a single data structure with an O(1) time complexity.