[Tutor] Tree that doesn't grow [implementing linked lists]

Danny Yoo dyoo at hkn.eecs.berkeley.edu
Wed Mar 10 20:03:39 EST 2004


> > Let's take a detour for a moment.  Take a look at the following code:
> >
> > ###
> > def makeListEmpty(L):
> >     """Tries to empty out L.  Buggy."""
> >     L = []
> >
> > L = [1, 2, 3, 4, 5]
> > makeListEmpty(L)
> > print L
> > ###
> >
> > What do you expect to see here?  Does it do what you expect?
>
> What you are saying is this. In python, function is pass by value except
> if you using list.


Hi Zahar,


Actually, everything is "pass by value" in Python.  Lists are no
different, and that's why the code above doesn't do anything:

###
>>> def makeListEmpty(L):
...     L = []
...
>>> L = range(10)
>>> makeListEmpty(L)
>>> L
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
###




At the moment, you're trying to implement binary trees.  If you're still
stuck, try something simpler.  Have you tried implementing a simpler
structure, like a linked list?


Here's is a buggy implementation of a linked list that simulates
essentially the same bug:

###
class Node:
    def __init__(self, value, next):
        """Constructs a new node with attributes 'value' and 'next'."""
        self.value, self.next = value, next


def make_llist():
    """Constructs a new Linked List.

    Implementation node: the list is initially a sentinel node.
    """
    return Node("sentinel front", None)


def display(llist):
    """Displays a linked list."""
    node = llist.next  ## skip the sentinel node
    print "[",
    while node != None:
        print node.value,
        node = node.next
    print "]"


def insert(llist, value):
    """Inserts a new value into a linked list."""
    insert_helper(llist, value)


def insert_helper(node, value):
    """Tries to add a new value to the end of a list.  Broken."""
    if node == None:
        node = Node(value, None)
    else:
        insert_helper(node.next, value)
###


I've removed most of the class stuff to make things a little simpler, plus
I've modified the representation slightly so that every list has a
"sentinel" head.



Let's see how this code might work:

###
>>> l = make_llist()
>>> l.next = Node("foobar", None)  ## let's manually insert 'foobar'
>>> display(l)
[ foobar ]
>>>
>>>
>>> insert(l, "hello")             ## let's try it through our function
>>> display(l)
[ foobar ]                         ## nope, no effect.
>>>
>>>
>>> l.next.next = Node("manually_inserted", None)
>>> display(l)
[ foobar manually_inserted ]
###




Everything here except the insert_helper() is functioning, and, again
insert_helper() appears to have no effect.  So let's take another look at
the insert_helper():


###
def insert_helper(node, value):
    """Tries to add a new value to the end of a list.  Broken."""
    if node == None:
        node = Node(value, None)
    else:
        insert_helper(node.next, value)
###


insert_helper() is recursive, so we can break this down into cases.
What's the base case?



The code, as it stands now, thinks that the base case is when

    if node == None:
        node = Node(value, None)

As we saw above, though, because of call-by-value, this really has no
effect:  we're just rebinding 'node' to a new Node, and there's no linking
going on between our list and the new node.


If we have a list like:

    "sentinel"


and we want to add "node2", it's not enough to just draw a new node:

    "sentinel"         "node2"


because "node2" is floating around in space, and is not attached to
anything.  That's what something like:

    if node == None:
        node = Node(value, None)

is doing.



But instead, we need to do more: we need to draw a link from one node to
another:

    "sentinel"  ---->  "node2"

where we tie the 'next' arrow of some node and loop it at the Node that
we've just constructed.


The base case on insertion should not be when we've fallen off our list
and hit None, because, by that time, it's too late to try attaching
anything to the list.  We need to be anchored right at the edge, teetering
at the very end, so that we can tie an arrow with 'next' to our new node.
And that's a different base case than 'node == None'.



Anyway, hope this helps.  Good luck!




More information about the Tutor mailing list