Doubly Linked List example in Java

In this post, we will see the Doubly Linked List example in Java. Here we will cover insertion part, for deletion part we have separate post.

Introduction : Doubly Linked List(DLL) contains one data reference and two node pointers, next and previous. In previous posts, we have seen the Singly Linked List implementation in JAVA where each node has one data reference and one node pointer to the next node. In doubly linked list, in addition to the singly linked list, there will be one extra node pointer which points the previous node. Because of two node pointers in doubly linked list, we could traverse the list in both forward and backward directions. In this post, we will see the insertion of data in doubly linked list using java.

 

In a doubly linked list, previous node reference of root node will be always NULL. Likewise, next node reference of last node in a doubly linked list will be always NULL.

Advantages over singly linked list :

  1. A Doubly Linked List can traverse in both forward and backward directions.
  2. The delete operation in doubly linked list is more efficient in case of delete by index. Here, we need to understand this statement by example. Suppose, we have a singly linked list A–>B–>C–>D–>E and similar data in doubly linked list A<–>B<–>C<–>D<–>E . Now, if we need to delete the node by index lets say, delete the node at index=3, doubly linked list will be more efficient. In case of singly linked list, we must traverse from A to D (index starts from 0) in forward direction with 4 units of distance to get the previous node and next node of index=3. But in case of doubly linked list, we can identify the shortest route of either from head or tail of the list. In this particular case, since index=3 and it’s near to tail of the list, we can traverse in backward direction from E to D with 1 unit of distance to get the next node and previous node of index=3. We will see the similar implementation in next post where we will perform the delete operation on doubly linked list using java.
  3. Reversing of doubly linked list is simple and straightforward.
  4. Searching is faster in case of sorted doubly linked list.

Disadvantages over singly linked list :

  1. An extra space is required to store the address of previous node.
  2. Any operation on doubly linked list require two pointers reference change/modification.

Real time use :

  1. An applications where navigation workflow is required which can traverse in both forward and backward directions. Example: Amazon online shopping application. We follow some certain steps before placing the order like item search, add to cart, select delivery address, payment and place order. We follow these certain steps and any point of time we can go back or forth . Here we can use doubly linked list and each node will store the data of each step.
  2. Used in browsers to implement backward and forward navigation of visited web pages.
  3. Used in gaming software to represent the level of the user. User can even go back to previous level and re-play that level.
  4. Used in Notepad applications to perform Undo and Redo operations.

 

Now, we will see the structure of node and different overloaded methods for add operation in doubly linked list example in Java.

DoublyNode.java :

Below is the DoublyNode class with one data reference and two node pointers ‘next” and previous. We will make this class generic to create DoublyNode of any object type using JAVA Generics. Also, we have overridden hashCode() and equals() methods which will be used to check the equality of two DoublyNode.

 

DoublyLinkedList.java :

DoublyLinkedList class contains root of the doubly linked list of type DoublyNode<T> and variable name as “root”. We made this class generic to create doubly linked list of any object type. Also, It has integer variable “size”. Now, we will see the different methods to add the data to the doubly linked list at end of the list, at start of the list and at particular position of the doubly linked list.

public void add(T data) :

This method will add the element at end of the doubly linked list. We must maintain one data reference and two node pointers for each doubly node.

public void addAtFirst(T data) :

This method will add the element at start of the doubly linked list.

public void (T data , int index) :

This method will add the data at specified index. Index starts from 0 to n-1 where n=size of the doubly linked list. If index is negative, there will be no change in doubly linked list. If index is more than size of the doubly linked list, method will throw IndexOutOfBoundsException.

Apart from these method, we have some supporting methods like getLastNode() , next(), clear(), hashCode(), equals() etc.

 

To test these methods, we will create one DTO class Item.java and add some item objects to doubly linked list.

 

Output :

 

Hope you like this post. Please leave your comments/suggestions.

 

You may like:

Introduction of Doubly Linked List(DLL)

Delete Operation in Doubly Linked List

Reverse a Doubly Linked List

Iterator For Doubly Linked List

Singly Linked List

Top