A circular list is a linked list in which the last link points back to the first link. There are many ways to design a circular list. Sometimes there is a pointer to the start of the list. However, this makes the list less like a real circle and more like an ordinary list that has its end attached to its beginning. Make a class for a singly linked circular list that has no end and no beginning. The only access to the list is a single reference, current, that can point to any link on the list. This reference can move around the list as needed. (See Programming Project 5.5 for a situation in which such a circular list is ideally suited.)

Your list should handle insertion, searching, and deletion. You may find it convenient if these operations take place one link downstream of the link pointed to by current. (Because the upstream link is singly linked, you cant get at it without going all the way around the circle.) You should also be able to display the list (although youll need to break the circle at some arbitrary point to print it on the screen). A step()method that moves current along to the next link might come in handy too.

The code base of the list is this:

class Link { public int iData; // data item public double dData; // data item public Link next; // next link in list // ------------------------------------------------------------- public Link(int id, double dd) // constructor { iData = id; // initialize data dData = dd; // ('next' is automatically } // set to null) // ------------------------------------------------------------- public void displayLink() // display ourself { System.out.print("{" + iData + ", " + dData + "} "); } } // end class Link

//////////////////////////////////////////////////////////////// class LinkList { private Link first; // ref to first link on list

// ------------------------------------------------------------- public LinkList() // constructor { first = null; // no links on list yet } // ------------------------------------------------------------- public boolean isEmpty() // true if list is empty { return (first==null); } // ------------------------------------------------------------- // insert at start of list public void insertFirst(int id, double dd) { // make new link Link newLink = new Link(id, dd); newLink.next = first; // newLink --> old first first = newLink; // first --> newLink } // ------------------------------------------------------------- public Link deleteFirst() // delete first item { // (assumes list not empty) Link temp = first; // save reference to link first = first.next; // delete it: first-->old next return temp; // return deleted link } // ------------------------------------------------------------- public void displayList() { System.out.print("List (first-->last): "); Link current = first; // start at beginning of list while(current != null) // until end of list, { current.displayLink(); // print data current = current.next; // move to next link } System.out.println(""); } // ------------------------------------------------------------- } // end class LinkList ////////////////////////////////////////////////////////////////

class LinkListApp { public static void main(String[] args) { LinkList theList = new LinkList(); // make new list

theList.insertFirst(22, 2.99); // insert four items theList.insertFirst(44, 4.99); theList.insertFirst(66, 6.99); theList.insertFirst(88, 8.99);

theList.displayList(); // display list

while( !theList.isEmpty() ) // until it's empty, { Link aLink = theList.deleteFirst(); // delete link System.out.print("Deleted "); // display it aLink.displayLink(); System.out.println(""); } theList.displayList(); // display list } // end main() } // end class LinkListApp