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

Merge Two Sorted Linked Lists

This post talks about, merging two sorted linked lists into one sorted linked list. The implementation doesn't use any extra space(except head node overhead). It's implemented below in Java, but same approach can be applied in any programming language.

Merge method takes two sorted linked lists as arguments and returns the head of the final merged linked list.

First Linked List       1 -->6 -->13 -->49 -->114 -->null

Second Linked List   5 -->9 -->23 -->null

Merged Linked List  1 -->5 -->6 -->9 -->13 -->23 -->49 -->114 -->null

The merge method uses a new node i.e. merged to generate the merged list. It starts with the smallest node of either list and keeps on adding the next larger node (in while loop). Method will come out of the while loop if either of the lists is traveled fully. Then the remaining nodes of other list get appended to the end of merged list.

 package algo;  
   
 /**  
  * LinkedList implementation which merges two sorted linkedlists without using  
  * any extra space (except overhead of head)  
  *   
  * @author Siddheshwar  
  *   
  */  
 public class MergeLinkedList<E extends Comparable<E>> {  
      Node<E> head;  
   
      /**  
       * merges two sorted linked lists and returns node of the merged list  
       *   
       */  
      public Node<E> merge(Node<E> n1, Node<E> n2) {  
           Node<E> merged = null; // pointer for merged list  
           Node<E> resp = null; // head of merged list  
   
           if (n1 == null)  
                return n2;  
           if (n2 == null)  
                return n1;  
   
           int cmp = 0;  
           while (n1 != null && n2 != null) {  
                cmp = n1.compareTo(n2);  
                if (merged == null) {  
                     if (cmp < 0) {  
                          merged = n1;  
                          n1 = n1.next;  
                     } else {  
                          merged = n2;  
                          n2 = n2.next;  
                     }  
                     resp = merged; // points to head of merged list  
                } else {  
                     if (cmp < 0) {  
                          merged.next = n1;  
                          n1 = n1.next;  
                          merged = merged.next;  
                     } else {  
                          merged.next = n2;  
                          n2 = n2.next;  
                          merged = merged.next;  
                     }  
                }  
           }  
   
           // append the remaining nodes of the either list  
           if (n1 == null)  
                merged.next = n2;  
           else  
                merged.next = n1;  
   
           return resp;  
      }  
   
      /**  
       * Node implementation which forms linked list  
       *   
       */  
      private static class Node<E extends Comparable<E>> implements  
                Comparable<Node<E>> {  
           E data;  
           Node<E> next;  
   
           public Node(E data, Node<E> next) {  
                super();  
                this.data = data;  
                this.next = next;  
           }  
   
           @Override  
           public String toString() {  
                return "Node [data=" + data + "]";  
           }  
   
           @Override  
           public int compareTo(Node<E> node) {  
                return this.data.compareTo(node.data);  
           }  
      }  
   
      public void addNodeLast(E d) {  
           if (head == null) {  
                head = new Node<E>(d, null);  
                return;  
           }  
           Node<E> h = head;  
           while (h.next != null)  
                h = h.next;  
           h.next = new Node<E>(d, null);  
      }  
   
      public void print() {  
           Node<E> h = head;  
           while (h != null) {  
                System.out.print(h.data + " -->");  
                h = h.next;  
           }  
           System.out.println("null");  
      }  
   
      public void print(Node<E> head) {  
           Node<E> h = head;  
           while (h != null) {  
                System.out.print(h.data + " -->");  
                h = h.next;  
           }  
           System.out.println("null");  
      }  
   
      /**  
       * Main method for testing  
       */  
      public static void main(String[] args) {  
           /**  
            * First linked list  
            */  
           MergeLinkedList<Integer> l1 = new MergeLinkedList<>();  
           l1.addNodeLast(1);  
           l1.addNodeLast(6);  
           l1.addNodeLast(13);  
           l1.addNodeLast(49);  
           l1.addNodeLast(114);  
           System.out.print("First Linked List :");  
           l1.print(l1.head);  
   
           /**  
            * Second linked list  
            */  
           MergeLinkedList<Integer> l2 = new MergeLinkedList<>();  
           l2.addNodeLast(5);  
           l2.addNodeLast(9);  
           l2.addNodeLast(23);  
           System.out.print("Second Linked List :");  
           l2.print(l2.head);  
   
           /**  
            * Final, merged linked list  
            */  
           MergeLinkedList<Integer> mergedList = new MergeLinkedList<>();  
           mergedList.head = mergedList.merge(l1.head, l2.head);  
           System.out.print("Merged Linked List :");  
           mergedList.print(mergedList.head);  
      }  
 }  
   

