As I continue to study data structures and algorithms, I am finding that writing things out is helping to improve my understanding of data structures and a few ways to manipulate the data in them. I will use this series to discuss Doubly Linked Lists, and use illustration, followed by example code, to lay out my understanding of a few methods.
Doubly Linked Lists are similar to Singly Linked Lists. If you are looking for an explanation on Singly Linked Lists, you can take a look at my posts on that. One key difference with Doubly Linked Lists is that they have a pointer that references the previous node. Also, they take up more memory however that comes with more flexibility because you are not confined to traversing the list in one direction only.
Building a Node class for Doubly Linked Lists is similar to building a Node class for Singly Linked Lists and the only difference is adding a previous pointer. A node is an object with a key-value pair and will look like this: {value: value, next: null, prev: null}. Here is an illustration of nodes referencing each other:
Here is an example of code that builds the node:
A Doubly Linked List class creates the structure for the list. It includes the head, tail, and length properties. Here is an example of code that builds the Doubly Linked List:
These two classes are used to instantiate a list. Within the Doubly Linked List class, various methods can be written. I will share two methods: push() and pop(). When you are looking to add a node to the end of a list, you can create a push() method. This method takes a parameter to create a new node that is added to the end of the list. Here is an illustration of that method:
Edge case: you can account for an empty list. If it is not empty, then follow the steps mentioned above.
Here is an example code for a push() method:
A pop() method removes a node from the end of a Doubly Linked List. A parameter is not needed for this method. Below is an illustration:
Edge cases: account for if the list is empty, or has only one node. If neither of those cases applies, then follow the steps illustrated above.
Here is an example code for a pop() method:
The time complexity for push() and pop() methods in a Doubly Linked List will be O(1) constant time because the number of operations does not increase as the length of the list increase.
Next week I will share what I have learned about creating shift() and unshift() methods. As always, the learning process is ongoing, so feel free to share your comments if I got anything incorrect. 😀
Top comments (0)