Be the first user to complete this post

  • 0
Add to List
Beginner

192. Doubly Linked List Complete Implementation

In this article, we will see what is doubly linked list is, how it is different from other linked lists and how to implement it.

Earlier we have seen what Singly Linked List and Circular Linked List are and How to implement it. In a way, you say that it's an extension of a singly linked list. I would suggest that if you do not about Linked list, first read "Singly Linked List"

Let's see the difference between single and doubly linked lists.

Singly Linked List vs Doubly Linked List

Singly Linked ListDoubly Linked List
Easy ImplementNot easy
Less memoryMore Memory
Can traverse only in the forward directionTraverse in both directions, back, and froth
Doubly Linked List

So as we can see the in a doubly linked list each node has two references, next and prev which makes it possible to traverse in both directions.

Let's see how the Node structure will look like

Doubly Linked List - Node
class Node{
   int data;
   Node next;
   Node previous;
   public Node(int data){
      this.data = data;
      next = null;
      previous = null;
   }
}

Operations:

NOTE: we are two references here, head and tail. Head points the start of the linked list and tail points to the last node of the linked list.

Add at the Start : Add a node the begin­ning of the linked list. Its O(1). If size is 0 then make the new node as head and tail else put the at the start, change the head and do not change the tail.

Add at the End : Add a node at the end of the linked list. its O(1) since we have tail reference. If size is 0 then make the new node as head and tail else put node at the end of the list using tail reference and make the new node as tail.

Delete at the Start : Delete a node from begin­ning of the linked list and make the head points to the 2nd node in the list. Its O(1).

Get Size: returns the size of the linked list.

Get Ele­ment at Index : Return the ele­ment at spe­cific index, if index is greater than the size then return –1. its O(n) in worst case.

Print: Prints the entire linked list. O(n).

Output:

Adding Node 2 at the start
Adding Node 1 at the start
Doubly Linked List:  1 2
Adding Node 3 at the End
Doubly Linked List:  1 2 3
Adding node after 2
Doubly Linked List:  1 2 4 3
deleting node 1 from start
Doubly Linked List:  2 4 3
Element at index 2: 4
Adding Node 1 at the start
Doubly Linked List:  1 2 4 3
deleting node 3 from end
Doubly Linked List:  1 2 4
Size of the Linked List: 3