> > 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 <[EMAIL PROTECTED]> (I read email only on weekends) _______________________________________________ Python-il mailing list [email protected] http://hamakor.org.il/cgi-bin/mailman/listinfo/python-il
