[Python-il] The Tuples and Lists question

[Beni Cherniavsky]

> > On Wed, 2008-06-11 at 16:00 +0300, Rani Hod wrote:
> > > Why do other languages have arrays and linked lists as different types
> > > of sequences?
> > > "The only difference" is that linked lists are easy to modify and
> > > arrays admit random access to elements.
> > > These are two distinct data structures with different operation
> > > complexity.

Before terrible confusion ensues, I'd like to stress that Python's
"list"s *are not linked lists*!
They are resizable arrays (known in some languages as "vector"s).
Random access is O(1).  Naturally, they use over-allocation so that
amortized append is also O(1).

It so happened in the history of programming languages that all early
dynamic languages chose linked lists as their primary data structure
and the word "list" has become nearly synonymous with linked lists.
But all modern dynamic languages (at least imperative ones) have moved
away from linked lists and use resizable arrays as the main data
structure for sequences.  They give better performance for typical use
cases and are simpler to use correctly.

-- 
Beni Cherniavsky <cben at users.sf.net> (I read email only on weekends)