pointer to pointer in python

Question

I am relatively new to python and am trying to understand how to relate Python with C/C++. Consider the problem: Check if a given Linked List is a Palindrome. From this source, I found a very effective solution:

// Initial parameters to this function are &head and head
bool isPalindromeUtil(struct node **left, struct node *right)
{
 /* stop recursion when right becomes NULL */
 if (right == NULL)
 return true;
 /* If sub-list is not palindrome then no need to
 check for current left and right, return false */
 bool isp = isPalindromeUtil(left, right->next);
 if (isp == false)
 return false;
 /* Check values at current left and right */
 bool isp1 = (right->data == (*left)->data);
 /* Move left to next node */
 *left = (*left)->next;
 return isp1;
}
// A wrapper over isPalindromeUtil()
bool isPalindrome(struct node *head)
{
 isPalindromeUtil(&head, head);
}

Basically a pointer to pointer is assigned to the front (left pointer) and a pointer is assigned to the end of the list (right pointer). Once the pointers reach their respective positions, they recurse through and find match the values. Here, *left maintains the state of the pointer to pointer whose value persists through the recursive loop. One of the solutions in python would be passing the left pointer back along with the boolean value. However if there are multiple pointer to pointers being used, the number of return elements explode! Bad design. Is there any other way of doing it?

EDIT:

Thank you so much for the responses! I forgot to mention that I'm not trying to solve the Palindrome problem here. I am trying to understand if there is a Pythonic equivalent way of working with pointers. What I am trying to comprehend is when if a question is posed to me, which uses data structures such as linked list, should I try to convert it into other data structures such as list or if I need to be creative and solve the question using the same data structure. Since pointer to pointer is pretty important concept in Linked List and BST, is there an equivalent solution or work around for this concept?

Edit #2: The rough code I have come up with is as below. However, the left_ptr remains stuck in the same position since its a pointer and not pointer to pointer:

def palindrome_utils(self, left_ptr, right_ptr):
 if right_ptr is None:
 return True
 prev_result = self.palindrome_utils(left_ptr, right_ptr.get_link())
 cur_result = left_ptr.get_data() == right_ptr.get_data()
 left_ptr = left_ptr.get_link()
 return cur_result and prev_result
def palindrome(self):
 return self.palindrome_utils(self.head, self.head)

• TigerhawkT3: Another way of working with pointers, or another way of determining whether a word is a palindrome?
• NightShadeQueen: When you say "linked list", are you working with collections.deque?
• PM 2Ring: It's not always useful to try to replicate C/C++ data structures & algorithms in Python. Bear in mind that the (relative) speed of various algorithms may differ radically when implemented in Python rather than C/C++, due to interpreter overheads. Eg, a Python library function that operates on a sequence can be blazingly fast compared to operating on the list items in a Python for or while loop because the function can process the list at C speed. TL; DR: Don't try to write C/C++ when you're writing in Python.

Answer 1

EDIT: Added l == l[::-1] as is_palindrome5, which is pretty fast and by far the most readable and pythonic.

The fastest I can get to check palindromes is this one-liner:

