Tuesday, February 26, 2019

Doubly Linked List Implementation Java Program

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.

doubly linked list in Java

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-

  1. Insertion in doubly linked list
  2. Doubly Linked List traversal
  3. Deleting node in Doubly Linked List
  4. 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-

  1. Inserting at the beginning of Doubly Linked List
  2. Inserting at the end of Doubly Linked List
  3. 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.

doubly linked list insertion
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

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

  1. How to Reverse a Linked List in Java
  2. Deque Implementation in Java Using Doubly Linked List
  3. Find Minimum and Maximum Value Nodes in Binary Search Tree - Java Program
  4. Converting String to Enum Type - Java Program
  5. How to Display Pyramid Patterns in Java - Part1

You may also like-

  1. Setting And Getting Thread Name And Thread ID - Java Program
  2. Creating PDF in Java Using iText
  3. How to Create Password Protected Zip File in Java
  4. Difference Between Two Dates in Java
  5. Invoke Method at Runtime Using Java Reflection API
  6. Difference Between Abstract Class And Interface in Java
  7. Spring Batch Processing Using JDBCTemplate batchUpdate() Method
  8. HDFS Federation in Hadoop Framework