[Tutor] lists [Twisted Linked Lists / Hansel and Gretel]

[Danny Yoo]

On Thu, 25 Apr 2002, Lloyd Hugh Allen wrote:

> "Victor R. Cardona" wrote:
> > My mistake. Although, I still can't think of a reason why you would want
> > to go out of your way to implement a linked list in Python.
> >
> > Thanks,
> > Victor
>
> I'd like to, as an academic exercise...I hear they're an important
> construct to understand. I Python okay, but don't C so well (-4.0 in one
> eye, -4.5 in the other).

My personal feeling is that you don't need "linked lists"... at least, not
at first.  For most purposes, normal Python lists work perfectly well to
allow us to store collections of data.


But when we get more involved with programming, we might find outselves
less interested in collecting objects, and more interested in representing
the relationships between those objects.


Here's a concrete example of why structure is important:

    http://www.mordent.com/folktales/grimms/hng/hng.html

"""
Early in the morning came the woman, and took the children out of their
beds. Their piece of bread was given to them, but it was still smaller
than the time before. On the way into the forest Hansel crumbled his in
his pocket, and often stood still and threw a morsel on the ground.
"Hansel, why do you stop and look round " said the father, "go on." "I am
looking back at my little pigeon which is sitting on the roof, and wants
to say good-bye to me," answered Hansel. "Fool!" said the woman, "that is
not Your little pigeon, that is the morning sun that is shining on the
chimney." Hansel, however, little by little, threw all the crumbs on the
path.

The woman led the children still deeper into the forest, where they had
never in their lives been before. Then a great fire was again made, and
the mother said: "Just sit there, you children, and when you are tired you
may sleep a little; we are going into the forest to cut wood, and in the
evening when we are done, we will come and fetch you away." When it was
noon, Gretel shared her piece of bread with Hansel, who had scattered his
by the way. Then they fell asleep and evening passed, but no one came to
the poor children. They did not awake until it was dark night, and Hansel
comforted his little sister and said: "Just wait, Gretel, until the moon
rises, and then we shall see the crumbs of bread which I have strewn
about, they will show us our way home again."
"""


Hansel is using a linked list traversal algorithm.  Here, it's the linkage
--- the structural relationship --- between the breadcrumbs that Hansel
really cares about, and not the breadcrumbs itself.


Hope this helps!