Monday, 28 July 2014

Doubly Linked List using Java

An implementation of basic classes required for  Doubly Linked List using Java

class - DNode  -  the class to initialise node objects for the list
           DblyLinkedList -  the class to build ours doubly linked list

The sentinels for the list are - head and trailer
Code is well commented for visualising the whole  scenario  




 /*
 * @class Dnode for creating nodes  of a doubly linked list
 */
public class DNode {
  
    // node's data
     private String data ;
    
     // node's next and previous pointer variables
     private DNode next , prev ;
    
     //constructor initialisng the node
     public DNode(DNode next ,  DNode prev , String data ){
         this.next = next;
         this.prev = prev ;
         this.data = data;
        
     }
    
     //getters and setters for a  node
     public DNode getNext()
     {
         return this.next;
     }
     public DNode getPrev()
     {
         return this.prev;
     }
     public String  getData()
     {
          return this.data;
     }
     public void  setNext(DNode newNext)
     {
          this.next = newNext;
     }
     public void  setPrev(DNode newPrev)
     {
          this.next = newPrev;
     }
     public void setData(String newData)
     {
         this.data = newData;
     }
  



-------------------------------------------------
  /*
 *  @class DblyLinkedList for creating a doubly linked list using objects of DNode class as nodes
 */
public class DblyLinkedList {
    //header and trailer sentinels of a list
    //the header and trailer have their previous and
    //next node object pointer variables as null respectively
    private DNode head ,trailer ;
    private static int size ;
   
    //constructor initialise the doubly linked list
    //with size zero and head and trailer sentinels pointing eachother
    public DblyLinkedList()
    {
         DblyLinkedList.size = 0;
         this.head =  new DNode(null,null,null);
         this.trailer =  new DNode(null ,head , null );
         this.head.setNext(trailer);
    }
   
    //returns the total nodes in list
    public int getSize()
    {
        return DblyLinkedList.size;
    }
   
    //returns whether the list is empty
    public boolean isEmpty()
    {
        return ( DblyLinkedList.size == 0 );
    }
   
    //returns the first node of list
    public DNode getFirst() throws IllegalStateException
    {
        if(isEmpty()) throw new IllegalStateException("The list is empty ");
        return head.getNext();
    }
   
    //returns the last node of list
    public DNode getLast() throws IllegalStateException
    {
        if(isEmpty()) throw new IllegalStateException("The list is empty ");
        return trailer.getPrev();
    }
   
    // returns the node before a given node v
    // error occurs if the given node v is head
    //returns the first node of list
    public DNode getNext(DNode v) throws IllegalStateException
    {
        if(v == head) throw new IllegalStateException("Cannot move past the header itself");
        return v.getNext();
    }
   
    //inserts a given node z before a given node v
    // error occurs if v is a header
    public void insertBefore(DNode v ,DNode z) throws IllegalArgumentException
    {
        DNode u = v.getPrev(); // may throw an IllegalArgumentException
        z.setNext(v);
        z.setPrev(u);
        u.setNext(z);
        v.setPrev(z);
        DblyLinkedList.size++;
       
    }
    //inserts a given node z after a given node v
    // error occurs if v is a trailer
    public void insertAfter(DNode v ,DNode z)
    {
        DNode w = v.getNext(); // may throw an IllegalArgumentException
        z.setNext(w);
        z.setPrev(v);
        v.setNext(z);
        w.setPrev(z);
        ++DblyLinkedList.size;
       
    }
   
    // inserts a given node at head
    public void insertAtHead(DNode z)
    {
        insertAfter(head,z);
    }
   
    // insert a given node at tail
    public void insertAtTail(DNode z)
    {
        insertBefore(trailer,z);   
    }
   
    //removes a given node v from list
    // error occurs if v is a among sentinels head or trailer
    public void removeNode(DNode v)
    {
        DNode u =  v.getPrev();// may throw an IllegalArgumentException
        DNode w  = v.getNext();// may throw an IllegalArgumentException
       
        //make u and w point eachother
        u.setNext(w);
        w.setPrev(u);
       
        //null out pointer references of given node v to remove it
        v.setNext(null); v.setPrev(null);
       
        //decrement the size of list
        --DblyLinkedList.size;
       
    }
   
    //returns whether a given node z has a previous node
    public boolean hasPrev(DNode z)
    {
        return ( z != head ) ;
    }
   
    //returns whether a given node z has a next node
    public boolean hasNext(DNode z)
    {
        return ( z != trailer ) ;
    }
   
    // returns a string representation of  the list
    public String toString()
    {
        String s = "[ ";
        DNode v = head.getNext();
       
        while(v != trailer)
        {
            s +=  v.getData();
            v = v.getNext();
            if( v != trailer )
            {
                s += " ," ;
            }
            else
            {
                s += " ]" ;
                break;
            }
        }
        return s;
    }
   
  }


No comments:

Post a Comment