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!

This link may help you stackoverflow.com/questions/16382887/… — Wundwin Born
– Wundwin Born, Commented Aug 6, 2014 at 9:07
hmm circular list is tricky . because start and end are kind of unknown, I like to see an answer for this too. — nafas
– nafas, Commented Aug 6, 2014 at 9:09

Marco13 · Accepted Answer · 2014-08-06 10:37:17Z

I think the key point is that the lists are circular. Thus, I assume that the lists

A, B, C, D, E 
   B, C, D, E, A

should be considered as equal. Because they are. When you rotate a circle, it's still a circle.

So I guess the trick is to check each element of the other list, and see whether the the list is equal when starting at this element. In the example above, one would test

Is the list B, C, D, E, A equal to A, B, C, D, E? No
Is the list C, D, E, A, B equal to A, B, C, D, E? No
Is the list D, E, A, B, C equal to A, B, C, D, E? No
Is the list E, A, B, C, D equal to A, B, C, D, E? No
Is the list A, B, C, D, E equal to A, B, C, D, E? Yes. Finally.

A quick implementation with some test cases, I hope that the most important cases are covered:

public class CircularListEquality {
    public static void main(String[] args) {

        CircularList<String> c0 = createList("A", "B", "C", "D", "E");
        CircularList<String> c1 = createList("A", "B", "C", "D");
        CircularList<String> c2 = createList(     "B", "C", "D", "E");
        CircularList<String> c3 = createList(     "B", "C", "D", "E", "A");

        CircularList<String> c4 = createList("A", "B", "C", "A", "B", "C");
        CircularList<String> c5 = createList("A", "B", "C");

        CircularList<String> c6 = createList("A");
        CircularList<String> c7 = createList("A", "A", "B", "C");

        test(c0, c1, false);
        test(c0, c2, false);
        test(c1, c2, false);
        test(c0, c3, true);
        test(c3, c0, true);
        test(c4, c5, false);
        test(c5, c4, false);
        test(c6, c7, false);
    }

    private static <T> void test(
        CircularList<T> c0, CircularList<T> c1, boolean expected) {
        boolean actual = c0.equals(c1);
        if (actual == expected) {
            System.out.print("PASSED");
        } else {
            System.out.print("FAILED");
        }
        System.out.println(" for " + toString(c0) + " and " + toString(c1));
    }

    private static <T> String toString(CircularList<T> c) {
        StringBuilder sb = new StringBuilder();
        Element<T> current = c.first;
        while (true) {
            sb.append(String.valueOf(current.info));
            current = current.next;
            if (current == c.first) {
                break;
            } else {
                sb.append(", ");
            }
        }
        return sb.toString();
    }

    private static CircularList<String> createList(String... elements) {
        CircularList<String> c = new CircularList<String>();
        for (String e : elements) {
            c.add(createElement(e));
        }
        return c;
    }

    private static <T> Element<T> createElement(T t) {
        Element<T> e = new Element<T>();
        e.info = t;
        return e;
    }
}

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

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 object) {
        if (this == object)
        {
            return true;
        }
        if (object == null)
        {
            return false;
        }
        if (!(object instanceof CircularList<?>))
        {
            return false;
        }
        CircularList<?> that = (CircularList<?>) object;

        Element<?> first0 = first;
        Element<?> current0 = first0;
        Element<?> first1 = that.first;
        Element<?> current1 = first1;
        while (true) {
            if (equalSequence(current0, current0, current1, current1)) {
                return true;
            }
            current1 = current1.next;
            if (current1 == first1) {
                return false;
            }
        }
    }

    private static boolean equalSequence(
        Element<?> first0, Element<?> current0,
        Element<?> first1, Element<?> current1) {
        while (true) {
            if (!equalElements(current0, current1)) {
                return false;
            }
            current0 = current0.next;
            current1 = current1.next;
            if (current0 == first0 && current1 == first1) {
                return true;
            }
            if (current0 == first0) {
                return false;
            }
            if (current1 == first1) {
                return false;
            }
        }
    }

    private static boolean equalElements(Element<?> t0, Element<?> t1) {
        if (t0 == null) {
            return t1 == null;
        }
        return equal(t0.info, t1.info);
    }

    private static <T> boolean equal(T t0, T t1) {
        if (t0 == null) {
            return t1 == null;
        }
        return t0.equals(t1);
    }
}

