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)

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

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.

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.

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.