[Tutor] Complexity of list operations

[Dave Kuhlman]

On Tue, Oct 23, 2007 at 08:17:33PM -0400, Danny Yoo wrote:

[helpful explanation snipped]

> 
> That being said, if all our operations are applied only at the end of the 
> list, the time complexity of those two operations look better.  We can 
> argue for O(1) behavior under that particular restriction.  But I think 
> Kent was considering the worst-case behavior, since it's an upper bound on 
> how bad things can get.

Danny -

Thanks for this explanation.  I've wondered about the costs of
using a list as a FIFO data structure (first in, first out), and
doing, for example:

    lst.insert(0, obj)

and:

    obj = lst.pop()

Also, this is probably a good place to mention deque
(http://docs.python.org/lib/deque-objects.html), which attempts to
reduce those costs.

Dave

-- 
Dave Kuhlman
http://www.rexx.com/~dkuhlman