(EDIT: Added another test case)

Wow! That's quite thorough. But it's actually broken a little. Let's consider two lists: the first one has only one element, e1. Would the second one have e1, e1, e2 and e3, your algorithm would still return true :) However, you're probably right and e1, e2 is most likely supposed to "equal" e2, e1, you made a very good point.
@ccjmne I added another test case for this, and it works as expected. Note that the equalSequence method implicitly checks whether the sequences have the same length, by returning true only when the sequences arrive again at their first element at the same time.
Well, the elements are specific for the list. You can' use the same element in two lists, because then, the next and previous pointers are simply inconsistent. That's not related to my solution, but to the way how the list is implemented in the first place.
Oh my, you're right! I can't even think with mutable objects anymore... +1 :)

ccjmne · Accepted Answer · 2014-08-06 11:48:48Z

2

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.

edited Aug 6, 2014 at 11:48

answered Aug 6, 2014 at 10:08

ccjmne

9,6213 gold badges52 silver badges68 bronze badges

4 Comments

Maas Over a year ago

This is perfect if we can modify the class. Can you comment on my latest answer? I tried to use ref to check for loop break.

ccjmne Over a year ago

You're right, it implies being able to alter the CircularList class a little! However, it would also cover the cases where the list contains duplicate elements... ;)

Marco13 Over a year ago

In this case, the lists A,B,C and B,C,A would be considered as being different, but I think they should be equal (because they are just rotated).

ccjmne Over a year ago

You're probably right! That's a very good point. I now also handle that case.

Afzaal Ahmad Zeeshan · Accepted Answer · 2014-08-06 09:11:23Z

0

The ! operator just inverts the true to false and vice versa.

So, the code of yours about that one thing would mean an opposite of the actual

if !o instanceof CircularList<T>

would return false, if the o object is instance of CircularList<T>. Otherwise it would return to be true if the o is not an instance of CirculatList<T>. You're just trying to invert the actual result of the o instanceof CircularList<T>.

answered Aug 6, 2014 at 9:11

Afzaal Ahmad Zeeshan

15.9k14 gold badges61 silver badges106 bronze badges

Comments

Othman Benchekroun · Accepted Answer · 2014-08-06 10:08:28Z

0

The instruction :this == o; returns true only when they have the same adresse (when it's the same object), I think that what you need is something that would return true when both lists contains same elements, try this :

public boolean equals(CircularList<T> other){
    Element<T> e1 = first;
    Element<T> e2 = other.first;
    while(e1.next != first && e2.next != other.first){
       if(e1.info == e2.info){
           e1 = e1.next;
           e2 = e2.next;
       }
       else return false;
    } 
    if (e1.next == first && e2.next == other.first)
         return true;
    else return false;

}

i think that this would work !!

edited Aug 6, 2014 at 10:08

answered Aug 6, 2014 at 9:33

Othman Benchekroun

2,0582 gold badges20 silver badges38 bronze badges

10 Comments

Marco Baratella Over a year ago

Ty for all, very interisting..but I must (because it's an university test) to implement the equals method only to the CircularList class.. and i cannot edit or add any other method to element class!

Othman Benchekroun Over a year ago

Actually, this would probably give you a StackOverFlowException since the list is circular, I think you may need to add an attribute for the length of the list

Othman Benchekroun Over a year ago

ok i see, is it possible to add an attribute to your class for the length of the list ?

Marco Baratella Over a year ago

i can only add something inside the equals method... :)

Othman Benchekroun Over a year ago

This is not as simple as you wanted it, but i don't see how you can do it othewise

|

Maas · Accepted Answer · 2014-08-06 10:16:57Z

0

How about this equals implementation? We can avoid tweaking your Class.

    public boolean equals(CircularList<T> other)
        {
           **Standard checks will go here (ref equals, class type etc)**

            boolean result = false;
            result = first.equals(other.first);

            Element<T> next = first.next;
            Element<T> nextOfOther = other.first.next;

            while (null != next && null != nextOfOther)
            {
                // break cyclic loop
                if (next.equals(first))
                    break;

                result = next.equals(nextOfOther);

                if (!result)
                    // We know they aren't equal so break
                    break;

                next = next.next;
                nextOfOther = nextOfOther.next;

            }

            return result;
        }

edited Aug 6, 2014 at 10:16

answered Aug 6, 2014 at 9:17

Maas

1,3679 silver badges20 bronze badges

7 Comments

ccjmne Over a year ago

I see a StackOverflowException coming right away... :)

