# 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 emptyCall

*addLast*if the specified index is equal to the size of the listTraverse 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.