DEV Community

Brad Goldsmith
Brad Goldsmith

Posted on • Updated on

Data Structures and Algorithms - Doubly Linked List

I believe this will be very brief as a doubly linked list is basically the same thing as a singly linked list with the exception that each node will not only have next pointer but a previous pointer as well. In that manner a doubly linked list may traverse bidirectionally as well as start at either the tail or the head. So for the pop() method you could just start from the tail and then traverse one down and set it's next value to null. So much more efficient than having to traverse it all the way up. This does add a little complexity however when adding / removing a node since we have to account for the dual connecting nodes. And by default a DLL uses more memory than a SLL however it does have more flexibility as you can see here. So which one is right to use? I guess that would depend on each individual situation and if memory is something to be accounted for, which it should, then in that case the SLL would probably be the way to go.

I was very curious about memory allocation and a couple of other small nuances and stumbled across this page: DLL vs SLL . According to them the memory difference is 4bytes (SLL) vs 8bytes(DLL) so what I gather there is that other pointer literally doubles the memory allocation. Good to know and there are some other cool comparisons if you'd like to check them out.

So as per this "series" here is a link to my github repo where I created the Doubly Linked List class. Doubly Linked List. I'm sure there are many other ways of implementing these methods and there are probably some that I have left off so feel free to comment on it. Again sorry for the short content but as you can see the Doubly Linked List is extremely similar to a Singly Linked List so this is all I have.

Top comments (0)