Questions on Using Python to Teach Data Structures and Algorithms

Marc 'BlackJack' Rintsch bj_666 at
Thu Sep 28 04:31:19 CEST 2006

In <451b2c0b at>, efrat wrote:

> 1. What exactly is a Python list? If one writes a[n], then is the 
> complexity Theta(n)? If this is O(1), then why was the name "list" 
> chosen?

Why not?  It has all the methods one expect from an abstract data type
"list".  It's not the O() behavior but the interface that defines abstract
data types.  If it's a (double) linked list or a dynamical array under the
hood is an implementation detail.

	Marc 'BlackJack' Rintsch

More information about the Python-list mailing list