python constructor is not returning None when calling recursively

Question

The following code is not returning None but some mysterious "main_.link_list object":

class link_list(object):
    """a link list class"""
    def __init__(self, list):
        super(link_list, self).__init__()
        pdb.set_trace()
        if list==[]:
            return None
        else:
            self.value = list[0]
            self.next = link_list(list[1:len(list)])

Test code prints 'False':

l=link_list([1,2,3])
print l.next.next.next==None

Why?

Answer 1

.__init__() is not really a constructor.

__init__ as a constructor?

The object will be created whether or not you return None from .__init__(). As @Ignacio Vazquez-Abrams noted in the comments, Python expects None as the return value from .__init__(); you can't return anything else anyway. If you need to signal some sort of catastrophic error, you should raise an exception.

In your example, you should probably have a class that represents a complete linked list, with a "head" reference and a "tail" reference, and another class that represents a data entry in the linked list. Then the linked list class itself can be tested for a null list by checking to see if head is None.

EDIT: Upon a little bit of further thought, your single-class implementation will work; it's just that we need to set .next to None inside .__init__(). Here is my edit of your code:

class link_list(object):
    """a link list class"""
    def __init__(self, lst):
        super(link_list, self).__init__()
        pdb.set_trace()
        if len(lst) > 1:
            self.value = lst[0]
            self.next = link_list(lst[1:])
            print "id == %d, linked in %d" % (id(self), id(self.next))
        elif len(lst) == 1:
            self.value = lst[0]
            self.next = None
            print "length-one case: id == %d" % id(self)
        else:
            self.value = None
            self.next = None
            print "length-zero case: id == %d" % id(self)

l=link_list([1,2,3])
print l.next.next.next is None

Notes:

• I fixed the indentation.

• I used lst instead of list for the variable name, so as not to shadow the built-in type list.

• I added some print statements to help you watch what is going on.

EDIT: And, for completeness, here is an implementation using two classes: a class that represents a list and might be zero-length, and a class that represents one entry in the list. A for loop builds the chain of entries, and can build a list from any sequence (including an iterator); slicing is not used so the sequence does not have to be a list.

class link_list_val(object):
    """one value for a linked list"""
    def __init__(self, value):
        self.value = value
        self.next = None

class link_list(object):
    """a link list class"""
    def __init__(self, seq):
        self.head = None

        for value in seq:
            x = link_list_val(value)
            if self.head is None:
                self.head = x;
                cur = x
            else:
                cur.next = x
                cur = x

l=link_list([1,2,3])
print l.head.next.next.next is None

EDIT: Here's one more version. This uses iteration to build the linked list, not tail recursion, but does it with a single class. The trick is that the .__init__() function needs to know whether it is building a whole linked list, or just making one instance to be used to build a linked list; hence the check for seq is None. If the user passes in a sequence, .__init__() builds a whole linked list, but otherwise it just makes one instance to be used as a link in the list.

class link_list(object):
    """a link list class"""
    def __init__(self, seq=None):
        super(link_list, self).__init__()
        if seq is None:
            return
        pdb.set_trace()
        itr = iter(seq)
        try:
            self.value = next(itr)
        except StopIteration:
            self.value = None
            self.next = None
            return
        cur = self
        for value in itr:
            cur.next = link_list()
            cur = cur.next
            cur.value = value
        cur.next = None

l=link_list([])
print l.next is None
l=link_list([1,2,3])
print l.next.next.next is None

First we get a new iterator from the sequence. Then we attempt to pull a value from the sequence with next(). If this fails we have a zero-length linked list and return it; if this succeeds, we use that value for the head of the linked list and then loop over the rest of the values from the sequence.

Playing directly with iterators may seem tricky, but I think it is the cleanest way to handle cases like this, where we want to pull the first item from the sequence and then loop over the remaining ones, and we don't want to use slicing (and thus only work with an actual list).

Answer 2

class Item(object):
    '''Linked list'''

    def __new__(cls, lst):
        '''Construct object (allocate the memory)'''
        if lst:
            return super(Item, cls).__new__(cls)

    def __init__(self, lst):
        '''Initialize object (already created)'''
        self.value = lst[0]
        self.next = self.__class__(lst[1:])

    def __repr__(self):
        '''Representate as string'''
        return "%s(%s) -> %s" % (
            self.__class__.__name__,
            self.value,
            repr(self.next)
        )

>>> items = Item([1,2,3])
>>> print items
Item(1) -> Item(2) -> Item(3) -> None
>>> items.next.next.next is None
True