The listdata class is only slightly changed to add a second pointer.
/** * This is an intermediate class that holds the data and pointer * * @author Kent Archie * @version 1/29/2002 */ import data; public class listdata { private data d; // the data element in this node private listdata next; // the pointer to the next one private listdata prev; // the pointer to the previous one /** Constructor for objects of class ListData */ public listdata() { d=null; next=null; prev=null; } public listdata(data other) { d=other; next=null; prev=null;} public listdata getNext() { return next; } public void setNext(listdata v) { next = v;} public listdata getPrev() { return prev; } public void setPrev(listdata v) { prev = v;} public data getData() { return d;} public void setData(data x) { d=x;} } // class ListDataThe llist class serves as the header record in some senses but not in others. This means that it holds pointers to both the head and tail and the length but the first element on the list doesn't point to it. This is mostly important in the delete method.
/** * This is an implementation of the list container using linked lists * * @author Kent Archie * @version 1/27/2002 */ import data; import listdata; public class llist { private listdata Head; // first entry in this list private listdata Tail; // last entry in this list private int Length; // the number of nodes in the list /** Constructor for objects of class llist */ public llist() { Head=null; Tail=null; Length=0; } /* We make a listdata node first. If there is no memory, we return false. Later this will be changed to use exceptions. Adding to the front is easy since we just set the head pointer to the new element and set the new elements next field to point to whatever the list head pointed to. If the head is null, it still works the way we want. */ public boolean addToFront(data d) { listdata my_l=new listdata(d); if( my_l == null) return false; // no memory my_l.setNext(Head); // leave the prev pointer null if(Head != null) Head.setPrev(my_l); if(Tail == null) Tail = my_l; // first one Head = my_l; Length++; return true; } // addToFront /* Like addToFront(), we first create a listdata node and add the data to it. Then we have to find the last element of the list. We do this in a loop where we check if the pointer is null and if it isn't, check if its next is null. We want to stop when the pointer is referring to the last element. If the pointer is null when we leave the loop, then the list was empty and we just point the Head pointer at it. Otherwise, we change the next pointer of the last one to point to the one we just added. */ public boolean addToEnd(data d) { listdata my_l; if( (my_l = new listdata(d)) == null) return false; // no memory Length++; // if the tail pointer is null, so must the head pointer if(Tail == null) Head = Tail = my_l; // first entry else { Tail.setNext(my_l); // make the last one point to the new one my_l.setPrev(Tail); Tail = my_l; } return true; } // addToEnd public int getLength() { return Length; } /* we will provide 2 interfaces for searching. One will take two integers and make a data object. The other will take a data object. Both will simply call the search routine to do the actual work. These are provided as a convenience to the user. */ public listdata find(int a, int b) { return search(new data(a,b)); } public listdata find(data target) { return search(target); } /* We start at the front of the list and look at each element checking if the data item stored there is the same as one we passed in. */ private listdata search(data target) { for(listdata lptr = Head; lptr != null; lptr = lptr.getNext()) if(lptr.getData().equals(target)) return lptr; return null; // if we get here, we didn't find it } // find // walk the list and print each data item public void printList() { for(listdata lptr = Head; lptr != null; lptr = lptr.getNext()) System.out.println(lptr.getData()); } // printList /* addBefore() takes two data objects as parameters. The first (target) is used as the parameter to the search routine. If we find the node, we insert the second (newone) before the found one. */ public boolean addBefore(data target,data newone) { listdata t; if( ( t = search(target)) == null) return false; // didn't find it // t now points to the target node in the list listdata n = new listdata(newone); Length++; n.setPrev(t.getPrev()); // n to prev n.setNext(t); // n to t (t.getPrev()).setNext(n); // prev to n t.setPrev(n); // t to n return true; } // addBefore /* addAfter() takes two data objects as parameters. The first (target) is used as the parameter to the search routine. If we find the node, we insert the second (newone) after the found one. */ public boolean addAfter(data target,data newone) { listdata t; if( ( t = search(target)) == null) return false; // didn't find it // t now points to the target node in the list listdata n = new listdata(newone); // make a new node Length++; n.setNext(t.getNext()); // n to target next n.setPrev(t); // n to t (t.getNext()).setPrev(n); // target next to n t.setNext(n); // t to n if( t == Tail) Tail = n; return true; } // addAfter public boolean delete(data target) { listdata t; if( ( t = search(target)) == null) return false; // didn't find it // t now points to the target node in the list // some special cases are handled first // first (or only) one Length--; if(Head == t) { System.out.println("Deleting first node"); if(t.getNext() != null) { (t.getNext()).setPrev(null); // new first one } Head = t.getNext(); return true; } // head == t // last one if(Tail == t) { System.out.println("Deleting last node"); Tail = Tail.getPrev(); Tail.setNext(null); return true; } // Tail == t // now the general case where it is between to other nodes System.out.println("Deleting middle node"); (t.getPrev()).setNext(t.getNext()); // prev to next (t.getNext()).setPrev(t.getPrev()); // next to prev return true; } // delete // return the first object from the list public listdata getFirst() { return Head;} /* first set the second (if there is one) to be the new first. Then point the head to this one. If the list is now empty, fix the tail pointer. */ public void chop() { System.out.println("starting chop"); if(Head == null) return; if(Head.getNext() == null) { Head = Tail = null; Length=0; return; } (Head.getNext()).setPrev(null); Head = Head.getNext(); Length--; } // chop } // class llistHere is the driver class and the results from running it.
/** * Driver for the array implementation of a list * * @author Kent Archie * @version 1/27/2002 */ import llist; public class main { public static void main(String[] args) { llist joe = new llist(); joe.addToFront(new data(1,42)); joe.addToFront(new data(2,43)); joe.addToEnd(new data(3,44)); joe.printList(); System.out.println("There are " + joe.getLength() + " items in the list"); look(joe,1,42); look(joe,2,43); look(joe,2,454); System.out.println("\nAdding before (3,44)"); if(joe.addBefore(new data(3,44), new data(4,44))) System.out.println("target found"); else System.out.println("target not found"); System.out.println("after addBefore"); joe.printList(); System.out.println("There are " + joe.getLength() + " items in the list"); System.out.println("\nAdding after (2,43)"); if(joe.addAfter(new data(2,43), new data(5,45))) System.out.println("target found"); else System.out.println("target not found"); System.out.println("after addAfter"); joe.printList(); System.out.println("There are " + joe.getLength() + " items in the list"); System.out.println("\nDeleting (5,45)"); if(joe.delete(new data(5,45))) System.out.println("target found"); else System.out.println("target not found"); System.out.println("after delete"); joe.printList(); System.out.println("There are " + joe.getLength() + " items in the list"); System.out.println("\nDeleting first (2,43)"); if(joe.delete(new data(2,43))) System.out.println("target found"); else System.out.println("target not found"); System.out.println("after delete"); joe.printList(); System.out.println("There are " + joe.getLength() + " items in the list"); System.out.println("\nDeleting last (3,44)"); if(joe.delete(new data(3,44))) System.out.println("target found"); else System.out.println("target not found"); System.out.println("after delete"); joe.printList(); System.out.println("There are " + joe.getLength() + " items in the list"); System.out.println("\nGetting the first one"); listdata l = joe.getFirst(); if(l == null) System.out.println("There is no first one"); else { System.out.println("The first one is " + l.getData()); } System.out.println("There are " + joe.getLength() + " items in the list"); System.out.println("\nDeleting the first one"); joe.chop(); joe.printList(); System.out.println("There are " + joe.getLength() + " items in the list"); } // main // look for the item indicated in the list passed. print results private static void look(llist l, int a, int b) { listdata results = l.find(new data(a,b)); if(results != null) System.out.println("Item(" + a + "," + b + ") found"); else System.out.println("Item(" + a + "," + b + ") not found"); } // look } // class main
target found after addAfter x= 2 y= 43 x= 5 y= 45 x= 1 y= 42 x= 4 y= 44 x= 3 y= 44 There are 5 items in the list Deleting (5,45) Deleting middle node target found after delete x= 2 y= 43 x= 1 y= 42 x= 4 y= 44 x= 3 y= 44 There are 4 items in the list Deleting first (2,43) Deleting first node target found after delete x= 1 y= 42 x= 4 y= 44 x= 3 y= 44 There are 3 items in the list Deleting last (3,44) Deleting last node target found after delete x= 1 y= 42 x= 4 y= 44 There are 2 items in the list Getting the first one The first one is x= 1 y= 42 There are 2 items in the list Deleting the first one starting chop x= 4 y= 44 There are 1 items in the list