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 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