What Is Doubly Linked List?

A warm hello to all the readers!

In this post, we will understand the second variation or type which is called Doubly Linked List.

Doubly linked list differs from singly linked list in a way that it allows to travel in both directions front and back. And to do the same, the node stores three pieces of data.

1. Pointer or memory address of previous node
2. Actual value of node
3. Pointer or memory address of next node

And a sample doubly linked list is represented as:

Node1 is the first node and therefore it has nothing to point to a previous node. Therefore, previous pointer value is null. Node1 also points to the next node Node2.

Node2 points to previous node Node1 and to the next node Node3.

Node3 points to previous Node2. Node3 is the last node and thereby points to null value.

What Are Doubly Linked List Operations?

Let us now talk about different operations that can be performed on doubly linked list.

1. The item can be accessed
2. A new item can be inserted in the beginning, end or anywhere in between the list
3. Any item can be deleted
4. Any item can be searched by traversing the list

What Is The Time Complexity Of Doubly Linked List?

Now we know the different operations that can be performed on the doubly linked list. We shall now see what is the time complexity of each operation.

1. Accessing element – This takes O(n) time because each element has to be traversed to see memory address of next element
2. Inserting element – This takes O(n) time since in worst case if inserting element in middle of the list, then this requires traversing the list.
3. Deleting element – This again takes O(n) time since in worst case if inserting element in middle of the list, then this requires traversing the list.
4. Searching element – This also takes O(n) time since it requires (n) unknown number of iterations over the elements of the list in order to search a particular value