HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Checking if a LinkedList is a palindrome

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
palindromecheckinglinkedlist

Problem

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 list) {
        boolean isPalindrome = true;
        Stack s = new Stack();
        Iterator 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 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.

Solution

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 list) {
    ListIterator forward = list.listIterator(0);
    ListIterator 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

Code Snippets

if (s.pop() != iterator2.next()) {
if (!s.pop().equals(iterator2.next())) {
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;
}

Context

StackExchange Code Review Q#161396, answer score: 6

Revisions (0)

No revisions yet.