Removing an element in a circular linked list

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

33 Replies - 8649 Views - Last Post: 30 April 2011 - 08:32 PM Rate Topic: -----

#1 confusedincollegeCS  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 18
  • Joined: 30-April 11

Removing an element in a circular linked list

Posted 30 April 2011 - 12:10 PM

Hello! I am incredibly confused at the moment. I am working on a recommended assignment for school that our teacher said would be on our exam and I have no idea what I'm doing, so I could really use some help.

Basically I need to read a circular linked list that has "assassin" names in it. I need to find the specified assassin in the list and then "kill the next person" (aka remove the element next to wherever I find the position). I think I've figured out the smaller methods and how to find the assassins place (I'm not positive since I can't test it without the last part). The problem is I have no idea how to remove the next element. Please help me, I'll really appreciate it and I really want to understand this program for my test!! I've tried using the pointers but it's really confusing me.

Here's my code so far, the part I'm having trouble with is in the fire method:

import java.util.LinkedList;


class ListItem {

    String data;
    ListItem next;

}


class CircularList {

    // The usual list variables.
    ListItem front = null;
    ListItem rear = null;

    // To keep track of the size.
    int numItems = 0;


    public void add (String s)
    {
    	if (front == null) {
    	    front = new ListItem ();
    	    front.data = s;
    	    rear = front;
    	    rear.next = null;
    	}
    	else {
                ListItem nextOne = new ListItem ();
    	    nextOne.data = s;
    	    rear.next = nextOne;
    	    rear = nextOne;
    	}    

    	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, CircularList assassins)
    {
		
    	//take in name
    	if (front.data == null){
    		String error = "Error: no such assassin";
    		return error;
    	}
    	
    	char [] newassassin = new char [assassin.length()];
    	//find assassin
    	for(int i=0; i<numItems; i++){
    		if(assassins.contains(assassin)){
    			int pos = i;
    		}
    		//eliminate next assassin
    		newassassin[i] = assassins.front.data.charAt(i+1); 
    	}
    	assassin = newassassin.toString();
    	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 AssasinGame {

    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);
        
        for (int i=0; i< assassins.size(); i++){
        String victim = assassins.fire ("Gavrilo Princip",assassins);
        System.out.println ("\nGavrilo's victim: " + victim + "\n  Remaining: " + assassins);
        // Gavrilo's victim: James Earl Ray

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

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

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

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

}



Is This A Good Question/Topic? 0
  • +

Replies To: Removing an element in a circular linked list

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10486
  • View blog
  • Posts: 38,858
  • Joined: 27-December 08

Re: Removing an element in a circular linked list

Posted 30 April 2011 - 12:29 PM

Why does your fire() method need a CircularList object as a param? It is an instance method, meaning it has access to your CircularObject fields.

I think this line is where the misconception lies. You are using a LinkedList. You have no need to deal with arrays at all. Rather, start at the front Node, assigning it to a temp Node. Loop while temp != null and current.data is not equal to the assassin, moving current = current.next on each iteration. Then outside of your loop, removing the next element is pretty simple. Simply set current.next = current.next.next.
char [] newassassin = new char [assassin.length()];



You might also want to check out my LinkedList tutorial.

Hope this helps some. :)
Was This Post Helpful? 0
  • +
  • -

#3 confusedincollegeCS  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 18
  • Joined: 30-April 11

Re: Removing an element in a circular linked list

Posted 30 April 2011 - 12:47 PM

That does make more sense. I figured I wasn't supposed to use an array but I was at the point where I was just trying random things to get a loop through. What is current though?
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10486
  • View blog
  • Posts: 38,858
  • Joined: 27-December 08

Re: Removing an element in a circular linked list

Posted 30 April 2011 - 12:52 PM

I'm just calling the temp Node current, since it represents the current Node we are examining.
Was This Post Helpful? 0
  • +
  • -

#5 confusedincollegeCS  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 18
  • Joined: 30-April 11

Re: Removing an element in a circular linked list

Posted 30 April 2011 - 01:05 PM

Oh okay. I'm still confused though because I'm not sure how to assign that as a node. This is what I have now for the fire method:

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



The problem is my end output is only printing the original list...so I have no idea what to do... :/
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10486
  • View blog
  • Posts: 38,858
  • Joined: 27-December 08

Re: Removing an element in a circular linked list

Posted 30 April 2011 - 01:12 PM

You are comparing a Node and a String in your if statement. Better to compare temp.data to assassin. Also, use the String equals() method to compare Strings, not the == and != operators, as they compare memory locations, not values.

Don't shift the data. Shift the Nodes. Simply, front.next should be assigned front.next.next. That's it.
front.next.data = front.next.next.data; 


Was This Post Helpful? 0
  • +
  • -

#7 confusedincollegeCS  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 18
  • Joined: 30-April 11

Re: Removing an element in a circular linked list

Posted 30 April 2011 - 01:14 PM

Right, I understand I need to compare temp.data but I'm not sure how to signify temp as a node. When I first set it as a node I couldn't store the front.data in the temp and then when I put it as a string obviously I don't have temp.data as an option.
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10486
  • View blog
  • Posts: 38,858
  • Joined: 27-December 08

Re: Removing an element in a circular linked list

Posted 30 April 2011 - 01:17 PM

Declare temp as a Node and assign it front:
Node temp = front;


Was This Post Helpful? 0
  • +
  • -

#9 confusedincollegeCS  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 18
  • Joined: 30-April 11

Re: Removing an element in a circular linked list

Posted 30 April 2011 - 01:19 PM

Yes I tried that, but I got an error message since front isn't compatible with the Node...
Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10486
  • View blog
  • Posts: 38,858
  • Joined: 27-December 08

Re: Removing an element in a circular linked list

Posted 30 April 2011 - 01:21 PM

Ah, your Node class is called ListItem. LinkedLists, Trees, Graphs, etc., are Node-based structures. So you will commonly see their components referred to as Nodes. Just know that Node refers to an individual unit class that contains data and points to one or more other Nodes. :)
Was This Post Helpful? 0
  • +
  • -

