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