[Tutor] Intermediate/advanced concepts
alan.gauld at btinternet.com
Sat Nov 8 00:16:07 CET 2008
"Kent Johnson" <kent37 at tds.net> 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
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
More information about the Tutor