Java Doubly Linked List

Java Doubly Linked List is a type of Linked List where each node apart from storing data has two links. The first link points to the previous node and the other link points to the next node of the list. Doubly Linked List, also abbreviated as DLL is much like a Single Linked List. Both Linked lists contain a pointer to the next node and a data field to represent the actual value to be stored in the node. The main difference is that DLL contains a pointer to the previous node in the list i.e. nodes in DLL are aware of both the previous and the next node. In this article, we will have a look at Doubly Linked List in Java, explore few examples, and get to know its Implementation.

ADVERTISEMENT Popular Course in this category JAVA MASTERY - Specialization | 78 Course Series | 15 Mock Tests

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

Syntax

There is no particular syntax for the Doubly Linked list in Java, but we will see How to declare the Doubly Linked List in Java. Before looking into a declaration of Doubly Linked List, let us see the Concept behind the implementation of Doubly Linked List.

Node in Double Linked List:

Prev Node

Data

Next Node

Prev Node

Data

Next Node

Here Prev Node and Next Node are pointers to previous and next elements of node respectively. ‘Data’ is the actual element where data is stored.

Below are some of the important terms we need to understand,

• Prev: Each link of linked list has a link to the previous node called Prev.
• Next: Each link of linked list has a link to the next node called Next
• Link: Each link of linked list can store data, known as element.
• Linked List: It contains the connection link to the first link and the last link.

Algorithm

• Define a Node class that represents a node in the linked list. It should have 3 properties i.e. previous node, data, and the next node
• Define another class to create a Doubly Linked List with two nodes i.e head and tail. Initially, these values will be null.
• Create a function for adding nodes in the linked list,
• It will first check whether the head is null and then insert the node as the head.
• Both head and tail will then point to the new node.
• If the tail is not null, the new node will be inserted at the list end in such a way that the pointer of the new node will point to the tail.
• Thus, the new node will become a new tail.

Declaration of Node for Doubly Linked List in Java:

class Node {
public int data;
public Node prev;
public Node next;
public void displayData() {
//content of the function}
}

As we can see there is an extra declaration or a reference(Node prev) in the case of Doubly Linked List.

Basic Operations of Doubly Linked List

Below are the basic operations available for Doubly Linked List,

• Insertion: Adding an element at the beginning of the linked list
• Deletion: Deleting an element at the beginning of the linked list
• Insert After: Adding an element after an item of linked list
• Insert Last: Adding an element to the end of the linked list
• Delete Last: Deleting an element at the end of linked list
• Delete: Deleting an element from the linked list using a key.
• Display forward: Displaying complete list in forward manner
• Display backward: Displaying complete list in backward manner

Examples of Java Doubly Linked List

Below are the different examples of Java Doubly Linked List:

Example #1: Declaration of Node and Adding nodes to Display

Code:

public class DLL {
class Node{
public int data;
public Node prevNode;
public Node nextNode;
public Node(int data) {
this.data = data;
}
}
Node headNode, tailNode = null;
public void addDLLNode(int data) {
Node newDLLNode = new Node(data);
if(headNode == null) {
headNode = tailNode = newDLLNode;
headNode.prevNode = null;
tailNode.nextNode = null;
}
else {
tailNode.nextNode = newDLLNode;
newDLLNode.prevNode = tailNode;
tailNode = newDLLNode;
tailNode.nextNode = null;
}
}
public void displayNode() {
Node currentNode = headNode;
if(headNode == null) {
System.out.println("Doubly Linked List is empty");
return;
}
System.out.println("Nodes in Doubly Linked List: ");
while(currentNode != null) {
System.out.print(currentNode.data + " ");
currentNode = currentNode.nextNode;
}
}
public static void main(String[] args) {
DLL dLinkedList = new DLL();
dLinkedList.addDLLNode(9);
dLinkedList.addDLLNode(7);
dLinkedList.addDLLNode(5);
dLinkedList.addDLLNode(3);
dLinkedList.addDLLNode(1);
dLinkedList.addDLLNode(3);
dLinkedList.addDLLNode(5);
dLinkedList.addDLLNode(7);
dLinkedList.displayNode();
}
}

Output:

So here we are creating a Node class to declare a Doubly Linked list and displaying the values of DLL.

Example #2: Delete at beginning of the linked list and display

Code:

public class DLL {
class Node{
public int data;
public Node prevNode;
public Node nextNode;
public Node(int data) {
this.data = data;
}
}
public void displayNode() {
Node tempNode = headNode;
while (tempNode != null) {
System.out.print(tempNode.data + "–>");
tempNode = tempNode.nextNode;
}
System.out.println("END");
}
Node headNode, tailNode = null;
public void addNode(int data) {
Node newNode = new Node(data);
if(headNode == null) {
headNode = tailNode = newNode;
headNode.prevNode = null;
tailNode.nextNode = null;
}
else {
tailNode.nextNode = newNode;
newNode.prevNode = tailNode;
tailNode = newNode;
tailNode.nextNode = null;
}
}
public void deleteInitialNode() {
if(headNode == null) {
System.out.println("Doubly Linked List is empty");
return;
}
else {
if(headNode != tailNode) {
headNode = headNode.nextNode;
}
else {
headNode = tailNode = null;
}
}
}
void printNode() {
Node currNode = headNode;
if(headNode == null) {
System.out.println("Doubly Linked List is empty");
return;
}
while(currNode != null)
{
System.out.print(currNode.data + " ");
currNode = currNode.nextNode;
}
System.out.println();
}
public static void main(String[] args) {
DLL doublyLL = new DLL();
doublyLL.addNode(3);
doublyLL.addNode(5);
doublyLL.addNode(7);
doublyLL.addNode(9);
doublyLL.addNode(11);
System.out.println("Doubly linked list: ");
doublyLL.printNode();
doublyLL.addNode(15);
doublyLL.addNode(17);
doublyLL.addNode(19);
doublyLL.deleteInitialNode();
doublyLL.addNode(21);
System.out.println("Doubly Linked List after deleting at the beginning: ");
doublyLL.printNode();
}
}

Output:

So here, the node is deleted at the beginning of the linked list i.e. Node 3 is deleted/ removed.

DLL can be traversed in forwarding and backward directions. Delete operation in DLL can be more efficient if the node pointer to be deleted is given. Every Node in DLL requires extra space for the previous pointer. All operations require an extra pointer to be maintained.

With this, we shall conclude our topic “Java Doubly Linked List”. We have seen What Java Doubly Linked List is and how is it implemented in Java programming with few examples. We have also seen Algorithm for Doubly Linked List and have listed out few operations applicable to DLL. We have implemented Insertion and delete at first operations, likewise, there are other operations also available which you can work on.

The above is the detailed content of Java Doubly Linked List. For more information, please follow other related articles on the PHP Chinese website!