#11 confusedincollegeCS  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 18
  • Joined: 30-April 11

Re: Removing an element in a circular linked list

Posted 30 April 2011 - 01:25 PM

Sorry, I still don't understand how to store it in the node then. Do I have to add a cast?
Was This Post Helpful? 0
  • +
  • -

#12 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10486
  • View blog
  • Posts: 38,858
  • Joined: 27-December 08

Re: Removing an element in a circular linked list

Posted 30 April 2011 - 01:27 PM

View Postmacosxnerd101, on 30 April 2011 - 04:21 PM, said:

Ah, your Node class is called ListItem. LinkedLists, Trees, Graphs, etc., are Node-based structures. So you will commonly see their components referred to as Nodes. Just know that Node refers to an individual unit class that contains data and points to one or more other Nodes. :)

Use a ListItem variable.

I don't mean to be rude, but it sounds like you are in a data structures class, but are a little weak on the fundamentals like data types. I would strongly suggest checking out the Java Tutorials Section on DIC for a refresher on the basics.
Was This Post Helpful? 0
  • +
  • -

#13 confusedincollegeCS  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 18
  • Joined: 30-April 11

Re: Removing an element in a circular linked list

Posted 30 April 2011 - 01:34 PM

Oh okay, wow duh on my part. And no it's not rude, you are right, I am pretty weak on this which is why I'm trying to understand it.

Problem is, umm I still don't! (Surprised?) I have the following for my fire code so from what I understand it should be returning the name of who is next. The problem is while it is removing that person it keeps displaying victim as the original person named as the assassin (the input String). Am I missing something?!

Here's the fire code again and the output below:
 
 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 !=assassin){
    		temp = temp.next;
    	}
    	//eliminate next assassin
    	temp.next = temp.next.next;
    	assassin = temp.data;
    	return assassin;
    }



Output (just for the first part of the main method):
[ "Jackal" "Mata Hari" "John Wilkes Booth" "Lee Harvey Oswald" "Gavrilo Princip" "James Earl Ray" "Jack Ruby"]

Gavrilo's victim: Gavrilo Princip
Remaining: [ "Jackal" "Mata Hari" "John Wilkes Booth" "Lee Harvey Oswald" "Gavrilo Princip" "Jack Ruby"]

Gavrilo's victim: Gavrilo Princip
Remaining: [ "Jackal" "Mata Hari" "John Wilkes Booth" "Lee Harvey Oswald" "Gavrilo Princip"]
Was This Post Helpful? 0
  • +
  • -

#14 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10486
  • View blog
  • Posts: 38,858
  • Joined: 27-December 08

Re: Removing an element in a circular linked list

Posted 30 April 2011 - 02:12 PM

I already pointed this out. You should be using the equals() method, not the != operator. So, !(temp.data.equals(assassin)).
temp.data !=assassin


Was This Post Helpful? 0
  • +
  • -

#15 confusedincollegeCS  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 18
  • Joined: 30-April 11

Re: Removing an element in a circular linked list

Posted 30 April 2011 - 02:22 PM

Oh, my bad you did I'm sorry, totally missed that. Now the first fire part works, and I get the first output to print correctly. Yay, making progress!

Yet I'm still having trouble getting the output I'm supposed to be getting for the rest of it. I think I have an error somewhere since my compiler is pegging both the line:
assassin = temp.next.data.toString(); 

and the line (in main):
victim = assassins.fire ("Jack Ruby"); 


I'm not sure how to fix this, especially since I'm not sure what the exception is here unless it's that Jack Ruby no longer exists? Or is it that it doesn't go to the front of the list it just has nothing to go to? Sorry I'm having so much trouble with this but I'm just really trying to understand it.
Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3