Java Method equals circular list

Question

Here is the code for my Element class:

public class Element<T> {
    Element<T> next;
    Element<T> previous;
    T info;
}

... and for CircularList:

public class CircularList<T> {
    Element<T> first=null;

    public void add(Element<T> e){
        if (first==null){
            first=e;
            e.next=e;
            e.previous=e;
        } 
        else { //add to the end;
            first.previous.next=e;
            e.previous = first.previous;
            first.previous=e;
            e.next=first;
        }
    }

    public boolean equals(Object o){
        // TODO
    }
}

I don't know how to make an equals method for a circular list...

Only check if o instanceof CircularList<T> ?? (if ! return false else true?) mmm.. dunno how to do it :(

I know (from school) that I have to check 3 conditions:

if this == o return true
if o == null return false
if !o instanceof CircularList<T> return false

...

I don't know now if I have to check element from list1 to o , with a while... help me :)

Is an university test and I cannot modify or add method to element class.. I only have to implement the equals method from the CircularList<T> class!

Answer 1

The solution is obtained by tweaking your CircularList class a little: let's add it a length field.

public class CircularList<T> {
    int length = 0;  // <- this field contains the number of elements that the list has.
    Element<T> first = null;

    public void add(Element<T> e){
        if (first == null){
            first = e;
            e.next = e;
            e.previous = e;
        } 
        else {
            first.previous.next = e;
            e.previous = first.previous;
            first.previous = e;
            e.next = first;
        }

        this.length++;  // <- increment each time you call add().
    }
}

Now, implementing equals becomes trivial:

@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;

    @SuppressWarnings("unchecked")
    final CircularList<T> other = (CircularList<T>) obj;

    if(other.length != this.length) {
        return false;
    }

    Element<T> current = this.first;
    Element<T> otherCurrent = other.first;
    int offset = 0;
    boolean found = false;
    do {
        found = checkSequence(current, otherCurrent);
        if(!found) {
            offset++;
            otherCurrent = otherCurrent.next;
        }
    } while(!found && offset < length) ;

    return found;
}

private boolean checkSequence(Element<T> current, Element<T> otherCurrent) {
    int i = 0;
    while(i < length && current.info == otherCurrent.info) {
        current = current.next;
        otherCurrent = otherCurrent.next;
        i++;
    }

    return i == length;
}

What I'm doing here in the checkSequence method is simply iterating over each elements (there are length of them in both lists) and checking that they're all the same by pair.

Then, if I left my loop because i reached length, it means that I've been through all the elements and that they were all identical. If i, at this point, is smaller than length, it means that the ith elements of the lists weren't the same.

Thus, I simply return i == length.

---

On top of this, I want to handle the cases where we're considering lists like:

• A, B, C
• C, A, B

... which must be equal.

Thus, I'm simply calling checkSequence, at most length times, comparing the second list to the first one with all possibles offsets.