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(); } }
Saturday, May 12, 2012
Doubly linked list implementation in java
I used generics here to write this.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment