patternjavaMinor
Checking if a LinkedList is a palindrome
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.
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.
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:
That's doing a native object comparison, and you are comparing
Then, your
Further, consider that your input is a
You can see this running in ideone: https://ideone.com/LmfQrB
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.