CODEWITHSUNDEEP
javaarrayscollectionslinked-listpalindrome
Thomas Yamakaitis
Thomas Yamakaitis

Reputation: 463

isPalindrome - Collection and List Reversal

This is a homework lab for school. I am trying to reverse a LinkedList, and check if it is a palindrome (the same backwards and forwards). I saw similar questions online, but not many that help me with this. I have made programs that check for palindromes before, but none that check an array or list. So, first, here is my isPalindrome method:

public static <E> boolean isPalindrome(Collection<E> c) {
    Collection<E> tmp = c;
    System.out.println(tmp);
    Collections.reverse((List<E>) c);
    System.out.println(c);
    if(tmp == c) { return true; } else { return false; }
}

My professor wants us to set the method up to accept all collections which is why I used Collection and cast it as a list for the reverse method, but I'm not sure if that is done correctly. I know that it does reverse the list. Here is my main method:

public static void main(String...strings) {
    Integer[] arr2 = {1,3,1,1,2};
    LinkedList<Integer> ll2 = new LinkedList<Integer>(Arrays.asList(arr2));
    if(isPalindrome(ll2)) { System.out.println("Successful!"); }
}

The problem is, I am testing this with an array that is not a palindrome, meaning it is not the same backwards as it is forwards. I already tested it using the array {1,3,1} and it works fine because that is a palindrome. Using {1,3,1,1,2} still returns true for palindrome, though it is clearly not. Here is my output using the {1,3,1,1,2} array:

[1, 3, 1, 1, 2]
[2, 1, 1, 3, 1]
Successful!

So, it seems to be properly reversing the List, but when it compares them, it assumes they are equal? I believe there is an issue with the tmp == c and how it checks whether they are equal. I assume it just checks if it contains the same elements, but I'm not sure. I also tried tmp.equals(c), but it returned the same results. I'm just curious is there is another method that I can use or do I have to write a method to compare tmp and c?

Thank you in advance! Tommy

Upvotes: 0

Views: 1572

Answers (3)

fabian
fabian

Reputation: 82461

You need to copy the Collection to a List / array. This has to be done, since the only ordering defined for a Collection is the one of the iterator.

Object[] asArray = c.toArray();

You can apply the algorithm of your choice for checking if this array is a palindrom to check, if the Collection is a palindrom.

Alternatively using LinkedList it would be more efficient to check, if the list is a palindrom without creating a new List to reverse:

public static <E> boolean isPalindrome(Collection<E> c) {
    List<E> list = new LinkedList<>(c);
    Iterator<E> startIterator = list.iterator();
    ListIterator<E> endIterator = list.listIterator(list.size());

    for (int i = list.size() / 2; i > 0; i--) {
        if (!Objects.equals(startIterator.next(), endIterator.previous())) {
            return false;
        }
    }
    return true;
}

Upvotes: 0

Joop Eggen
Joop Eggen

Reputation: 109557

Many small points

public static <E> boolean isPalindrome(Collection<E> c) {
    List<E> list = new ArrayList<>(c);
    System.out.println(list);
    Collections.reverse(list);
    System.out.println(list);
    return list.equals(new ArrayList<E>(c));
}

Reverse only works on an ordered list. One makes a copy of the collection. One uses equals to compare collections.

public static void main(String...strings) {
    int[] arr2 = {1, 3, 1, 1, 2};
    //List<Integer> ll2 = new LinkedList<>(Arrays.asList(arr2));
    List<Integer> ll2 = Arrays.asList(arr2);
    if (isPalindrome(ll2)) { System.out.println("Successful!"); }
}

Upvotes: 0

Alex Chermenin
Alex Chermenin

Reputation: 858

In your code c and tmp are links to same collection and tmp == c will be always true. Your must clone your collection to new instance, for example: List<E> tmp = new ArrayList(c);.

Upvotes: 2

Related Questions