Introduction To Doubly Linked List

In previous article we learned about SinglyLinkedList.

https://techyield.blogspot.com/2019/06/singly-linked-list-introduction.html

Here we are going to discuss about DoublyLinkedList.

In SinglyLinkedList we have a value field and a reference field to the next node.

In DoublyLinkedList we have one extra field called prev node which points to the prev node. With this field we are able to know the previous node of the current node.


Node Structure :

class DoublyListNode {

int val;
DoublyListNode prev , next;

DoublyListNode(int x){
val = x;
}

}

The entire list is represented with the head node as in SinglyLinkedList.


Operations :

Add Operation :

If we want to insert cur after an existing node prev  .

We can add in two steps :

1. Link cur with prev and next , where next is the original next node of prev.

2. Re link the prev and next with cur.

Similar to the singly Linked List the space and time complexity is O(1).

Delete Operation :

If we want to delete an existing node cur from the doubly linked list we can simply link its prev node prev with the next node next.

Unlike the singly linked list it is easy to get the prev field in constant time O(1).

Here the space and time complexity both are O(1).