Palindrome check throws infinite loop (using iterator and linked lists collection)

Question

I´m trying to write a method to determine if a singly linked list of type string is a palindrome.

The idea is to copy the second half to a stack, then use an iterator to pop the elements of the stack and check that they are the same as the elements from 0 to around half of the singly linked list.

But my iterator method is throwing an infinite loop:

public static boolean isPalindrome(LinkedList<String> list, Stack<String> stack ) {
    int halfList = (int) Math.ceil(list.size()/2);   // we get half the list size, then round up in case it´s odd
    // testing: System.out.println("half of size is " + halfList);`
    
    // copy elements of SLL into the stack (push them in) after reaching the midpoint
    int count = 0;
    boolean isIt = true;
    
    Iterator<String> itr = list.iterator();  
    Iterator<String> itr2 = list.iterator();  
    
    System.out.println("\n i print too! ");
    
    // CHECK!! Node head = list.element();
    
    // LOOP: traverse through SLL and add the second half to the stack (push)
    // if even # of elements
    if ( list.size() % 1 == 0 ) {
        System.out.println("\n me too! ");
        while ( itr.hasNext() ) {
            String currentString = itr.next();      // this throws an exception in thread empty stack exception
            count ++;
            if ( count == halfList ) stack.push(list.element());
            // THIS IS THE INFINITE LOOP
            System.out.println("\n me three! ");
        }
    }
    
    // else, if odd # of elements
    else {
        while ( itr.hasNext() ) {
            count ++;
            if ( count == halfList -1 ) stack.push(list.element());
        }
    }
    
    // Now we compare the first half of the SLL to the stack (pop off elements)
    // even
    if ( list.size() % 1 == 0 ) {       
        while ( itr2.hasNext() ) {
            count ++;
            if ( count == halfList +1 ) break;
            int compared = stack.pop().compareTo(list.element());
            if ( compared != 0) isIt = false;     // if when comparing the two elements, they aren´t similar, palindrome is false
        }
    }   
    // odd
    else {
        while ( itr2.hasNext() ) {
            count ++;
            if ( count == halfList ) break;
            int compared = stack.pop().compareTo(list.element());
            if ( compared != 0) isIt = false;
        }
    }

    return isIt;
}

What am I doing wrong?

Answer 1

There are many issues:

• list.size() % 1 == 0 is not checking whether the size is even. The correct check is % 2.
• The stack exception cannot occur on the line where you put that comment. It occurs further down the code where you have stack.pop(). The reason for this exception is that you try to pop an element from a stack that has no more elements.
• The infinite loop does not occur where you put that comment. It would occur in any of the other loops that you have further in the code: there you never call itr.next() or itr2.next(), and so you'll loop infinitely if you ever get there.
• The stack never gets more than 1 value pushed unto it. This is because you have a strict equality condition that is only true once during the iteration. This is not what you want: you want half of the list to end up on the stack. This is also the reason why you get a stack error: the second half of your code expects there to be enough items on the stack.
• push(list.element()) is always going to push the first list value to the stack, not the currently iterated one. This should be push(currentString).
• count ++; is placed at an unintuitive place in your loops. It makes more sense if that line is moved to become the last statement in the loop.
• The if ( count statements are all wrong. If you move count ++ to be the last statement, then this if should read if ( count >= halfList ) for the even case, and if ( count > halfList ) for the odd case. Of course, it would have been easier if halfList would have been adapted, so that you can deal equally with the odd and even case.
• The second part of your code has not reset the counter, but continues with count ++. This will make that if ( count == halfList ) is never true, and so this is another reason why the stack.pop() will eventually raise an exception. Either you should reset the counter before you start that second half (with count = 0;) or, better, you should just check whether the stack is empty and then exit the loop.
• The second half of your code does not need to make the distinction between odd or even.
• Instead of setting isIt to false, it is better to just immediately exit the function with return false, as there is no further benefit to keep on iterating.
• The function should not take the stack as an argument: you always want to start with an empty stack, so this should be a local variable, not a parameter.
• There is no use in doing Math.ceil on a result that is already an int. Division results in an int when both arguments are int. So to round upwards, add 1 to it before dividing: (list.size()+1) / 2
• Avoid code repetition

Most of these problems are evident when you debug your code. It is not so helpful to put print-lines with "I am here". Beter is to print values of your variables, or to step through your code with a good debugger, while inspecting your variables. If you had done that, you would have spotted yourself many of the issues listed above.

Here is a version of your code where the above issues have been resolved:

public static boolean isPalindrome(LinkedList<String> list) {
    Stack<String> stack = new Stack<String>(); 
    int halfList = (list.size()+1) / 2; // round upwards
    Iterator<String> itr = list.iterator(); 
    
    while (halfList-- > 0) itr.next(); // skip first half of list
    while ( itr.hasNext() ) stack.push(itr.next()); // flush rest unto stack

    Iterator<String> itr2 = list.iterator();  
    while ( itr2.hasNext() && !stack.empty()) { // check that stack is not empty
        if (stack.pop().compareTo(itr2.next()) != 0) return false; // no need to continue
    }
    
    return true;
}