3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$
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.

| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Edited to fix a problem in the reverse iterator, and added links to ideone. \$\endgroup\$ – rolfl Apr 21 '17 at 15:29
  • 1
    \$\begingroup\$ I think you could stop midway in the loop. \$\endgroup\$ – the_lotus Apr 21 '17 at 15:41
  • \$\begingroup\$ 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. \$\endgroup\$ – rolfl Apr 21 '17 at 20:00
  • \$\begingroup\$ you can get the current index from the listiterator so it's not that big of a deal. \$\endgroup\$ – ratchet freak Apr 23 '17 at 9:55
  • \$\begingroup\$ @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). \$\endgroup\$ – SarahData Apr 27 '17 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.