Doubly Linked List

Prerequisites 

• You should have read the big O notation
• You should have read the data structure introduction
• You should have read the Singly Linked List data structure

Things to be discussed are

• Construct a Doubly Linked List
• Compare and contrast Doubly and Singly Linked Lists
• Implement basic operations on a Doubly Linked List

What are doubly linked lists?
These are almost identical to Singly Linked Lists, except every node has another pointer, to the previous node.
 
Diagram Example

How do doubly-linked lists work?
This data structure works, in the same way, the singly linked list works. The only difference is that there is a pointer for each node that points to the previous node. So when our pointer is at a particular node, we can still go back and look at the previous data in the previous node. We cannot do this in the singly linked list data structure.
BigO of Doubly Linked Lists
Insertion –   O(1)
Removal –   O(1)
Searching –   O(N)
Access –   O(N)
Key Points About Doubly Linked Lists

• Doubly Linked Lists are almost identical to Singly Linked Lists except there is an additional pointer to previous nodes
• Better than Singly Linked Lists for finding nodes and can be done in half the time!
• However, they do take up more memory considering the extra pointer
• Doubly linked lists are used to implement other data structures and certain types of caches

Written By Okocha Ebube