Saturday, May 12, 2012

Doubly linked list implementation in java

I used generics here to write this.

public class DLLNode {
   private E data = null;
   private DLLNode prevNode = null;
   private DLLNode nextNode = null;

   public E getData() {
     return data;
   }

   public void setData(E data) {
     this.data = data;
   }

   public DLLNode getPrevNode() {
     return prevNode;
   }

   public void setPrevNode(DLLNode prevNode) {
     this.prevNode = prevNode;
   }

   public DLLNode getNextNode() {
     return nextNode;
   }

   public void setNextNode(DLLNode nextNode) {
     this.nextNode = nextNode;
   }
}


public class DoublyLinkedList {
  private DLLNode headNode = null;
  private DLLNode tailNode = null;
  private int nodeCount = 0;

  public void addFirst(E data){
    DLLNode newNode = new DLLNode();
    newNode.setData(data);

    if(headNode == null && tailNode == null){
       headNode = tailNode = newNode;  //new node becomes both head and tail
    }
 
    else{            
       newNode.setNextNode(headNode);
       headNode.setPrevNode(newNode);
       headNode = newNode;
    }

    nodeCount++;     
 }

 public void addLast(E data){
    DLLNode newNode = new DLLNode();
    newNode.setData(data);

    if(headNode == null && tailNode == null){
       headNode = tailNode = newNode;  //new node becomes both head and tail
    }

    else{            
       tailNode.setNextNode(newNode);
       newNode.setPrevNode(tailNode);
       tailNode = newNode;
    }

    nodeCount++;     
  }

  public boolean delete(E data){
     DLLNode curNode = headNode;
     DLLNode prevNode = headNode;

     while(curNode != null){
        if(curNode.getData().equals(data)){   //find the node which has the data
              prevNode = curNode.getPrevNode();

              if(nodeCount == 1){ // if there is only node in the list, and that one node contains the data to be deleted
                  headNode = tailNode = null; // now both head and tail points nowhere                             
               }   
  
              else if(curNode == headNode){
                  headNode = headNode.getNextNode(); // move the head node to next node
                  headNode.setPrevNode(null); // make new head node's  prev node value as null
                  curNode.setNextNode(null); // set the next node of the previous head node (cur node) to null                                      
               }

         else if(curNode == tailNode){
                  tailNode = prevNode;       // make the tail node as previous node
                  tailNode.setNextNode(null); //set the next node of tail node as null, as this is the tail node
                  curNode.setPrevNode(null);  //make cur node not point to prev node                       
                }

               else{
                  prevNode.setNextNode(curNode.getNextNode());  // make the prev node point to next node of cur node
                  curNode.getNextNode().setPrevNode(prevNode);  //make next node point to pren node
                  curNode.setNextNode(null); // make cur node not point to next node
                  curNode.setPrevNode(null); // make cur node not point to prev node                       
                }

                nodeCount--;
                return true;  //return true to say that data is found and is deleted 
             }           
             curNode = curNode.getNextNode();
      }
      return false;  // //return false to say that data is not found and is not deleted
  }


  public void displayLinkedListFromHead(){
      DLLNode node = headNode;
      System.out.println("Node Count: " + nodeCount);
      if(headNode != null){
          System.out.println("Head Node: " + headNode.getData());
          System.out.println("Tail Node: " + tailNode.getData());
      }

      while(node != null){
          System.out.println(node.getData().toString());
          node = node.getNextNode();
      }
 }    

  public void displayLinkedListFromTail(){
      DLLNode node = tailNode;
      System.out.println("Node Count: " + nodeCount);
      if(headNode != null){
           System.out.println("Head Node: " + headNode.getData());
           System.out.println("Tail Node: " + tailNode.getData());
      }

      while(node != null){
           System.out.println(node.getData().toString());
           node = node.getPrevNode();
      }

    }    
}

public class TestDLL {
    public static void main(String[] args){
       DoublyLinkedList list = new DoublyLinkedList();
       list.addFirst(1);
       list.addFirst(2);
       list.addLast(3);
       list.addLast(4);

       //list.delete(2);
       //list.delete(3);
       //list.delete(2);
       list.delete(4);
  
       list.displayLinkedListFromHead();
       list.displayLinkedListFromTail();
      }
}

No comments:

Post a Comment