8 Replies - 6436 Views - Last Post: 06 April 2014 - 08:35 PM Rate Topic: -----

#1 cbass0  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 06-April 14

Josephus circular linked list java problem

Posted 06 April 2014 - 12:50 PM

I am creating a josephus java program with a circular linked list. Can someone go over my code and tell me whats wrong

This is what the methods are suppose to do

a. size(): Returns the number of items in the list.

b. isEmpty(): Returns true if the list is empty and false otherwise

c. advance(): Moves the cursor from the current position to the next item. If the cursor is at the end (tail) of this list, calling advance() should make the cursor refer to the first element in the list. If the list is empty, this operation should have no effect.

d. getCurrent(): Return the String value in the node referenced by the cursor unless the CircularLL is empty in which case write an error message to System.err.

e. add(String data): Adds a new item to the list by creating a newNode and linking it to the end of the circular linked list. The last node should point to the new node and then you should make lastNodeInserted point to new node as well.) Please note that a circular linked list is always circular. The last node should point to the beginning node. When there is only one node in a CircularLL, its next should point to itself. This method updates currNode when the first node is added, and always updates lastNodeInserted and numNodes. Take care when adding the first node – this is a special case and should be handled differently.

f. remove(): If the list is empty, write an error message to System.err indicating that an attempt was made to remove from an empty queue and return null. Assuming the list isn’t empty, this method removes the node currently referenced by the cursor, reassigns the cursor to point to the next node in the list, and returns the String value stored in that node. To keep the list ‘linked’, you’ll need to locate the previous node to the one you’re removing and connect its next to the node which follows the one you’re removing. Create a local Node variable (prev) to find it. Consider and handle the special case when there is only one node and you’re removing it. And make sure to update lastNodeInserted whenever you remove the node that it is pointing to.

g. toString(): This should return a String representation of the circular linked list, with the first value displayed being the data of the first node added (not the data in the last node).



public class CircularLL {
    private class Node {
        String data;
        Node next;

        public Node(String data) {
            this.data = data;
            this.next = null;
        }

        public Node(String data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private int numNodes;
    private Node currNode;
    private Node lastNodeInserted;

    public int size() {
        return numNodes;
    }

    public boolean isEmpty() {
        return numNodes == 0;
    }

    public void advance() {
        if (isEmpty()) {
        } else {
            currNode = currNode.next;
        }
    }

    public String getCurrent() {
        String temp = null;
        if (isEmpty()) {
            System.err.println("Error getting current: The list is empty.");
        } else {
            temp = currNode.data;
        }
        return temp;
    }

    public void add(String data) {
        if (currNode == null) {
            currNode = new Node(null);
            currNode.data = data;
            lastNodeInserted = currNode;
            lastNodeInserted.next = null;
        } else {
            Node nextOne = new Node(null);
            nextOne.data = data;
            lastNodeInserted.next = nextOne;
            lastNodeInserted = nextOne;
        }
        numNodes++;
    }

    public String remove() {
        Node previous = currNode;
        Node current = currNode;

        if (isEmpty()) {
            System.err.println("Error removing: The list is empty, returning null.");
            return null;
        } else {
            previous = current;         
            current = current.next;
        }
        if (current == currNode) {
            currNode = currNode.next;
        } else {
            previous.next = current.next;
        }
        numNodes--;
        return current.data;
    }

    public String toString() {
        Node curr = currNode;
        String result = "front";
        while (curr != null) {
            result += " --> " + curr.data;
            curr = curr.next;
        }
        return result;
    }
}




Is This A Good Question/Topic? 0
  • +

Replies To: Josephus circular linked list java problem

#2 jon.kiparsky  Icon User is online

  • Chinga la migra
  • member icon


Reputation: 10681
  • View blog
  • Posts: 18,289
  • Joined: 19-March 11

Re: Josephus circular linked list java problem

Posted 06 April 2014 - 12:56 PM

What's the problem you're having? Are you getting compiler errors, or is the program failing at runtime, or are you getting wrong answers, or what? What is the behavior that makes you think something is wrong?
Was This Post Helpful? 0
  • +
  • -

#3 cbass0  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 06-April 14

Re: Josephus circular linked list java problem

Posted 06 April 2014 - 01:02 PM

I don't think the add and remove methods are working correctly as they are stated in the instructions.

Here is additional information of how I am supposed to create this circular linked list class:

1. Define a circular linked list class you can use to represent the circle of rebels. It doesn’t need to be a generic class. Call your class CircularLL. This class should include an inner private class named Node. Create Node as a class with two private data members: data of type String and next of type Node. (Because this class is declared as private inside the body of the CircularLL class, your CircularLL methods will be able to access the data members data and next directly and it is absolutely fine to do so.) Besides the Node inner private class, the CircularLL class contains a count of the number of nodes in the linked list (numNodes) and references to the last node inserted (lastNodeInserted) and to the current node (currNode). Think of currNode as a cursor, keeping track of the current position. lastNodeInserted is updated in the add method. With each addition, lastNodeInserted should be updated to the node just created so that after the last node has been added, lastNodeInserted will point at that. When the first node in the CircularLL object is created, the current node should be initialized to reference it. currNode should be advanced to the next node whenever the advance() method is called. (lastNodeInserted refers to the metaphorical last node in the circular linked list. So to access the first node in the linked list, we’d use lastNodeInserted.next.)
Was This Post Helpful? 0
  • +
  • -

#4 jon.kiparsky  Icon User is online

  • Chinga la migra
  • member icon


Reputation: 10681
  • View blog
  • Posts: 18,289
  • Joined: 19-March 11

Re: Josephus circular linked list java problem

Posted 06 April 2014 - 01:07 PM

Again, what is the behavior that you're seeing that you think is incorrect? I'm happy to help, as are many members, but please help me out here. It's a lot easier for me if I know what to look for.
Was This Post Helpful? 0
  • +
  • -

#5 infernorthor  Icon User is offline

  • D.I.C Lover

Reputation: 362
  • View blog
  • Posts: 1,718
  • Joined: 07-February 14

Re: Josephus circular linked list java problem

Posted 06 April 2014 - 01:08 PM

With a circular LL you should have no null references.
Was This Post Helpful? 1
  • +
  • -

#6 cbass0  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 06-April 14

Re: Josephus circular linked list java problem

Posted 06 April 2014 - 01:11 PM

I don't know if the add and remove method are linking the list.
Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12147
  • View blog
  • Posts: 45,156
  • Joined: 27-December 08

Re: Josephus circular linked list java problem

Posted 06 April 2014 - 01:22 PM

Why don't you know that? Have you tested the List? Testing code is always the developer's (read- your) responsibility.
Was This Post Helpful? 1
  • +
  • -

#8 VintageT  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 06-April 14

Re: Josephus circular linked list java problem

Posted 06 April 2014 - 08:27 PM

cpsc 165 @ Dom? Did you write your main method already.
Was This Post Helpful? 0
  • +
  • -

#9 jon.kiparsky  Icon User is online

  • Chinga la migra
  • member icon


Reputation: 10681
  • View blog
  • Posts: 18,289
  • Joined: 19-March 11

Re: Josephus circular linked list java problem

Posted 06 April 2014 - 08:35 PM

Here's an important thing to notice in the assignment. Ponder this for a little while and see if enlightenment proceeds therefrom.

Quote

e. add(String data): Adds a new item to the list by creating a newNode and linking it to the end of the circular linked list. The last node should point to the new node and then you should make lastNodeInserted point to new node as well.)

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1