[Python-Dev] FIFO data structure?

[Jeremy Fincher]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Sunday 20 April 2003 06:53 am, andrew cooke wrote:
> i haven't looked at the code, but when you mention lists are you referring
> to standard python structures?  i understood that the thing in python that
> looks like a list is actually an array (a simple one, not a vlist), so
> access to index elements is done in constant time.

But deleting an element from the beginning is O(n), because all the elements 
have to be moved back to replace it.  So queues implemented via list.append 
and list.pop(0) are O(N) in dequeue.

> (the links you gave don't work for me.)

Ah, shoot, I always forget the ~fincher.

New links:

<http://www.cis.ohio-state.edu/~fincher/fifo.py>
<http://www.cis.ohio-state.edu/~fincher/test_fifo.py>

Jeremy
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (FreeBSD)

iD8DBQE+oskdqkDiu+Bs+JIRAu/tAJ0dPjbD65e5Kw1XctbrWwYGt4jAZgCaAgF3
2+3nzAjeswigkg9697bx38Y=
=E8ES
-----END PGP SIGNATURE-----