Implementing Doubly Linked List in Java

This post talks about doubly linked list implementation in Java. Fundamentals of linked list and single linked list is discussed in one of the earlier post here.

In doubly linked list, there is one more reference/pointer to store previous element of  the list. So, you can traverse the list in either direction (unlike single linked list where you can traverse only forward).
Java platform provides inbuilt API for doubly linked list; so as a developer you don't need to re-invent the wheel. But at times you need to implement it to solve some specific problem.

Dobubly linked list with next and previous references

 

Java Implementation

package algo;  
   
 /**  
  * Double Linked List  
  *   
  * @author Siddheshwar  
  */  
 public class DoublyLinkedList<E> {  
      Node<E> start;  
      Node<E> end;  
   
      private class Node<E> {  
           Node<E> prev;  
           E data; // the data stored in this node  
           Node<E> next;  
   
           public Node(Node<E> prev, E data, Node<E> next) {  
                this.prev = prev;  
                this.data = data;  
                this.next = next;  
           }  
   
           public Node<E> getPrev() {  
                return prev;  
           }  
   
           public void setPrev(Node<E> prev) {  
                this.prev = prev;  
           }  
   
           public E getData() {  
                return data;  
           }  
   
           public void setData(E data) {  
                this.data = data;  
           }  
   
           public Node<E> getNext() {  
                return next;  
           }  
   
           public void setNext(Node<E> next) {  
                this.next = next;  
           }  
      }  
   
      /**  
       * prev of first points to null and next of last also points to null also  
       * start points to first and end points to last  
       */  
      public void addTail(E d) {  
           if (start == null) {  
                Node<E> t = new Node<E>(null, d, null);  
                start = t;  
                end = t;  
           } else {  
                Node<E> lastNode = end;  
                Node<E> t = new Node<E>(null, d, null);  
                t.setPrev(lastNode);  
                lastNode.setNext(t);  
                end = t;  
           }  
      }  
   
      public void addAtHead(E d) {  
           if (start != null) {  
                Node<E> t = new Node<E>(null, d, null);  
                Node<E> tmp = start;  
                tmp.setPrev(t);  
                t.setNext(tmp);  
                start = t;  
           } else { // if list is empty then call normal add operation  
                addTail(d);  
           }  
      }  
   
      public void print() {  
           Node<E> current = start;  
           System.out.print(" values in link-list from beginning :");  
           while (current.next != null) {  
                System.out.print(current.getData() + ", ");  
                current = current.getNext();  
           }  
           System.out.print(current.getData()); // print last node  
      }  
   
      public void printFromLast() {  
           System.out.print(" values in link-list from end are :");  
           Node<E> current = end;  
           while (current.getPrev() != null) {  
                System.out.print(current.getData() + ", ");  
                current = current.getPrev();  
           }  
           System.out.print(current.getData()); // print last node  
      }  
   
      public static void main(String[] args) {  
           DoublyLinkedList<Integer> sll = new DoublyLinkedList<Integer>();  
           sll.addTail(1);  
           sll.addTail(2);  
           sll.addTail(3);  
           sll.addTail(4);  
           sll.addAtHead(0);  
   
           sll.print();  
           System.out.println();  
           sll.printFromLast();  
      }  
 }  

Output:

values in link-list from beginning :0, 1, 2, 3, 4
 values in link-list from end are :4, 3, 2, 1, 0

Related Post :Implementing Single linked list in Java