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;
    }
    ....

Answer 1

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();
}