Checking if a LinkedList is a palindrome

Question

I would like to know if my code is \$O(n)\$ space complexity. The code checks if a doubly linked list is Palindrome.

public boolean isPalindromeList(LinkedList<Integer> list) {
 boolean isPalindrome = true;
 Stack<Integer> s = new Stack<Integer>();
 Iterator<Integer> iterator = list.iterator();
 // step1: iterate over the list and each put the element in the Stack
 while (iterator.hasNext()) {
 s.push(iterator.next());
 }
 // step2: pop elements from Stack and compare it while iterating through
 // the list
 Iterator<Integer> iterator2 = list.iterator();
 while (iterator2.hasNext()) {
 if (s.pop() != iterator2.next()) {
 return false;
 }
 }
 // for example List = {1,2,5,3}. Stack.pop()=3 do compare 3 == 1 if no
 // return false else continue
 // repeat pop() and compare with next element in the List
 return isPalindrome;
 }

According to my understanding, it's \$O(1)\$ space complexity, because it's just changing the node that iterator points to, not creating a new variable or reference. But, I'm not sure if pointing to another object results in creating a new variable in Java Stack memory referencing the current node object in the heap space.

Answer 1

Stack<Integer> s = new Stack<Integer>();
// step1: iterate over the list and each put the element in the Stack
while (iterator.hasNext()) {
 s.push(iterator.next());
}

This alone means it's O(n). Because stack has internally an array to hold all its elements that needs to grow as it holds more elements. Each reference to an element also takes up space.

Answer 2

As Ratchet Freak points out, your code uses an \$n\$ size stack to manage the reversal of the list, so it's \$O(n)\$ space complexity. The question is whether there's a better way too, though.

First up, your comparison here is very dubious:

if (s.pop() != iterator2.next()) {

That's doing a native object comparison, and you are comparing Integer, and not int. This is bound to fail, and I am surprised it works for you (I presume Java is reusing Objects for your int value boxing). You should be calling this instead:

if (!s.pop().equals(iterator2.next())) {

Then, your isPalindrome variable is useless. It's never set to false. Instead you return immediately if it's not a palindrome (which is a good thing).

Further, consider that your input is a LinkedList which is a double-linked implementation (as you pointed out) which means a reversed iteration is "easy".

public boolean isPalindromeList(LinkedList<Integer> list) {
 ListIterator<Integer> forward = list.listIterator(0);
 ListIterator<Integer> reverse = list.listIterator(list.size());
 while (forward.hasNext()) {
 if (!forward.next().equals(reverse.previous())) {
 return false;
 }
 }
 return true;
}

You can see this running in ideone: https://ideone.com/LmfQrB

• rolfl: Edited to fix a problem in the reverse iterator, and added links to ideone.
• the_lotus: I think you could stop midway in the loop.
• rolfl: With a list iterator mechanism it's not as "clean" to count to the middle, but I agree, that it would save half the time if it can easily be done. It changes the loop from a while-loop to a for-loop I presume.
• ratchet freak: you can get the current index from the listiterator so it's not that big of a deal.
• SarahData: @rolfl I didn't know about ListIterator, it's very useful in this case and it's possible to fix the traversal to the half. So time complexity in this case is O(n) at worst and space complexity is O(1).