[Tutor] binary trees/ linked lists

[Magnus Lycka]

At 11:32 2002-10-03 +0100, alan.gauld@bt.com wrote:
> > Is there anything like a linked list
>
>A Python list is like a linked list....

Not really...

I'd say a python list is like a vector in C++
etc. It's not implemented as a linked list,
and it neither has the interface, nor the
timing characteristics you would expect from
a linked list.

In a linked list you reach a certain element
by traversal. Each element points to the next.
Lists can be double-linked (also having a
pointer to the previous), and then it might
be as fast to find the last element as the
first, but to find an element in the middle,
you need to walk through a lot of elements.

A vector finds each element, given it's index
as a simple offset from a base adress. Fetching
any element is equally fast.

In python, fetching any element from a list is
equally fast, regardless of position.

A linked list is, on the other hand, very fast
for inserting new elements anywhere. You just
have to change the pointers in the immediate
vicinity.

In a vector, it's quick to append an element to
the end, but if you insert it in the beginning,
you have to move all the other elements, which
is slow.

With a big python list, .append(0) is much, much
faster than .insert(0,0)



--=20
Magnus Lyck=E5, Thinkware AB
=C4lvans v=E4g 99, SE-907 50 UME=C5
tel: 070-582 80 65, fax: 070-612 80 65
http://www.thinkware.se/  mailto:magnus@thinkware.se