Menu
I've recently come across some of the PHP-SPL data structures and the I've been looking over the first one, the doubly linked list. I've a rough idea what a linked list is and now I can see what a doubly linked list is but my question is: What in the world would I do with this?
I seems like it would be just as easy to use an array. Can some Computer Science type enlighten me?
427
The most common reason to use a doubly linked list is because it is easier to implement than a singly linked list. While the code for the doubly linked implementation is a little longer than for the singly linked version, it tends to be a bit more “obvious” in its intention, and so easier to implement and debug.
Doubly linked list can be used in navigation systems where both forward and backward traversal is required. It can be used to implement different tree data structures. It can be used to implement undo/redo operations.
If we need better performance while searching and memory is not a limitation in this case doubly linked list is more preferred. As singly linked list store pointer of only one node so consumes lesser memory. On other hand Doubly linked list uses more memory per node(two pointers).
Singly linked list is preferred when we have memory limitation(we can't use much memory) and searching is not required. Doubly linked list is preferred when we don't have memory limitation and searching is required(we need to perform search operation on the linked list).
Unlike a singly-linked list, a doubly linked list can walk the list in either direction, and do object insertion and deletion in the middle of the list in O(1) (provided you already has access to spot in the list where it's going to happen, unlike a singly linked list. That said, doubly linked lists are inferior in other ways and are defiantly not something you'll come across that often in practice.
125
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
