[Tutor] Intermediate/advanced concepts

[Alan Gauld]

"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 
> 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.