Problems with implementing circularly linked list of strings

[jhamill]

okay, i am trying to implement a program that cycles through a circularlly linked list to find different strings "assassins" and then eliminate the next person in the list. I believe that most of my code is correct with the exception of how I set up my linked list as circular. I have spent many hours trying to figure this out with no luck so any and all help is appreciated. I set rear.next = front which i thought would make the list circular, and I tried countless other methods. As of right now my it works properly when i delete rear.next = front until it needs to loop back to the beginning, and nothing prints to the console at all if I do include rear.next = front....... I am very confused. here is my add method which I believe to be the source of the problem followed by the rest of my code for reference. Thanks so much.

public void add (String s){

        if (front == null) {
            front = rear = new ListItem ();
            front.data = s;
            //          front.next = rear;
            rear = front;   
        }
        else {
            rear.next = new ListItem();
            rear = rear.next;
            rear.data = s;
            rear.next = front;
        }
        numItems ++;
    }

And the rest of it

import java.util.LinkedList;


class ListItem {

    String data;
    ListItem next;

}


class CircularList {

    // The usual list variables.
    ListItem front = null;
    ListItem rear = null;
    ListItem last = null;
    // To keep track of the size.
    int numItems = 0;


    public void add (String s){

        if (front == null) {
            front = rear = new ListItem ();
            front.data = s;
            //          front.next = rear;
            rear = front;   
        }
        else {
            rear.next = new ListItem();
            rear = rear.next;
            rear.data = s;
            rear.next = front;
        }
        numItems ++;
    }


    public int size ()
    {
        return numItems;
    }


    public String toString ()
    {
        if (front == null) {
            return "empty";
        }

        // Put all the elements (data only) into the string.
        String s = "[";
        ListItem listPtr = front;
        while (listPtr != null) {
            s += " \"" + listPtr.data + "\"";
            listPtr = listPtr.next;
        }
        return s + "]";
    }


    public String fire (String assassin)
    {
        //take in name
        if (front.data == null){
            String error = "Error: no such assassin";
            return error;
        }
        //find assassin
        ListItem temp = front;
        while (temp !=null && !(temp.data.equals(assassin))){
            temp = temp.next;
        }

        //determine victim
        assassin = temp.next.data.toString();
        //eliminate next assassin
        temp.next = temp.next.next;
        return assassin;
    }





    public boolean contains (String s)
    {
        if (front == null) {
            return false;
        }

        // Start from the front and walk down the list. If it's there,
        // we'll be able to return true from inside the loop.
        ListItem listPtr = front;
        while (listPtr != null) {
            if ( listPtr.data.equals(s) ) {
                return true;
            }
            listPtr = listPtr.next;
        }
        return false;
    }
}


public class AssassinGame {
    public static void main (String[] argv)
    {

        CircularList assassins = new CircularList ();
        assassins.add ("Jackal");
        assassins.add ("Mata Hari");
        assassins.add ("John Wilkes Booth");
        assassins.add ("Lee Harvey Oswald");
        assassins.add ("Gavrilo Princip");
        assassins.add ("James Earl Ray");
        assassins.add ("Jack Ruby");
        System.out.println (assassins);
        //      System.out.println("b");

        String victim = assassins.fire ("Gavrilo Princip");
        System.out.println ("\nGavrilo's victim: " + victim + "\n  Remaining: " + assassins);
        // Gavrilo's victim: James Earl Ray

        victim = assassins.fire ("Jack Ruby");
        System.out.println ("\nJack's victim: " + victim + "\n  Remaining: " + assassins);
        // Jack's victim: Jackal

        victim = assassins.fire ("Mata Hari");
        System.out.println ("\nMata's victim: " + victim + "\n  Remaining: " + assassins);
        // Mata's victim: John Wilkes Booth

        victim = assassins.fire ("Jackal");
        System.out.println ("\nJackal's victim: " + victim + "\n  Remaining: " + assassins);
        // Victim: Error: no such assassin.

        victim = assassins.fire ("Jack Ruby");
        System.out.println ("\nJack's victim: " + victim + "\n  Remaining: " + assassins);
        //        // Jack's second victim: Mata Hari
    }


}

[jhamill]

updated fire method that works now, just need to be able to correctly set up circularly linkedlist.....

