Printing Circular List

Question

I'm doing my assignment which is to create a Circular List, I believe that my methods are working properly, except for my print method.

    public String print() {
        String str = "";
        Node curr = first;

        for(int i = 0; i < getSize(); curr = curr.getNext(), i++) {
            str += curr.getData();
        }
        return str;
    }

I test it with the numbers: {1,2,3,4,5}, and when I call my print method I get 15432 as a result. Does any one know what could be wrong with this, apparently I'm not seeing it. Also if you need more code, let me know.

EDIT: After some comments I realize it's not my print method, here are my add() and getData() methods:

    public void add(int value) {
        if(first == null) {
            first = new Node(value, null);
            first.setNext(first);
        } else {
            Node newNode = new Node(value, first.getNext());
            first.setNext(newNode);
        }
        System.out.println("Added: " + value);
        size++;
    }

    public int getData() {
        return first.getData();
    }

EDIT 2: The constructor;

class CircularList {
    private Node first;
    private int size;

    public CircularList() {
        first = null;
        size = 0;
    }
    ....

Nothing apparently wrong here. Maybe your `add` method is adding items in the wrong order. Is this a doubly linked list? — Joni, May 31 '13 at 15:25
can we have the getNext() implementation and the constructor/add element methods? — Andrew W, May 31 '13 at 15:25
`curr.getNext()` - Are you sure this is doing what it is supposed to do? From what you describe, `curr.getNext()` appears to function as a `curr.getPrev()` — Alex Gittemeier, May 31 '13 at 15:25
It looks like you have your next a previous pointers backwards. If so, the bug would either be in the `add()` method or in `getNext()` — Mel Nicholson, May 31 '13 at 15:25
I'm rather sure your problem isn't in the above code snippet — Michael Butscher, May 31 '13 at 15:26
I just updated the post to include the add() and getData() methods, I will change my print method to use String Builder, thanks for that suggestion. — Matthew Brzezinski, May 31 '13 at 15:28
I suggest you write a simple unit test which adds one element at a time and check it adds them in the order you expect. When you discover the simplest case which doesn't do what you expect, I suggest stepping through your code in your debugger so you understand what it is doing. — Peter Lawrey, May 31 '13 at 15:33

Sergey Kalinichenko · Accepted Answer · 2013-05-31T15:44:41.907

The problem is with the add method: it appears that the method adds the item as the number two in the list, rather than adding it to its end. This does not apply to the initial entry, because the head and the tail are the same for it.

To fix this problem, keep the Node last element in the CircularList, and do the insertion at the last, not at the first element. This makes deletion of the last element a little harder to manage, but the speedup that you gain is worth it.

If you would like to surprise your teacher, you can use a "magic trick":

public void add(int value) {
    if(first == null) {
        first = new Node(value, null);
        first.setNext(first);
    } else {
        // Remember the current first
        Node oldFirst = first;
        // Make a copy of the first node the "new first"
        first = new Node(first.getValue(), first.getNext());
        // Copy the new value into the "old first",
        // and make its next point to the "new first"
        oldFirst.setValue(value);
        oldFirst.setNext(first);
    }
    System.out.println("Added: " + value);
    size++;
}

Make sure that you fully understand this trick. Draw it on a piece of paper to understand it better. Your teacher may ask you about this, because it's not very common.

As far as the printing goes, do not use +=, use StringBuilder instead. You can also avoid the counter by observing that your printing should end when the curr reaches first again:

public String print() {
    StringBuilder str = new StringBuilder();
    Node curr = first;
    while (true) {
        str.append(curr.getData());
        curr = curr.getNext();
        if (curr == first) break;
    }
    return str.toString();
}

Thanks for this, drawing out a diagram definitely helped. Is there a reason as to use StringBuilder as opposed to +=? — Matthew Brzezinski, May 31 '13 at 16:25
@user1327636 The reason to avoid `+=` in a loop is that otherwise each iteration creates a new instance of `String` which gets thrown away. If you are printing `{1,2,3,4}`, then the strings `"1"`, `"1,2"`, and `"1,2,3"` will be created temporarily, and then thrown away (recall that Java strings are immutable, so `+=` makes a new object). [Here](http://stackoverflow.com/a/7817989/335858) is a link to an answer discussing the problem at some length. — Sergey Kalinichenko, May 31 '13 at 16:29
In your add method should we add first = oldfirst at the end in the else condition .... because its a class variable..... — sethi, Jun 02 '13 at 15:09
@bapusethi No, absolutely not. You seem to have misunderstood the approach. I do not blame you, it's not trivial. Please try this out with paper and pencil to see how this works. P.S. Your edit was incorrect, I rejected it. — Sergey Kalinichenko, Jun 02 '13 at 15:21

Printing Circular List

1 Answers1