"Kent Johnson" <[EMAIL PROTECTED]> wrote
For example a linked list is pretty much a Python list.
Other than the very different timing characteristics!
True, but its pretty rare that timing issues are a reason
for me to choose a data structure - especially if I need
to hand code it! :-)
Python lists are O(1) for reading or writing a value at an index,
O(n) for inserting and deleting. Linked lists are O(n) for reading
and writing and O(1) for insertion and deletion (at a known
location).
I would say O(1) only if you already have a reference to
that location (ie its known in that sense) but if you know that
it's at position 23 but you only have a reference to the head
you still need to navigate sequentially to the 23rd element
so its still an O(n). O(1) only applies when inserting at
the next position to where you currently are. That's not too
common a scenario in my experience.
But the geneal point is a good specific example (and I
was struggling to think of one!) where you might choose a
non standard list over the vanilla version. The array module
is another case where performance is improved over the
standard lists.
Alan G.
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