I have implemented it in Java using Generics so that you can store any type of object in the node. One of the tricky aspects is the implementation of the Comparable interface. 

Note that compareTo(..) method in the Node class basically compares the data stored in the node. And it assumes that the data is comparable. This will be perfectly fine as long as you are using inbuilt classes like String, Integer as they implement Comparable. But if you need to compare your own custom object (say Student, Animal), make sure that the class implements the Comparable interface.

Binary Search Tree Implementation in Java

Binary Search Tree is a special type of Binary Tree where nodes are arranged in order: for each node, all elements in its left subtree are less than the node, and all elements in its right subtree are greater-or-equal to the node. Binary search trees are efficient in insert and lookup operations. On average it can locate a node in lg(n) time (i.e. log base 2).

BST is also known as Ordered Binary Tree. Below is the Java code of a binary search tree. The attribute, root of the class points to the root node of the tree. The nested Node<E> class is made private, as it is used only for internal storage inside the binary search tree and is not exposed for clients. Also, Node<E> encapsulates the state properly and exposes them only through interfaces (i.e. getters and setters).

   
 /**  
  * Java implementation of a Binary Search Tree through a generic node. You can  
  * store any data type in it provided compareTo method is properly implemented  
  *  
  * @author Siddheshwar  
  */  
   
 public class BST<E extends Comparable<E>> {  
      /**  
       * Pointer to the root node of the tree  
       */  
      Node<E> root;  
   
      /**  
       * Adds a new node to the tree  
       */  
      public void add(Node<E> t) {  
           if (t == null)  
                return;  
   
           if (root == null) {  
                root = t;  
           } else {  
                Node<E> r = root; // required so that root doesn't get overridden  
                add(r, t);  
           }  
      }  
   
      /**  
       * Internal method to add node to the tree  
       */  
      private void add(Node<E> root, Node<E> t) {  
           if (root == null || t == null)  
                return;  
   
           int cmp = t.compareTo(root);  
   
           if (cmp >= 0) {  
                if (root.getRight() != null)  
                     add(root.getRight(), t);  
                else {  
                     root.setRight(t);  
                     return;  
                }  
           }  
           if (cmp < 0) {  
                if (root.getLeft() != null)  
                     add(root.getLeft(), t);  
                else {  
                     root.setLeft(t);  
                     return;  
                }  
           }  
      }  

      /**  
       * In-order traversal method to print the tree in sorted way  
       */  
      public void inorderTraversal(Node<E> root) {  
           if (root != null) {  
                inorderTraversal(root.getLeft());  
                System.out.print(root.getData() + " ");  
                inorderTraversal(root.getRight());  
           }  
      }  
   
      /**  
       * Node class to represent each node of the tree  
       */  
      private class Node<E extends Comparable<E>> implements Comparable<Node<E>> {  
           E data;  
           Node<E> left;  
           Node<E> right;  
   
           public Node(E d) {  
                this.data = d;  
                this.left = null;  
                this.right = null;  
           }  

           public E getData() {  
                return data;  
           }  
   
           public Node<E> getLeft() {  
                return left;  
           }  
   
           public void setLeft(Node<E> left) {  
                this.left = left;  
           }  
   
           public Node<E> getRight() {  
                return right;  
           }  
   
           public void setRight(Node<E> right) {  
                this.right = right;  
           }  
   
           @Override  
           public int compareTo(Node<E> node) {  
                return this.data.compareTo(node.data);  
           }  
      }  
   
      /**  
       * Creates a new node and then adds it to the tree  
       */  
      private void insert(int num) {  
           Node<Integer> t = new Node<Integer>(num);  
           add((Node<E>) t);  
      }  
   
      /**  
       * Method to test the tree construction  
       */  
      public static void main(String[] args) {  
           BST<Integer> bst = new BST<Integer>();  
           bst.insert(10);  
           bst.insert(20);  
           bst.insert(5);  
           bst.insert(50);  
           bst.insert(7);  
           bst.insert(7);  
           System.out.println(" Tree in Sorted order :");  
           bst.inorderTraversal(bst.root);  
      }  
 }  
   

