Singly Linked Lists vs. Doubly Linked Lists
Examine how the two renditions of the linked list structure fare against each other.
We'll cover the following
Which is better?
DLLs have a few advantages over SLLs, but these perks do not come without a cost:
- Doubly linked lists can be traversed in both directions, which makes them more compatible with complex algorithms.
- Nodes in doubly linked lists require extra memory to store the
previousElement
pointer. - Deletion is more efficient in doubly linked lists as you do not need to keep track of the previous node. You already have a backward pointer for it.
At this point, the two major types of linked lists have been compared. The minor memory load that comes with DLLs can be forgone because of the convenience they provide.
This doesn’t mean that DLLs are perfect. There is always room for improvement!
Let’s discuss a tweak that can improve the functionality of both types.
Tail pointer in a linked list
The head
node is essential for any linked list, but what if you also kept account of the tail of the list? Now, you are aware of both ends of a linked list.
To add the tail
functionality, you must add another member to your LinkedList
class:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.