Saturday, May 12, 2012

Singly linked list implementation in java

I used generics here to write this.

public class Node {
   private E data = null;
   private Node nextNode = null;

   public Node(E data){   
     this.data = data;
     this.nextNode = null;
   }

   public Node(){   
   }

   public E getData() {
       return data;
   }

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

   public Node getNextNode() {
       return nextNode;
   }

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


public class SinglyLinkedList {
     private Node headNode = null;
     private Node tailNode = null;
     private int nodeCount = 0;    

     public void addFirst(E data){  // add to the head
       Node newNode = new Node(data);      

       if(headNode == null && tailNode == null){ // if list is empty, newNode is both the head and tail
           headNode = tailNode = newNode;                        
       }

       else{  // make newly added node as head node
           newNode.setNextNode(headNode);
           headNode = newNode;                             
       }

       nodeCount++;  
     }

    

     public void addLast(E data){ // add to the tail
       Node newNode = new Node(data);

       if(headNode == null && tailNode == null){ // if list is empty, newNode is both the head and tail
          headNode = tailNode = newNode;                        
       }

       else{ // make newly added node as tail node
          tailNode.setNextNode(newNode);
          tailNode = newNode;                 
       }
       nodeCount++;
     }    

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

       while(curNode != null){
             if(curNode.getData().equals(data)){   //find the node which has the data
                  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             
                     curNode.setNextNode(null); // set the next node of the previous head node (cur node) to null 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
                  }
                  
                  else{
                    prevNode.setNextNode(curNode.getNextNode());  // make the prev node point to next node of cur node
                    curNode.setNextNode(null); // make cur node not point to next node                             
                  }
 
                  nodeCount--;
                  return true;  //return true to say that data is found and is deleted 
             }

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

    
     public void displayLinkedList(){
       Node 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 class TestLinkedList {
   public static void main(String [] args){
      SinglyLinkedList list = new SinglyLinkedList();
      
      list.addFirst(1);
      list.addFirst(2);
      list.addLast(3);
      list.addLast(4);
      list.addFirst(5);
  
      list.displayLinkedList();

      list.delete(5);
      list.delete(4);  

      list.displayLinkedList();

   }
}

No comments:

Post a Comment