When I was a computer science student my two favorite classes were databases and data structures. Since starting my professional work as a web programmer I have not found my use cases for the data structures I learned in college until recently. So, today I want to talk about the data structure known as a Doubly Linked List and show you a use case for it that I have recently found.
What is a Doubly Linked List?
Now in the example class, I provided the before and after references are actually ids used in the map of objects. I do not use a direct reference for the object. Either way, it will work the same but I will get into that more later.
What is it good for?
A doubly linked list excels at a couple of things. Number one would be the time complexity of inserting and taking things out of it. With a normal array if you want to add something to the front you have to move that entire array forward. With a doubly-linked list, you just change the references to the before and after objects for the objects that you want to insert in-between. Here you see the time complexity compared:
|Doubly Linked ID List||O(1)||O(1)||O(1)||O(n)|
|Doubly Linked List||O(1)||O(1)||O(n)||O(n)||Normal Array||O(n)||O(n)||O(1)||O(n)|
Now if you are dealing with small data sets a doubly linked list may be a bit much. But if you are dealing with thousands or millions of objects then it becomes indicative to come up with a solution that is fast especially if you have to do a lot of inserting and deleting.
Real Example Use Case
So, I am currently developing a level creator program using TypeScript, Babylon.Js, and Electron. It allows you to place thousands upon thousands of models in a single scene and have the ability to edit each individually and in a group. On the left-hand display of the window, there is a display with all the nodes in the scene. The user can scroll through all the nodes, edit them, delete them, and drag n’ drop them to new locations and inside groups.
Well, in this case, if we used a normal array and the user had something like 10,000 models in the scene we would have to move all other 9,999 models in the array to match the new arrangement. But with a doubly-linked list, it becomes extremely fast. We just have to remove the object from the current list by changing its before and after references as well it’s surrounding objects and then either discard it or put it in another part of the list by once again changing its new surrounding objects before and after references as well as it’s own. So, It’s about 8 operations instead of 9k.