Output:
Tree in Sorted order :
5 7 7 10 20 50

Some Important Problems on Binary Tree :
http://cslibrary.stanford.edu/110/BinaryTrees.html

Related Post : Linkedlist Implementation in Java

Quicksort Implementation

Quicksort is a divide-and-conquer algorithm which centers around efficiently choosing the pivot value from the input data set. Based on this pivot value, the list is divided into two sublists - the first sublist containing all values less than or equal to the pivot and the second sublist containing all values greater than the pivot. This procedure is recursively called on these two sub lists.

Wikipedia has an interesting animation.

Below algorithm sorts array in-place and without using any extra space ( except the temporary holder, tmp). The algorithm selects the first element of the array as pivot value, but you can choose any value as the pivot.

Java Implementation 

package algo;

/**
 * QuickSort implemention
 * 
 * @author Siddheshwar
 * 
 */
public class QuickSort {

 /**
  * This method actually partitions the array in two sub parts. Doing
  * recursively the same, sorts the array as well
  * 
  */
 static int[] partition(int[] a, int low, int high) {
  int pi = low;
  int pivot = a[pi];
  int i = low, j = high;

  while (i < j) {
   // i should not exceed the high bound
   while (a[i] <= pivot && i < high)
    i++;

   // j should not reduce below low bound
   while (a[j] > pivot && j >= i)
    j--;

   if (i < j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
   }
  }

  // j is the final position for pivot element
  int tmp = a[j];
  a[j] = pivot;
  a[pi] = tmp;
  pi = j;

  // just for testing
  logging(a, pi);

  // do the same for lower and higher sub arrays
  if (low < pi - 1) {
   partition(a, low, pi - 1);
  }
  if (pi + 1 < high) {
   partition(a, pi + 1, high);
  }

  return a;
 }

 /**
  * Print array after each iteration to see how this sort works
  * 
  */
 public static void logging(int[] a, int pi) {
  for (int t : a) {
   System.out.print(t + " ");
  }
  System.out.println("\nPivot index :" + pi + "; Pivot :" + a[pi]);
 }

 public static void main(String[] args) {
  // int[] a = {0,666,1, 10, 30, 5, 19, 10};
  // int[] a = {1,1,1,1,1,1,1};
  // int[] a = {1,2,1,2,1,2,1};

  int[] a = { 0, 666, 2, 2, 2, 2, 45, 2, 3, 3, 3, 3 };
  a = QuickSort.partition(a, 0, a.length - 1);

  System.out.println("\nsorted array");
  for (int t : a) {
   System.out.print(t + " ");
  }
 }
}

Output:
0 666 2 2 2 2 45 2 3 3 3 3
Pivot index :0; Pivot :0
0 3 2 2 2 2 45 2 3 3 3 666
Pivot index :11; Pivot :666
0 3 2 2 2 2 3 2 3 3 45 666
Pivot index :9; Pivot :3
0 3 2 2 2 2 3 2 3 3 45 666
Pivot index :8; Pivot :3
0 2 2 2 2 2 3 3 3 3 45 666
Pivot index :7; Pivot :3
0 2 2 2 2 2 3 3 3 3 45 666
Pivot index :5; Pivot :2
0 2 2 2 2 2 3 3 3 3 45 666
Pivot index :4; Pivot :2
0 2 2 2 2 2 3 3 3 3 45 666
Pivot index :3; Pivot :2
0 2 2 2 2 2 3 3 3 3 45 666
Pivot index :2; Pivot :2

sorted array
0 2 2 2 2 2 3 3 3 3 45 666 

Important points

• Performance of the algorithm depends a lot on the choice of pivot value. If it divides the array in two almost equal sized array, run time complexity will be O(n log n). Worst case complexity for Quicksort is O(n^2).
• It also takes O(log n) stack space on an average.
• You can also consider using a stack to eliminate recursion.
• On a small array, Insertion Sort is faster than Quicksort. So you can consider using Insertion sort if the size of the array is small. 

References

http://algs4.cs.princeton.edu/23quicksort/

--
keep coding !!!