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.
[stextbox id=’info’] 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.[/stextbox]
Advantages over singly linked list :
- A Doubly Linked List can traverse in both forward and backward directions.
- 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.
- Reversing of doubly linked list is simple and straightforward.
- Searching is faster in case of sorted doubly linked list.
Disadvantages over singly linked list :
- An extra space is required to store the address of previous node.
- Any operation on doubly linked list require two pointers reference change/modification.
Real time use :
- 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.
- Used in browsers to implement backward and forward navigation of visited web pages.
- Used in gaming software to represent the level of the user. User can even go back to previous level and re-play that level.
- 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.
package com.netSurfingZone.doublyLinkedList;
public class DoublyNode<T> {
private T data ;
private DoublyNode<T> next;
private DoublyNode<T> previous;
public DoublyNode(T data) {
this.data = data;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public DoublyNode<T> getNext() {
return next;
}
public void setNext(DoublyNode<T> next) {
this.next = next;
}
public DoublyNode<T> getPrevious() {
return previous;
}
public void setPrevious(DoublyNode<T> previous) {
this.previous = previous;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((data == null) ? 0 : data.hashCode());
result = prime * result + ((next == null) ? 0 : next.hashCode());
result = prime * result + ((previous == null) ? 0 : previous.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof DoublyNode))
return false;
DoublyNode other = (DoublyNode) obj;
if (data == null) {
if (other.data != null)
return false;
} else if (!data.equals(other.data))
return false;
if (next == null) {
if (other.next != null)
return false;
} else if (!next.equals(other.next))
return false;
if (previous == null) {
if (other.previous != null)
return false;
} else if (!previous.equals(other.previous))
return false;
return true;
}
@Override
public String toString() {
return "[data=" + data + "]";
}
}
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.
package com.netSurfingZone.doublyLinkedList;
public class DoublyLinkedList<T>{
private int size;
private DoublyNode<T> root;
/**
* Add element at last.
*
* @param data
*/
public void add(T data) {
if (data == null) {
return;
}
if (root == null) {
root = new DoublyNode<T>(data);
} else {
DoublyNode<T> newNode = new DoublyNode<T>(data);
DoublyNode<T> lastNode = getLastNode(root);
lastNode.setNext(newNode);
newNode.setPrevious(lastNode);
}
size++;
}
/**
* Add element at first.
*
* @param data
*/
public void addAtFirst(T data) {
if (data == null) {
return;
}
DoublyNode<T> newNode = new DoublyNode<T>(data);
if (this.root != null) {
this.root.setPrevious(newNode);
newNode.setNext(this.root);
this.root = newNode;
} else {
this.root = newNode;
}
size++;
}
/**
* Add the element at specified index. Index start from 0 to n-1 where n=size of
* linked list. If index is negative value, nothing will be added to linked
* list.
*
* if index =0 , element will be added at head and element become the first
* node.
*
* @param data
* @param index
* - index at which element to be added.
*/
public void add(T data, int index) throws IndexOutOfBoundsException {
if (data == null) {
return;
}
// If index=0 , we should add the data at head
if (index == 0) {
addAtFirst(data);
return;
}
// If index= size, we should add the data at last
if (index == this.size) {
add(data);
} else if (index < this.size) {
DoublyNode<T> newNode = new DoublyNode<T>(data);
// get the node at (index) from linked list and mark as rightNode.
// get the node at (index-1) from linked list and mark as leftNode.
// set node of newly created node as right node.
// set node of left node as newly created Node.
DoublyNode<T> rightNode = getNode(index);
DoublyNode<T> leftNode = rightNode.getPrevious();
leftNode.setNext(newNode);
newNode.setPrevious(leftNode);
newNode.setNext(rightNode);
rightNode.setPrevious(newNode);
size++;
} else {
throw new IndexOutOfBoundsException("Index not available.");
}
}
/**
* Returns the Doubly Node at given index
* @param index
* @return
*/
private DoublyNode<T> getNode(int index) {
if (index < 0 || index > this.size - 1) {
throw new IndexOutOfBoundsException("Index not available.");
}
// If index=0 , return head
if (index == 0) {
return this.root;
}
// If index= size, return last node
if (index == this.size - 1) {
return getLastNode(this.root);
}
int pointer = 0;
DoublyNode<T> pointerNode = this.root;
while (pointer <= index) {
if (pointer == index) {
return pointerNode;
} else {
pointerNode = next(pointerNode);
pointer++;
}
}
return null;
}
/**
* Returns last node of given doubly node
* @param node
* @return
*/
private DoublyNode<T> getLastNode(DoublyNode<T> node) {
if(node !=null) {
DoublyNode<T> lastNode = node;
if (lastNode.getNext() != null) {
return getLastNode(lastNode.getNext());
} else {
return lastNode;
}
}
return null;
}
/**
* Returns next consecutive node of given doubly node
* @param node
* @return
*/
private DoublyNode<T> next(DoublyNode<T> node) {
if (node.getNext() != null) {
return node.getNext();
} else {
return null;
}
}
public int size() {
return this.size;
}
public void clear() {
this.root = null;
this.size = 0;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((root == null) ? 0 : root.hashCode());
result = prime * result + size;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof DoublyLinkedList))
return false;
DoublyLinkedList other = (DoublyLinkedList) obj;
if (root == null) {
if (other.root != null)
return false;
} else if (!root.equals(other.root))
return false;
if (size != other.size)
return false;
return true;
}
@Override
public String toString() {
String represent = "[";
DoublyNode<T> nextNode = this.root;
while (nextNode != null) {
represent = represent + nextNode.toString();
nextNode = next(nextNode);
if (nextNode != null) {
represent = represent + ",";
}
}
represent = represent + "]";
return represent;
}
}
To test these methods, we will create one DTO class Item.java and add some item objects to doubly linked list.
package com.netSurfingZone.dto;
public class Item {
private Integer itemId;
private String itemName;
private Double price;
public Item(Integer itemId, String itemName, Double price) {
super();
this.itemId = itemId;
this.itemName = itemName;
this.price = price;
}
public Integer getItemId() {
return itemId;
}
public void setItemId(Integer itemId) {
this.itemId = itemId;
}
public String getItemName() {
return itemName;
}
public void setItemName(String itemName) {
this.itemName = itemName;
}
public Double getPrice() {
return price;
}
public void setPrice(Double price) {
this.price = price;
}
@Override
public String toString() {
return "Item [itemId=" + itemId + ", itemName=" + itemName + ", price=" + price + "]";
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((itemId == null) ? 0 : itemId.hashCode());
result = prime * result + ((itemName == null) ? 0 : itemName.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof Item))
return false;
Item other = (Item) obj;
if (itemId == null) {
if (other.itemId != null)
return false;
} else if (!itemId.equals(other.itemId))
return false;
if (itemName == null) {
if (other.itemName != null)
return false;
} else if (!itemName.equals(other.itemName))
return false;
return true;
}
}
package com.netSurfingZone.doublyLinkedList;
import com.netSurfingZone.dto.Item;
public class TestDoublyLinkedList {
public static void main(String[] args) {
DoublyLinkedList<Item> doublyLinkedList=new DoublyLinkedList<>();
Item item1=new Item(101, "DELL Latitude 5647", 300.0);
Item item2=new Item(102, "Mac Book", 1000.0);
Item item3=new Item(103, "Mac Book Pro", 2000.0);
Item item4=new Item(104, "HP Elitebook", 700.0);
System.out.println("*****Adding first Item-101*****");
doublyLinkedList.add(item1);
System.out.println("Size = " + doublyLinkedList.size());
System.out.println(doublyLinkedList);
System.out.println(" ");
System.out.println("*****Adding item-102 at end*****");
doublyLinkedList.add(item2);
System.out.println("Size = " + doublyLinkedList.size());
System.out.println(doublyLinkedList);
System.out.println(" ");
System.out.println("*****Adding item-103 at first*****");
doublyLinkedList.addAtFirst(item3);
System.out.println("Size = " + doublyLinkedList.size());
System.out.println(doublyLinkedList);
System.out.println(" ");
System.out.println("*****Adding item-104 at index 1*****");
doublyLinkedList.add(item4, 1);
System.out.println("Size = " + doublyLinkedList.size());
System.out.println(doublyLinkedList);
System.out.println(" ");
}
}
Output :
*****Adding first Item-101***** Size = 1 [[data=Item [itemId=101, itemName=DELL Latitude 5647, price=300.0]]] *****Adding item-102 at end***** Size = 2 [[data=Item [itemId=101, itemName=DELL Latitude 5647, price=300.0]], [data=Item [itemId=102, itemName=Mac Book, price=1000.0]]] *****Adding item-103 at first***** Size = 3 [[data=Item [itemId=103, itemName=Mac Book Pro, price=2000.0]], [data=Item [itemId=101, itemName=DELL Latitude 5647, price=300.0]], [data=Item [itemId=102, itemName=Mac Book, price=1000.0]]] *****Adding item-104 at index 1***** Size = 4 [[data=Item [itemId=103, itemName=Mac Book Pro, price=2000.0]], [data=Item [itemId=104, itemName=HP Elitebook, price=700.0]], [data=Item [itemId=101, itemName=DELL Latitude 5647, price=300.0]], [data=Item [itemId=102, itemName=Mac Book, price=1000.0]]]
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