public String fire (String assassin)
    {
        //take in name
        if (front.data == null){
            String error = "Error: no such assassin";
            return error;
        }
        //find assassin
        ListItem temp = front;
        while (temp !=null && !(temp.data.equals(assassin))){
            temp = temp.next;
        }

        //determine victim
        while (temp.next==(null)){
            temp = front;
        }
        assassin = temp.next.data.toString();
        //eliminate next assassin
        temp.next = temp.next.next;
        return assassin;
    }

[rubberman]

You basically want your circular list class to extent the linked list class, not encapsulate it as you have. Then, your circular list class will ensure that the last node is pointing to the first node in the linked list. It eliminates a lot of cruft and lets you focus on the differences between the two types. That way, when you find the marker (assassin), you can easily remember that node, go to the next to find the following, and then set the following to the Next member of the assassin node. Voila! One dead victim! And you don't have to do anything to keep the list healthy except that if you "kill" the head of the linked list, you need to reset it to the next member that you just linked to the assassin... Clear as mud yet? :-)

[JamesCherrill]

Beware!

while (listPtr != null) {
    ...
    listPtr = listPtr.next;
}

When you get your list properly circular then this loop will never terminate, it just keeps going round and round the list forever. YOU need to terminate the loop when you get back to the start.

[jhamill]

I think now Im stuck in the infinite while loop like you said.... I tried if(rear==front) break; to get out of it but it didnt work...however when I simply type break it does work but messes up the rest of my output so it is clearly an issue...

[jhamill]

I am very nearly finished...i have the circular list working....but I cannot seem to decipher how this line of code eliminates any assassins, and or what it does exactly?!
temp.next = temp.next.next;

[JamesCherrill]

temp is the current node in the list
temp.next is a pointer to the next node
(temp.next).next is the next node's pointer to it's next node
eg If temp is node 1 then temp.next is node 2 and temp.next.next is node 3
In that example temp.next = temp.next.next; changes node 1's next node pointer to point to node 3, thus dropping node 2 from the list.

[jhamill]

now the problem is that it can temp.next.next does not loop back to the beginning of the list, and so theres no way to eliminate the first person off the list. I assume the problem is in my fire method.

public String fire (String assassin)
    {
        //take in name
        if (front.data == null){
            String error = "Error: no such assassin";
            return error;
        }
        //find assassin
        ListItem listPtr = front;
        while (listPtr !=null && !(listPtr.data.equals(assassin))){
            listPtr = listPtr.next;
        }

        //determine victim
        while (listPtr.next==(null)){
            listPtr = front;        
        }
        assassin = listPtr.next.data.toString();
        //eliminate next assassin
        if (listPtr.next==(null)){
        rear.next=front.next.next;
        }
        listPtr.next = listPtr.next.next;
        return assassin;
    }

and here is the class that makes the list

public class AssassinGame {
    public static void main (String[] argv)
    {

        CircularList assassins = new CircularList ();
        assassins.add ("Jackal");
        assassins.add ("Mata Hari");
        assassins.add ("John Wilkes Booth");
        assassins.add ("Lee Harvey Oswald");
        assassins.add ("Gavrilo Princip");
        assassins.add ("James Earl Ray");
        assassins.add ("Jack Ruby");
        System.out.println (assassins);
        //      System.out.println("b");

        String victim = assassins.fire ("Gavrilo Princip");
        System.out.println ("\nGavrilo's victim: " + victim + "\n  Remaining: " + assassins);
        // Gavrilo's victim: James Earl Ray

        victim = assassins.fire ("Jack Ruby");
        System.out.println ("\nJack's victim: " + victim + "\n  Remaining: " + assassins);
        // Jack's victim: Jackal

        victim = assassins.fire ("Mata Hari");
        System.out.println ("\nMata's victim: " + victim + "\n  Remaining: " + assassins);
        // Mata's victim: John Wilkes Booth

        victim = assassins.fire ("Jackal");
        System.out.println ("\nJackal's victim: " + victim + "\n  Remaining: " + assassins);
        // Victim: Error: no such assassin.

        victim = assassins.fire ("Jack Ruby");
        System.out.println ("\nJack's victim: " + victim + "\n  Remaining: " + assassins);
        //        // Jack's second victim: Mata Hari
    }


}