def is_palindrome1(l):
 return l[:len(l) // 2] == l[(len(l)+1) // 2:][::-1]

Checking non-palindromes is fastest with this python conversion of the c++ function in your question:

def is_palindrome2(l):
 left = 0
 right = len(l) - 1
 for i in xrange(0,len(l) / 2):
 if l[right] != l[left]:
 return False
 left += 1
 right -= 1
 return True

This is because this function doesn't create any new lists before beginning to compare elements. Note that I used non-palindromes which differ in the first and the last elements, so the check returns immediatly after the first comparison (which is not always the case for non-palindromes).

I also tested the answer of mistermiyagi (is_palindrome3) and the answer of PM 2Ring (is_palindrome4):

import itertools
def create_palindrome(n):
 return range(1,n) + range(n,0,-1)
def is_palindrome1(l):
 return l[:len(l) // 2] == l[(len(l)+1) // 2:][::-1]
def is_palindrome2(l):
 left = 0
 right = len(l) - 1
 for i in xrange(0,len(l) / 2):
 if l[right] != l[left]:
 return False
 left += 1
 right -= 1
 return True
def is_palindrome3(seq):
 for l, r in itertools.izip(iter(seq), reversed(seq)):
 if l != r:
 return False
 return True
def is_palindrome4(seq):
 return all(l == r
 for _, l, r in itertools.izip(xrange((1 + len(seq)) // 2),
 iter(seq), reversed(seq)))
def is_palindrome5(l):
 return l == l[::-1]
if __name__ == '__main__':
 import timeit
 setup_palindrome = "from __main__ import create_palindrome, %s; l = create_palindrome(%i)"
 setup_non_palindrome = "from __main__ import %s; l=range(%i)"
def test(f, n):
 return (timeit.timeit("%s(l)" % f, setup=setup_palindrome % (f, n), number=100000),
 timeit.timeit("%s(l)" % f, setup=setup_non_palindrome % (f, n), number=100000))
small = 5
big = 1000
for f in is_palindrome1, is_palindrome2, is_palindrome3, is_palindrome4:
 print("%s small list: palindrome: %f non-palindrome: %f" % ((f.__name__,) + test(f.__name__, small)))
for f in is_palindrome1, is_palindrome2, is_palindrome3, is_palindrome4:
 print("%s big list: palindrome: %f non-palindrome: %f" % ((f.__name__,) + test(f.__name__, big)))

Results:

is_palindrome1 small list: palindrome: 0.093779 non-palindrome: 0.073669
is_palindrome2 small list: palindrome: 0.087658 non-palindrome: 0.048855
is_palindrome3 small list: palindrome: 0.085866 non-palindrome: 0.056385
is_palindrome4 small list: palindrome: 0.139685 non-palindrome: 0.123519
is_palindrome5 small list: palindrome: 0.021798 non-palindrome: 0.022422
is_palindrome1 big list: palindrome: 1.589591 non-palindrome: 0.432679
is_palindrome2 big list: palindrome: 9.414250 non-palindrome: 0.043481
is_palindrome3 big list: palindrome: 7.315568 non-palindrome: 0.056859
is_palindrome4 big list: palindrome: 6.655833 non-palindrome: 0.128915
is_palindrome5 big list: palindrome: 2.095099 non-palindrome: 0.283472

• NightShadeQueen: Would you mind also timing a deque?
• MisterMiyagi: Thanks for the timing results! You might want to check non-palindromes as well. ;)
• user2804197: @MisterMiyagi Added the non-palindromes
• greybeard: While the question was tagged python-3.x from the start, this looks a Python 2 answer - l[:len(l) // 2] == l[-(len(l)//2):][::-1].

Answer 2

Here's a variation of MisterMiyagi's answer that doesn't test each pair twice:

import itertools
def is_palindrome(seq):
 maxi = (1 + len(seq))//2
 for i, l, r in itertools.izip(xrange(maxi), iter(seq), reversed(seq)):
 #print l, r
 if l != r:
 return False
 return True
data = ('abcba', '123321', 'ABCDBA')
for seq in data:
 print seq, is_palindrome(seq)
 a = list(seq)
 print a, is_palindrome(a)

output

abcba True
['a', 'b', 'c', 'b', 'a'] True
123321 True
['1', '2', '3', '3', '2', '1'] True
ABCDBA False
['A', 'B', 'C', 'D', 'B', 'A'] False

Or, as a one liner:

def is_palindrome(seq):
 return all(l == r
 for _, l, r in itertools.izip(xrange((1 + len(seq))//2), 
 iter(seq), reversed(seq)))

Note that all() short-circuits, so it will bail out as soon as a mismatch is detected.

• MisterMiyagi: You might want to use any( l != r for ... for extra verbosity, but I guess this is the best solution for expressiveness, compatibility and speed.

Answer 3

You could do the same way the C++ code does it.

You have a class Node with two members "data" and "next" that you use to make a home made chained list.

Instead of a pointer to node just use a reference to node. Instead of a pointer to pointer use a list containing one Node element.

Here is what can become relevant part of the code

# Recursive call
isp = isPalindromeUtil(left, right.next);
# A wrapper over isPalindromeUtil()
def isPalindrome(head)
 return isPalindromeUtil([head], head)
# Move left to next node 
 left[0] = left[0].next

This way, it will work as in the C++ code, that is when you "move left to next node" in the function it will be moved also for the caller of the function.

That is not a recommended way to do recursive calls. This example is not a good design. It is poorly commented too: "If sub-list is not palindrome then no need to check for current left and right, return false". This is wrong. If list is "ABCDEF", the innermost call of the recursion will test A and F, not C and D. It will also test everything twice: A-F, B-E, C-D, D-C, E-B, F-A, that is not really the most efficient way.

Answer 4

Python does not have the notion of pointers like C/C++, so certainly no double pointers. All objects though (everything but basic types), are references (non-const). If you'd have a Node class you can write the algorithm in a fairly similar way.

Answer 5

If you want to be recursive, you can slice the sequence:

def is_palindrome(seq):
 if len(seq) < 2:
 return True
 return seq[0] == seq[-1] and is_palindrome(seq[1:-1])

However, recursion in Python isn't encouraged. Python doesn't support tail call optimisation, and probably never will.

• redevined: shouldn't it be and is_palindrome(seq[1:-1])?
• Open AI - Opting Out: @Cipher Fixed, thanks. That's the second off by one error I've posted today. )c:
• PM 2Ring: As the old saying goes: "There are only two hard things in Computer Science: cache invalidation, naming things, and off-by-one errors.
• PM 2Ring: It should be mentioned that recursion should be avoided in Python (when practical), since Python doesn't have tail call optimization.
• Open AI - Opting Out: @PM2Ring And C++ does?

Answer 6

The most highly-optimized version of a Python palindrome checker is as follows:

def is_palindrome(s):
 s = ''.join(s) # just in case a deque is passed
 return s==s[::-1]

I am, of course, optimizing for the time required to write, debug, and maintain the code. If you want to optimize for memory or processing time, there's a lot of stuff you can do, including writing it in C or assembly, but you should make absolutely sure that you actually need this kind of optimization before you try it.

• MisterMiyagi: This will actually not work with python's double linked list deque - it does not support slicing.
• TigerhawkT3: @MisterMiyagi - I assumed that the exact data structure is an implementation detail. If we're working with a sequence of characters (which is what a palindrome is), the best way to represent that in Python is with a string. If for some reason you have a linked list of characters, you can always join() it before sending it to this function.
• MisterMiyagi: Sorry for being pedantic, but the OP specifically asked to "Check if a given Linked List is a Palindrome." I would totally agree that for a string or list, your answer is the way to go, and if anybody cannot spare the memory for the extra copy, he's got quite another problem.
• TigerhawkT3: @MisterMiyagi - I added the trivial join() I mentioned earlier. Now it will handle deques.