This post will conclude what I have learned about creating various methods within a Doubly Linked List. The methods that I will be discussing today build off of methods outlined in previous blog posts for this series. The previous methods needed to support the methods that I will be discussing today include get(), unshift() and shift(), and push() and pop(). Beginning with insert(), this method adds a node at a specified index. This method takes in two parameters (index and value), and calls on unshift(), push(), and get() methods to support it. Here is a visualization for creating this method:
Edge case 1: if the index is a negative number or greater than the length of the list, you can return false because that index is not valid.
Edge case 2: if the index is equal to zero, you can use the unshift() method to place a node at the start of the list.
Edge case 3: if the index is equal to the lists' length, you can use the push() method to place a new node at the end of the list.
If none of the above cases apply, then you can follow the steps outlined above.
Here is an example of code for an insert() method:
Next, the remove() method will remove a node at a specified index. This method takes one parameter (index) and makes use of shift() and pop() methods to support it. Below is a visualization for this method:
Edge case 1: if the index is a negative number or greater than or equal to the length, you can return undefined because the index passed is not valid.
Edge case 2: if the index is equal to zero, you can use the shift() method to remove a node from the start of the list.
Edge case 3: if the index is equal to the last index of the list, you can use the pop() method to remove the last node.
If none of the above cases apply, then you can follow the steps outlined above.
Here is an example of code for a remove() method:
Finally, this reverse() method will reverse a list in place and takes no parameters. This method works by swapping the head and tail, and changing the directions of the previous and next pointers. Below is an illustration:
Here is an example of code for a reverse() method:
The time complexity for these methods is O(1) constant time if insertion and removal occur at the start or end of the list because the number of operations remains the same. Otherwise, time complexity will be O(n) linear time because you will need to loop through the list to insert or remove at the middle, and the number of operations increases as the list's length increase. The reverse method is also O(n) linear time. Hopefully, others find this representation of the code helpful as it has been for me. There is so much to learn so please feel free to share comments or corrections if I have anything incorrect or missed anything. 🙂
Top comments (0)