Recursively traverse linked list -- help!
Jason
caljason76 at yahoo.com
Tue Feb 19 20:46:30 EST 2002
# I am a Python novice so I don't really understand how things
# work, yet. So some of this may either be wrong or not the
# Python way. Also I have no idea why the 'if __name__ == ...'
# construct is needed instead of just the naked main statements.
#
# A few notes on the code. There are two solutions: list_naked
# and list.
#
# list_naked is the simplies solution, it has no wrapper object
# and each node in list_naked is the head of a list. You can see
# the recursion in list_naked.sum() and list_naked.__str_all(),
# where you will notice the if statements that test for the
# base case of the recursion.
#
# list_wrapped is a little more complex. It has a wrapping object
# that is always used to refer to the list (unlike list_naked
# where the head of the list can change when a new value is pushed,
# hence the ll = ll.push(ll,x) assignment). Here, the recursion
# is stopped by the_list_wrapped_empty_node and all the control
# flow is done by the interpreter. I like this best, because I
# hate explicit control flow in programs and I think that it makes
# it easier to see the forest instead of the trees. Looking at
# list_wrapped.sum() it is clear: add this node to the sum of the
# rest. In list_naked.sum() you now have to look at two statements
# which do the same thing semantically. With list_wrapped there
# is no way to forget to check for your base case because you don't
# check anything! With just a list it seems a little too much,
# but when you start playing with various tree types and graphs
# it makes the code so much more readable.
#
# Also, can somebody help me find the documentation to the builtin
# procedures, like print(). I checked the __builting__ module docs
# but there is nothing there. Thanks
#
# -j
class list_naked:
def __init__(s, data, next = None):
s.data, s.next = data, next
def __str__(s):
return "[%s]" % s.__str_all()
def push(s, data):
return list_naked(data, s)
def sum(s):
if s.next: return s.data + s.next.sum()
else: return s.data
def __str_all(s):
if s.next: return str(s.data) + " " + s.next.__str_all()
else: return str(s.data)
class list_wrapped_node:
def __init__(s, data, next): s.data, s.next = data, next
def __str__(s): return str(s.data) + " " + str(s.next)
def sum(s): return s.data + s.next.sum()
class list_wrapped_empty_node(list_wrapped_node):
def __init__(s): pass
def __str__(s): return ""
def sum(s): return 0
class list_wrapped:
def __init__(s): s.head = list_wrapped_empty_node()
def __str__(s): return "[" + str(s.head) + "]"
def push(s, data): s.head = list_wrapped_node(data, s.head)
def sum(s): return s.head.sum()
if __name__ == '__main__':
ll = list_naked(0)
for i in range(6): ll = ll.push(i+1)
print ll
print ll.sum()
l = list_wrapped()
for i in range(6): l.push(i)
print l
print l.sum()
More information about the Python-list
mailing list