DSA #3: Doubly Linked Lists
In our previous post in this data structures and algorithms series, we discussed linked lists, particularly singly-linked lists, In this one, we will discuss doubly Linked and how to implement that in javaScript.
According to the illustration above the main difference between a singly linked list and a doubly-linked list is that in a doubly each node contains two references, a reference to the next node and a reference to the previous node. For the first node, the reference toward the previous node is null and for the last node (tail), the reference toward the next node is also equal to null.
Creating the doubly linked list class
The doubly linked list is very similar to the singly linked list. The only difference between both is that a doubly linked list has the previous pointer in each node.
First, you need to create a class for each node:
Next, create the DoublyLinkedList class as follows:
Notice that the tail is the last node of our doubly linked list. When you are creating a new list, head and tail are equal to null.
Insert a new node at the end of list
The code above shows how to add a new element to a doubly-linked list. The tail is the last element of our list we check if the tail exists, if so, the new node that we are adding should become the new tail, we make the next reference of the tail to point toward the new node. And if the current node is our new tail, her previous point should point toward the old tail.
if the tail doesn’t exist we assume it's the first node we are creating and the head and the tail point to this new node.
Insert new at the start of the list
We make the new node our new head by making the head point toward him, and by making the next referenceof the new node point toward the old head.
Insert new at a given position
The code above shows us at to insert an element at a given index. Firstly to optimize our operation we check the index — If the index is 1 call insertAtStart, and when the index is equal to the length of the doubly linked list call insertAtEnd. If the index isn’t equal to both of them we traverse the whole by incrementing the count variable that counts the number of nodes and by saving the node previous node to our actual node. When the count will equal to the index we stop the traversal. In the current variable, we have the node that should be after the new node. We make the prev referenceof the new node point towards prev and his next referencepoint towards the current. Since the current node should be after the node that we are adding, we make his pre referencepoint toward the new Node. Finally, we make the next referenceof the prev point towards the new node and increment the length of the list.
remove the first element
We are removing the first element, we make the head point toward the second element of the list.
remove the last element
We are removing the last element, the tail is our current last element, we point toward null the element previous to the tail because it will become the new tail and a tail doesn’t have an element after him then we make the previous element our new tail.
remove at a given index
Let's wrap everything together and add a print method for printing the whole list.
Now the DoublyLinkedList is complete, we can perform operations
The console output should be like this:
We are at the end of this article, hope you find something useful for your learning journey. See you in the post of this series.
The Nothing 🔺
