Doubly Linked List in Java

The doubly linked list is a data structure that has a set of linked nodes attached to each other in a sequential manner such that once can traverse both ways from a node (i.e. if we are at a node X we can go to the node previous of X or we can go to the node that is followed by X. Note: Each node in a doubly-linked list contains a data field, a previous pointer, and a next pointer.)

What is a Doubly Linked List in Java?

We have already studied how Linked list can be used to implement data structures like stack or features like mailing list etc. Now imagine we are implementing the feature of copying the text in a notepad using JAVA. For this, we can use the Linked List data structure that we create a new node every time we hit the copy tab and store the copied text in the node.

Butt there is an issue! What are we want to refer to as the very last text item we copied? How do we reach there? Now the only way to do this in Linked List is to start from the head node and traverse till we reach the second last node.

Traversing in Linked List is unidirectional (i.e. in the forward direction only) and we cannot go back to the previous nodes in Linked List. To tackle this problem Doubly Linked List was introduced.

The doubly linked list data structure can be referred to as a variation of the linked list data structure. The doubly linked list, similar to the linked lists is a data structure that can be set out as the collection of nodes.

In doubly linked lists the traversal is possible in both directions, i.e. both forward and backward. The nodes in the doubly linked lists are connected through pointers.

Each node in the doubly linked list contains three fields:

data: It stores the data like numbers, characters, etc.
previous pointer: It contains the address of the previous node.
next pointer: It contains the address of the next node.

General structure of a node in doubly linked list:

Pictorial representation:

STRUCTURE OF NODE

Since we have seen the structure of a node of a doubly linked list in java we will see how to implement a doubly linked list in java in the next sections.

Now by using the doubly linked list we can refer to the previous node. Thus our problem is solved. In order to get the last copied item, we will go to the last node and return its value.

Uses of DLL

We can implement the feature of front and back navigation in navigation system applications by using the Doubly linked list. This is done with the use of previous and next pointers.
The forward and backward navigations within the browsers with the help of forwarding and backward buttons are implemented using a doubly-linked list.
The classic game deck of cards can also be represented using a doubly-linked list.
The undo and redo functionalities in the applications like notepad etc can also be implemented using a doubly-linked list.
The Most recently use (MRU) and Least recently used (LRU) cache can also be constructed using a doubly-linked list.
The doubly linked list can be used to implement data structures like a binary tree, stack, etc.

Implementation of Doubly Linked List in Java

In this section, we will implement the doubly linked list using JAVA. Now before we start implementing the features like creating a new node or deleting a node in a doubly-linked list, let us see what a node looks like in a doubly-linked list.

The algorithm to implement a doubly linked list in Java:

Define a Node class that represents a node in the list. It will have three properties: data, previous which will point to the previous node, and next which will point to the next node.

Defining a Node

First of all, we will define a Node class. The node structure as discussed will have three fields data, prev, and next.

note: Both prev and next will be of the type node.

Following is the representation of a node in a doubly-linked list:

REPRESENTATION OF NODE

Creating Doubly Linked List Class

We will define another class DoublyLinkedList that will be used to create our doubly linked list. It will contain two nodes head and tail.

The head node will store the location of the first node.
The tail node will store the location of the last node.

Initially, both the head node and the tail node will be pointing to null.

Adding a New Node

Adding a new node to the front:

We will create a new function to add a new node to the doubly linked list at the front.

The function will do the following:

It will accept a value val as the parameter.
A new node temp will be create with the values of data, prev and next as val, head and null respectively.
We will check if the head node is null. If the head node is null then the node that is being added will be the head. Thus we will update the head.prev to temp.
Then we will assign temp to the head.
We will check if the tail is null. If the tail is null that means that the node that we have added is the only node. Thus this node will also act as the tail. Thus we will assign the temp to the tail.

code:

Pictorial representation:

NEW NODE ADDITION FRONT

Adding a new node to the back:

We will create a new function to add a new node to the doubly linked list at the back.

The function will do the following:

It will accept a value val as the parameter.
A new node temp will be create with the values of data, prev and next as val, null and tail respectively.
We will check if the tail node is null. If the tail node is null then the node that is being added will be the tail. Thus we will update the tail.next to temp.
Then we will assign temp to the tail.
We will check if the head is null. If the head is null that means that the node that we have added is the only node. Thus this node will also act as the head. Thus we will assign the temp to the head.

code:

Pictorial representation:

NEW NODE ADDITION BACK

Iterating through the Doubly Linked List

Forward iteration:

We will create a new Node temp and assign it head. Thus now our temp will point to the head.
Then we will run a while loop until the temp hits null. In the loop we will:
- Print the data of the head.
- Assign the next node to the temp.

Backward iteration:

We will create a new Node temp and assign it tail. Thus now our temp will point to the tail.
Then we will run a while loop until the temp hits null. In the loop we will:
- Print the data of the head.
- Assign the previous node to the temp.

Deleting Items from the Doubly Linked List

Deleting items from the front:

We will create a new node temp and assign it head. Thus now our temp will point to the head node.
Now we will assign head.next to the head node. Thus now our head node will start pointing to the node next to it.
Since now the head is pointing to the node next to it, now we will assign the prev pointer the value null (which was earlier pointing to the previous head node).
Finally, we will return the deleted node's data.

Deleting items from the back:

We will create a new node temp and assign it tail. Thus now our temp will point to the head node.
Now we will assign tail.prev to the tail node. Thus now our head node will start pointing to the node previous to it.
Since now the head is pointing to the node previous to it, we will need to set the value of the next to null (which was earlier pointing to the previous tail node).
Finally, we will return the deleted node's data.

The complete code will look like the following:

Pictorial representation of node deletion in a doubly linked list:

NODE DELETION

Doubly Linked List in Java Example

In this section, we will create a doubly linked list and add nodes to it. Then we will display our doubly linked list.

Output:

Pictorial representation:

DISPLAY LINKED LIST

Conclusion

The doubly linked list is an improvisation of the Linked List
In a doubly-linked list we can traverse both sides
The data is store the data in the node.
The prev is used to store the address of the previous node.
The next is used to store the address of the next node.
The doubly linked list is used in many real-life situations like implementing navigations.
The doubly linked list is used to implement data structures like tree, graph, etc.