Results 1 to 7 of 7
  1. #1
    stevenson15 is offline Member
    Join Date
    Apr 2009
    Posts
    3
    Rep Power
    0

    Exclamation Doubly Linked Lists

    Hi I am meant to create methods for a doubly linked list to add, add at the end and remove nodes from the list this is my list so far and i have added comments explaining the pseudo code behind it. The idea behind the program is its a hot potato game so when the music stops, or in our case once the hot potato has been passed n times, then the person holding the hot potato is out. The game continues until there is only 1 person left (the winner).

    _____________________ Person Class(This Is Complete)________________

    public class Person {
    String name;
    Person next;
    Person previous;

    // a double linked list

    Person (Person previous, String name, Person next) {
    this.name = name;
    this.previous = previous;
    this.next = next;
    }




    @Override
    public String toString () {
    String result = name;
    for (Person head = next; head!=null; head=head.next) {
    result += "," + head.name;
    }
    return result;
    }

    }

    _________Main Class(Completed but need to get names from txt file)_______
    public class Main {

    /**
    * @param args the command line arguments
    */
    public static void main(String[] args) {
    // read in the names of the players in the game
    // you should read them in from a text fil called names.txt

    String[] names = {"Gordon", "Carol","Lindsay","Ewan","Jamie","Lynda"};
    //String[] names = {"Gordon","Carol","Ewan"};
    //String[] names = {"Gordon"};
    //String[] names = {};

    // create a new HotPotato game
    HotPotato list = new HotPotato();

    // set n to an appropriate value
    int n = 5;

    // add the names to the HotPotato game
    for(int i = 0; i<names.length; i++){
    list.addEnd(names[i]);
    }

    if (list.size==0) {
    System.out.println ("Empty list.");
    } else if (list.size==1) {
    System.out.println ("Only: " + list.remove());
    } else {
    System.out.println (list);
    System.out.println ("First: " + list.remove());


    Person q = list.list;
    while (list.size > 1) {
    System.out.println (list);
    q = list.cycle (q, n-1);
    System.out.println ("Next: " + list.remove(q));

    }
    System.out.println ("Winner: " + list.remove());
    }
    }

    }

    ____________HotPotato Class(Need to compete methods _______________
    _____________added comments for tips but unsure of coding it)___________

    public class HotPotato {
    Person list;
    int size=0;

    public HotPotato() {

    }

    public void add (String name) {
    // TO DO


    // check if the list is empty
    // if empty add name to the list, with appropriate links
    // else add name to the list, with appropriate links
    // finally increment the size

    }

    public void addEnd (String name) {
    Person ins = new Person(null, name, null);
    Person current;
    if(list == null){
    list = ins;
    }
    else {
    current = list;
    while (current.next != null)
    {
    current = current.next;
    }
    current.next = ins;
    size++;
    }
    }
    // TO DO


    // check if the list is empty
    // if empty add name to the list, with appropriate links
    // else lop thoutght he list untl you come to the end of the lits
    // then add name to the list, with approriate links


    // finally increment the size


    public String remove () {
    // TO DO

    // set up a temporary String variable and set it to list.name

    // get the next entry in the list
    // check that it isnt null and that the netxc elent isn't null
    // and remove it by seting the links to appropriate values

    // decrement the size

    // return the temporary String variable


    }


    public String remove (Person p) {
    // TO DO
    if (p==null) {
    throw new IllegalArgumentException ();
    }
    if (p==list) {
    return remove();
    }
    // set up a temporary String variable and set it to p.name

    // check if previous is not null and
    // if so then change the links appropriately



    // check if next is not null and
    // if so then change the links appropriately

    // decrement the size

    // return the temporary String variable
    }

    public Person cycle (Person p, int i) {
    Person r = p;
    while (i>0) {
    if (r.next == null) {
    r = list;
    } else {
    r = r.next;
    }
    i--;
    }
    return r;
    }

    @Override
    public String toString () {
    return list.toString();
    }

    }
    Last edited by stevenson15; 04-20-2009 at 06:00 PM.

  2. #2
    mtyoung is offline Senior Member
    Join Date
    Dec 2008
    Location
    Hong Kong
    Posts
    473
    Rep Power
    6

    Default

    read file and get the string...
    you can read Scanner (Java Platform SE 6)

    Person Class has a variable named previous... so remember to update next and previous at the same time...

    i dont know what Person.add method want to do..., add to header? or the random position?
    Last edited by mtyoung; 04-21-2009 at 09:32 AM.

  3. #3
    mtyoung is offline Senior Member
    Join Date
    Dec 2008
    Location
    Hong Kong
    Posts
    473
    Rep Power
    6

    Default

    after reading the whole program...
    is that add and remove method add/remove at the head?
    or using a pointer variable, which may used for add/remove person to/from the list, in HotPotato class
    Last edited by mtyoung; 04-21-2009 at 09:55 AM.

  4. #4
    stevenson15 is offline Member
    Join Date
    Apr 2009
    Posts
    3
    Rep Power
    0

    Default

    add method - You have to test whether list (the private attribute in the HotPotato class) is empty.
    If it is empty then make list equal to a new Person (with the appropriate links)
    If it is not empty then make list equal to a new Person (with the appropriate links).

    addEnd method - is meant to add a new Person (with name of name) to the end of the list.
    So, as in the add(String name) method, you have to check whter you are alread at the end of the list.
    If so then make list equal to a new Person (with the appropriate links).
    If not, then you have to move through the list till you get to the end. The way to move through the list is, create a new Person (say p) equal to list. Then use p.next to check whter you have come ot the end of the list.
    Once you have come to the end of the list then make p.next equal to a new Person (with the appropriate links).

    The String remove() method will return the name of the Person being removed from the list by changing the appropriate links. Again, the important point is that the Person isn't removed but the links are reset so that the person is missed out in the chain.

    The method String remove(Person p) will remove a Person from the list, by changing the appropriate links. the Person p, is found by using the Person cycle(Person p, int i) method.

  5. #5
    mtyoung is offline Senior Member
    Join Date
    Dec 2008
    Location
    Hong Kong
    Posts
    473
    Rep Power
    6

    Default

    first ... do you have method to compare person?
    do person1 = person2 iff their name is same?

    second
    what position person will add to the list?
    If it is not empty then make list equal to a new Person (with the appropriate links).

    third
    every methods(include addEnd) modify the list, you need to update both Person.next and Person.previous

    4
    Again, the important point is that the Person isn't removed but the links are reset so that the person is missed out in the chain.
    i think it should be removed from the list the return the removed Person

    5
    cycle(Person p, int i), p should be the remove Person, then i is the size of list?

  6. #6
    stevenson15 is offline Member
    Join Date
    Apr 2009
    Posts
    3
    Rep Power
    0

    Default

    Just forget the add person it doesnt matter got that sorted. Just concetrate on the remove methods what happens is the person at the end is removed by checking that next = null then the links need to be altred but the person is returned so a temp string variable has to be declared. For the last remove method i dont understand i think the cycle method has to be called but the comments might help that is included i just dont understand them.

  7. #7
    mtyoung is offline Senior Member
    Join Date
    Dec 2008
    Location
    Hong Kong
    Posts
    473
    Rep Power
    6

    Default

    what happens is the person at the end is removed
    declare a String, set its value to Person.name of last person in the list
    second last person next set to null
    the last persion then set to null for garabage collector(GC) to collect

    instruction or your understanding?
    the Person p, is found by using the Person cycle(Person p, int i) method.

Similar Threads

  1. doubly linked list insert
    By ineedhelpwithjava in forum Advanced Java
    Replies: 1
    Last Post: 03-20-2009, 03:05 PM
  2. Help with Doubly linked list
    By Dr Gonzo in forum New To Java
    Replies: 5
    Last Post: 12-06-2008, 08:45 AM
  3. comparision between two lists
    By suprabha in forum Advanced Java
    Replies: 14
    Last Post: 08-01-2008, 03:49 PM
  4. Doubly-linked list with data structure
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-16-2008, 11:30 PM
  5. question about linked lists
    By jkurth in forum Advanced Java
    Replies: 1
    Last Post: 11-11-2007, 09:33 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •