Singly Linked Lists vs. Doubly Linked Lists

Let's see 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 previous_element pointer.
  • Deletion is more efficient in doubly linked lists as we do not need to keep track of the previous node. We already have a backwards pointer for it.

At this point, we’ve compared the two major types of linked lists. 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 which 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 we 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, all we have to do is add another member to our LinkedList class:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.