In this article, we are going to put the focus on how to implement a doubly linked list in Java.

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: 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:

```    ```
private Node<T> tail;
private int size;
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;
}
```
```

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:

```    ```
Node<T> newNode = new Node<T>(data, head, null);
}
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:

```    ```
Node<T> newNode = new Node<T>(data, null, tail);
if(tail != null) {
tail.next = newNode;
}
tail = 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) {
} else if (index == this.size()) {
} else {
Node<T> newNode = new Node<T>(data);
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;
}
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 {
tail = null;
} else {
}
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 {
} 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 {
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.

```    ```
public Node<T> getFirst() {
}

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) {
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");
}
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.

now, let’s put all the pieces together and test our doubly linked list implementation in Java:

```    ```
public static void main(String[] args) {
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 {
}
// 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