In this post we’ll see an implementation of Doubly Linked List in Java. In
__singly linked list__ each node points to the next node where as in Doubly Linked List each node stores references to
the next as well as previous node.

Following image shows how nodes of a doubly linked list reference each other.

There are two more references head and tail; head always points to the first node and the tail is a reference to the last node.

### Java program for Linked List

Operations covered in this Doubly Linked List implementation are-

- Insertion in doubly linked list
- Doubly Linked List traversal
- Deleting node in Doubly Linked List
- Doubly Linked List implementation in Java – Full Program

For representing nodes of the linked list a separate class is used which apart from the data also has two references for storing next and previous references to itself.

class Node{ //data int i; // next node in the list Node next; // previous node in the list Node prev; }

### Insertion in doubly linked list

For insertion in doubly linked list there are three scenarios-

- Inserting at the beginning of Doubly Linked List
- Inserting at the end of Doubly Linked List
- Inserting at the given index of Doubly Linked List

### Inserting at the beginning of Doubly Linked List

Inserting at the beginning has two scenarios.

If it is the first node then both head and tail should point to it.

If nodes already exist then the prev reference of the current node should point to the new node and next of new node node should reference the current first node. Head should start pointing to the inserted node.

public void insertFirst(int i){ //Create a new node Node newNode = new Node(i); // if first insertion tail should // also point to this node if(isEmpty()){ tail = newNode; }else{ head.prev = newNode; } newNode.next = head; head = newNode; size++; }

Note here that size variable is used to store the current size of the List.

### Inserting at the end of Doubly Linked List

Inserting at the end has two scenarios-

If it is the first node then both head and tail should point to it.

If nodes already exist then the current last node should reference the inserted node and prev reference of the new node should point to the current last node. Tail should start pointing to the inserted node.

public void insertLast(int i){ Node newNode = new Node(i); // if first insertion head should // also point to this node if(isEmpty()){ head = newNode; }else{ tail.next = newNode; newNode.prev = tail; } tail = newNode; size++; }

### Inserting at the given index of Doubly Linked List

Inserting at the given index has three scenarios.

If inserting at index 0 that is equivalent to insertFirst.

If inserting at index when (index == size) that is equivalent to insertLast.

Otherwise traverse to the node currently at the given index and shift the element currently at that position (and any subsequent elements)to the right.

public void insertAtIndex(int i, int index){ if(!isValidIndex(index)){ throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size); } Node newNode = new Node(i); Node current = head; //insert at the start if(index == 0){ insertFirst(i); } // insert at last else if(index == size){ insertLast(i); }else{ for(int j = 0; j < index && current.next != null; j++){ current = current.next; } newNode.next = current; current.prev.next = newNode; newNode.prev = current.prev; current.prev = newNode; size++; } }

### Doubly Linked List traversal

For a doubly linked list you can easily traverse it both forward and backward.

For forward traversal of the doubly Linked list you need to start from head and then move sequentially unless the next node reference is not null.

public void displayForward(){ Node current = head; while(current != null){ current.displayData(); current = current.next; } System.out.println(""); }

For backward traversal of the doubly Linked list you need to start from tail and then move backward unless the prev node reference is null.

public void displayBackward(){ Node current = tail; while(current != null){ current.displayData(); current = current.prev; } System.out.println(""); }

### Deleting node in Doubly Linked List

For deletion there are three scenarios-

- Delete first node of Doubly Linked List
- Delete last node of Doubly Linked List
- Delete node at given index in Doubly Linked List

### Delete first node of Doubly Linked List

For deleting the first node, in your doubly Linked list Java program you need to change the head reference so that it starts referencing the next node.

public Node deleteFirst(){ if(head == null){ throw new RuntimeException("List is empty"); } Node first = head; if(head.next == null){ tail = null; }else{ // previous of next node (new first) becomes null head.next.prev = null; } head = head.next; size--; return first; }

### Delete last node of Doubly Linked List

For deleting the last node in the doubly linked list change the reference for tail so that it starts referencing the previous node.

public Node deleteLast(){ if(tail == null){ throw new RuntimeException("List is empty"); } Node last = tail; if(head.next == null){ head = null; }else{ // next of previous node (new last) becomes null tail.prev.next = null; } tail = tail.prev; size--; return last; }

### Delete node at given index in Doubly Linked List

Deleting node at the given index has three scenarios.

If deleting node at index 0 that is equivalent to deleteFirst.

If deleting node at index when (index == size-1) that is equivalent to deleteLast.

Otherwise traverse to the node at the given index and change the references so that the node on the left of the node to be deleted starts referencing the node on the right of the node to be deleted and vice versa.

public Node deleteAtIndex(int index){ System.out.println("" + size); if(!isValidIndex(index+1)){ throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size); } Node current = head; //remove at the start if(index == 0){ return deleteFirst(); } // remove at last else if(index == size-1){ return deleteLast(); }else{ for(int j = 0; j < index && current.next != null; j++){ current = current.next; } current.prev.next = current.next; current.next.prev = current.prev; size--; } return current; }

### Doubly Linked List implementation in Java – Full Program

public class DoublyLinkedList { private Node head; private Node tail; private int size = 0; static class Node{ //data int i; // next node in the list Node next; // previous node in the list Node prev; Node(int i){ this.i = i; } public void displayData(){ System.out.print(" " + i); } } // constructor public DoublyLinkedList(){ this.head = null; this.tail = null; } public boolean isEmpty(){ return head == null; } public void insertFirst(int i){ //Create a new node Node newNode = new Node(i); // if first insertion tail should // also point to this node if(isEmpty()){ tail = newNode; }else{ head.prev = newNode; } newNode.next = head; head = newNode; size++; } public void insertLast(int i){ Node newNode = new Node(i); // if first insertion head should // also point to this node if(isEmpty()){ head = newNode; }else{ tail.next = newNode; newNode.prev = tail; } tail = newNode; size++; } public void insertAtIndex(int i, int index){ if(!isValidIndex(index)){ throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size); } Node newNode = new Node(i); Node current = head; //insert at the start if(index == 0){ insertFirst(i); } // insert at last else if(index == size){ insertLast(i); }else{ for(int j = 0; j < index && current.next != null; j++){ current = current.next; } newNode.next = current; current.prev.next = newNode; newNode.prev = current.prev; current.prev = newNode; size++; } } public Node deleteFirst(){ if(head == null){ throw new RuntimeException("List is empty"); } Node first = head; if(head.next == null){ tail = null; }else{ // previous of next node (new first) becomes null head.next.prev = null; } head = head.next; size--; return first; } public Node deleteLast(){ if(tail == null){ throw new RuntimeException("List is empty"); } Node last = tail; if(head.next == null){ head = null; }else{ // next of previous node (new last) becomes null tail.prev.next = null; } tail = tail.prev; size--; return last; } public Node deleteAtIndex(int index){ if(!isValidIndex(index+1)){ throw new IndexOutOfBoundsException("Index " + index +" not valid for linked list of size " + size); } Node current = head; //remove at the start if(index == 0){ return deleteFirst(); } // remove at last else if(index == size-1){ return deleteLast(); }else{ for(int j = 0; j < index && current.next != null; j++){ current = current.next; } current.prev.next = current.next; current.next.prev = current.prev; size--; } return current; } private boolean isValidIndex(int index){ return index >= 0 && index <= size; } // Method for forward traversal public void displayForward(){ Node current = head; while(current != null){ current.displayData(); current = current.next; } System.out.println(""); } // Method to traverse and display all nodes public void displayBackward(){ Node current = tail; while(current != null){ current.displayData(); current = current.prev; } System.out.println(""); } public static void main(String[] args) { DoublyLinkedList list = new DoublyLinkedList(); list.insertFirst(1); list.insertFirst(2); list.insertLast(3); list.insertLast(4); list.displayForward(); list.insertAtIndex(5, 3); System.out.println("Linked list backward traversal"); list.displayBackward(); System.out.println("Linked list forward traversal"); list.displayForward(); Node node = list.deleteAtIndex(2); System.out.println("Node with value "+ node.i + " deleted"); list.displayForward(); } }

__Output__

2 1 3 4 Linked list backward traversal 4 5 3 1 2 Linked list forward traversal 2 1 3 5 4 5 Node with value 3 deleted 2 1 5 4

That's all for this topic **Doubly Linked List Implementation Java Program**. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

__Related Topics__

**You may also like-**

## No comments:

## Post a Comment