Introduction to Java Doubly Linked List
In this article, we are going to put the focus on how to implement a doubly linked list in Java.
First, we will start with explaining what a doubly LinkedList is and what features bring in.
Then, we are going to showcase through a practical example how to create a doubly linked list implementation from scratch.
What is Doubly Linked List?
Simply put, a doubly LinkedList is a linear data structure that stores data in a form of nodes. It’s a variation and an extension of linked lists.
However, this type of list contains an extra pointer called previous compared to the basic LinkedList.
In short, each node of a doubly linked list has two references: next and previous to point to the next and the previous nodes respectively:
the following image illustrates how nodes are structured and chained in a doubly LinkedList:
Advantages over Singly Linked List
Typically, singly linked lists have only one reference that points to the next node. So, we can only traverse them forward.
This is where doubly linked lists come into play, they offer the ability to traverse them in both directions, forward and backward.
Another great advantage is the possibility to add and delete items easily. Unlike a singly linked list, we don’t need to iterate the entire list to find the previous node. We can just change pointers.
On other hand, one of the main disadvantages is that each node requires extra memory space for storing previous pointer.
Doubly Linked List Implementation in Java
We have explained in a previous article how to implement a singly linked list in Java. Check out that post to understand the basis of a linked list implementation.
Well, the java implementation of a doubly linked list follows the same rules. The only difference will be that we have to define another variable to reference the previous pointer.
Algorithm
The core building block for a linked list implementation is the node. Basically, each node of a doubly LinkedList must hold three components:
variable holding the data
reference storing a link to the next node
reference storing a link to the previous node
Let’s take a look at how we can implement a doubly linked list using a Java class:
public class DoublyLinkedList<T> {
private Node<T> head;
private Node<T> tail;
private int size;
public DoublyLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
private static class Node<T> {
private T data;
private Node<T> next;
private Node<<T> previous;
public Node(T data, Node<T> next, Node<T> previous) {
this.data = data;
this.next = next;
this.previous = previous;
}
public Node(T data) {
this(data, null, null);
}
}
}
As we can see, the backbone of a linked list implementation is the Node class which contains three variables: data, next, and previous.
Please bear in mind that the head references the first node and the tail point to the last node of the list.
Basic Operations Implementations
Now that we implemented the node in Java, let’s see how we can manipulate data in a doubly linked list.
We are going to implement the basic operations: returning the list size, checking if it is empty, adding, removing, and retrieving elements.
Returning the Size and Checking if the List is Empty
These two methods are the most simplest and basic ones, size() returns the size of the list. isEmpty() checks if the list is empty or not:
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
Adding New Elements
There are 3 different ways to insert new elements to a doubly linked list:
at the front
at the end
at a given position
First, let’s see how to insert a new element at the beginning of the list:
public void addFirst(T data) {
Node<T> newNode = new Node<T>(data, head, null);
if(head != null ) {
head.previous = newNode;
}
head = newNode;
if(tail == null) {
tail = newNode;
}
size++;
}
As we can see, the next of the new element is the head of the list, and its previous points to null.
In short, the new node becomes the head of our list.
Now, let’s implement the method that will allow us to add a new node at the end of the list:
public void addLast(T data) {
Node<T> newNode = new Node<T>(data, null, tail);
if(tail != null) {
tail.next = newNode;
}
tail = newNode;
if(head == null) {
head = newNode;
}
size++;
}
As shown above, the previous of the new node points to the old tail. Since the new node will be the new tail, its next points to null.
Please notice that we did not traverse the entire list to find the tail. This is the main benefit of a doubly linked list.
Finally, we are going to showcase how to insert a new node at a specific position:
public void addAtPos(int index, T data) {
if (index < 0 || index > this.size()) {
throw new IllegalArgumentException("Invalid Index");
} else if (index == 0) {
this.addFirst(data);
} else if (index == this.size()) {
this.addLast(data);
} else {
Node<T> newNode = new Node<T>(data);
Node<T> currentNode = head;
for (int i = 0; i < index; i++) {
currentNode = currentNode.next;
}
newNode.next = currentNode;
newNode.previous = currentNode.previous;
currentNode.previous = newNode;
newNode.previous.next = newNode;
size++;
}
}
Well, inserting a new node at a specific index is a complicated operation compared to addFirst and addLast.
Below are some of the challenges we need to take into account in order to add an element to a given position:
Throw an exception if the index is less than zero or greater than the size of the list
Call addFirst if the list is empty
Call addLast if the specified index is equal to the size of the list
Traverse the list until the index, then set up the new node pointers: new and previous
Displaying Elements
We can traverse a doubly linked list forward and backward. So, there are two convenient ways to display its elements.
Let’s implement the two methods:
public void displayForward() {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
Node<T>currentNode = head;
while (currentNode != null) {
System.out.println(currentNode.data);
currentNode = currentNode.next;
}
}
public void displayBackward() {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
Node<T> currentNode = tail;
while (currentNode != null) {
System.out.println(currentNode.data);
currentNode = currentNode.previous;
}
}
Deleting Elements
Now, let’s see together how to implement deletion methods. Similarly, we can remove elements either from the beginning, the end, or the middle of a doubly linked list.
First, we are going to explain how to delete the head (which is the first node) of the linked list:
public void removeFirst() {
if (this.isEmpty()) {
System.out.println("List is empty");
} else {
if (head.next == null) {
tail = null;
} else {
head.next.previous = null;
}
head = head.next;
size--;
}
}
To delete the first node, we need to assign the next node of the first node to the head.
Next, let’s see how to remove the last node which is the tail:
public void removeLast() {
if (this.isEmpty()) {
System.out.println("List is empty");
} else {
if (head.next == null) {
head = null;
} else {
tail.previous.next = null;
}
tail = tail.previous;
size--;
}
}
Similarly, we can remove the last node by making the last previous node the new tail of the list.
Lastly, let’s take a look at how we can remove a node at specific index:
public void removeAtPos(int index) {
if (index < 0 || index > this.size()) {
throw new IllegalArgumentException("Invalid Index");
} else if (index == 0) {
this.removeFirst();
} else if (index == this.size() - 1) {
this.removeLast();
} else {
Node<T> currentNode = head;
for (int i = 0; i < index; i++) {
currentNode = currentNode.next;
}
currentNode.previous.next = currentNode.next;
currentNode.next.previous = currentNode.previous;
size--;
}
}
As we can see, we need to iterate the list to find the node at the specified position.
Then, we can remove this node by assigning the previous node’s next to the current node’s next and pointing the current next’s previous to the previous node.
Searching and Retreiving Elements
In this section, we are going to exemplify how to get the first and the last nodes. Then, we will demonstrate how to search and fetch elements by index or value.
Let’s start with retrieving the first and the last nodes:
public Node<T> getFirst() {
return head;
}
public Node<T> getLast() {
return tail;
}
Now, let’s showcase how to get an element by its position or value:
public Node<T> getByValue(T value) {
Node<T> currentNode = head;
while (currentNode != null) {
if (currentNode.data.equals(value)) {
return currentNode;
}
currentNode = currentNode.next;
}
return null;
}
public Node<T> getByIndex(int index) {
if (index < 0 || index > this.size()) {
throw new IllegalArgumentException("Invalid Index");
}
Node<T> currentNode = head;
for (int i = 0; i < index; i++) {
currentNode = currentNode.next;
}
return currentNode;
}
In order to search a node by value, we need to loop through the list starting from the head and test if each node’s data is equal to the given value.
For searching an element by its index, we need to traverse the list until the specified index. Then, we simply return the current node.
Doubly LinkedList Implementation Example
now, let’s put all the pieces together and test our doubly linked list implementation in Java:
public static void main(String[] args) {
DoublyLinkedList cities = new DoublyLinkedList();
// Adding new elements
cities.addFirst("New York");
cities.addFirst("Vienna");
cities.addLast("London");
cities.addAtPos(3, "Tamassint City");
cities.addAtPos(2, "Lisbon");
cities.addLast("Seoul");
cities.addAtPos(4, "Helsinki");
cities.displayForward();
// Searching elements
System.out.println("--------------------------");
int index = 5;
String value = "Tokyo";
Node myCity = cities.getByIndex(index);
System.out.println("City at index " + index + " : " + myCity.data);
myCity = cities.getByValue(value);
if (myCity != null) {
System.out.println("City with value " + value + " is found");
} else {
System.out.println("City with value " + value + " not found");
}
// Deleting elements
System.out.println("--------------------------");
cities.removeFirst();
cities.removeLast();
cities.removeAtPos(2);
cities.displayBackward();
}
## Output:
Vienna
New York
Lisbon
London
Helsinki
Tamassint City
Seoul
--------------------------
City at index 5 : Tamassint City
City with value Tokyo not found
--------------------------
Tamassint City
Helsinki
Lisbon
New York
Conclusion
To sum it up, we have covered in-depth how to implement a doubly linked list in Java. First, we have explained what a doubly linked list is.
Then, along the way, we have implemented some of the basic operations such as adding, removing and, searching elements.