Exploring a possible solution

Now that we know the limitations of singly linked lists and the situations where those limitations lead to sub-optimal solutions, we can start to consider a data structure that can be used efficiently in such situations.

Doubly linked list

A doubly linked list is a bidirectional linear and dynamic data structure that stores data sequentially at random memory locations. Instead of storing just information about the next node in the list, a doubly linked list node also stores information about the previous node, making it a powerful bidirectional extension of a singly linked list.