Maas Over a year ago

I did mention about NULL checks to stop it, Would be happy to learn, how! :)

ccjmne Over a year ago

I think that since his List is circular, every element has a next element set. Consider the list that has only one element: its next and its prev both point to itself! Nowhere is a null reference (if I'm correct).

ccjmne Over a year ago

You're right. Except that the List itself would have that information, while you were suggesting to implement the recursive method in the Element class :) I think that you wouldn't have access to that bit of information you need. Besides that, even if the list wasn't circular, considering a list that has two elements, we'd still never end: while checking for the first ones' equality, you'd check whether its next are the same. This includes checking if the second one's previous' are the same... we're back at the beginning, only 2 stacks deeper :p

ccjmne Over a year ago

Same issue as @user3883676's answer. let's consider two lists: the first one has only one element, e1. Would the second one have e1, e1, e2 and e3, your algorithm would still return true :)

|

Maas · Accepted Answer · 2014-08-06 10:37:44Z

0

How about this, here I will first find and check for length then will check the elements.

public boolean equals(CircularList<T> other)
    {
        boolean result = false;
        result = first.equals(other.first);

        if (!result)
            return result;

        Element<T> next = first.next;
        Element<T> nextOfOther = other.first.next;

        int firstCount = 1;

        while (null != next)
        {
            if (next.equals(first))
                break;

            firstCount++;
            next = next.next;
        }

        int secondCount = 1;

        while (null != nextOfOther)
        {
            if (nextOfOther.equals(other.first))
                break;

            secondCount++;
            nextOfOther = nextOfOther.next;
        }

        if (firstCount != secondCount)
        {
            result = false;
        }

        next = first.next;
        nextOfOther = other.first.next;

        while (firstCount > 1)
        {
            result = next.equals(nextOfOther);
            if (!result)
                // We know they aren't equal so break
                break;

            next = next.next;
            nextOfOther = nextOfOther.next;
            firstCount--;

        }

        return result;
    }

answered Aug 6, 2014 at 10:37

Maas

1,3679 silver badges20 bronze badges

4 Comments

Marco13 Over a year ago

Same here as for ccjmne: Shouldn't two circular lists A,B,C and B,C,A be considered as being equal?

Maas Over a year ago

I think its arguable, consider a method to process the list if its only in the given order. Because we are holding the "first" element and any operation would start from there.

Marco13 Over a year ago

Only the asker can clarify this. (And maybe not even him, but only his advisor ;-)). But an equality test for simple linked lists would be rather trivial, so I guess there's more behind this...

Maas Over a year ago

Totally agree :) Java LinkList doesn't even have any special equals and rather use that of parent. java.util.AbstractList.equals(Object)

Collectives™ on Stack Overflow

Java Method equals circular list

6 Answers 6

4 Comments

4 Comments

Comments

10 Comments

7 Comments

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

4 Comments

4 Comments

Comments

10 Comments

7 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related