LINKED LISTS?

[Moshe Zadka]

On Sat, 13 May 2000, Courageous wrote:

> Okay, I downloaded the python source, as I had to know how
> lists were implemented in python. Does nobody care that
> pushing onto a so-called python "stack" is actually O(n)?
> Am I the only person who cares about O(1) versus 0(n)?

Practically, it's darned close to O(1) for allocations. If you have
multi-million element lists, and the difference start to annoy you, you
are free to write a new data type.
Most lists are <10,000, so optimizaing something for that case is more
beneficial.

> I don't get it. The code for python lists is, as plain as
> the nose on the end of my face, a resizeable vector
> implementation.

With some overallocation tricks, to prevent re-copying all the time.

> Which is all well and good, but where
> are the linked lists for those of us who want insert,
> delete, and append to be O(1)?

Ummmm....insert, delete and append to be O(1) is a deque, not a list. 
For plain lists, here is code:

define cons(car, cdr):
	return car, cdr

define car(cons):
	return cons[0]

define cdr(cons):
	return cons[1]

Writing a deque could be done with hand-written overallocating a list in
Python (if you weaken the reqs. to amortized O(1) instead of O(1)). It's 
a cute little exercise. 

if-the-names-seem-weird-study-scheme-grasshoper-ly y'rs, Z.
--
Moshe Zadka <moshez at math.huji.ac.il>
http://www.oreilly.com/news/prescod_0300.html
http://www.linux.org.il -- we put the penguin in .com