Lulu of the Lotus-Eaters mertz at gnosis.cx
Wed Aug 8 07:04:08 CEST 2001

```|You can't? It's clear enough. The average person doesn't dump thousands
|of items into a link list. That's what it takes in order for Python to "see" the
|O(1) complexity benefits that linked lists offer.

My admiration of Python lists has increased even futher today.  Like
most naive programmers (naive still after a couple decades of
programming), I figured that Python lists couldn't possibly be a very
good data structure if "insert in the middle" is a common operation.
After all, one has to copy all the tail elements over a position for
every insert, which makes the insertion O(N).  A linked list can save
all the copy operations.

With that in mind, I tried a little test:

--------------
import time, sys

if __name__ == '__main__':
LOOPS = int(sys.argv[1])
start = time.time()
lst = []
for i in xrange(LOOPS):
mid = i/2
lst = lst[:mid] + [None] + lst[mid:]
end = time.time()
print "%d Python concatenations in %5.2f seconds" % (LOOPS, end-start)

start = time.time()
lst = []
for i in xrange(LOOPS):
mid = i/2
new = lst[:mid]
new.append(None)
new.extend(lst[mid:])
lst = new
end = time.time()
print "%d Python List inserts in %5.2f seconds" % (LOOPS, end-start)

start = time.time()
for i in xrange(LOOPS):
mid = i/2
lst[mid] = None
end = time.time()
print "%d LinkedList inserts in %5.2f seconds" % (LOOPS, end-start)
--------------

The first two loops are basically the same, and just use Python lists and
slices in some obvious ways.  The first approach seemed like the "obvious" way
to do it, but it turns out to be noticably worse than the second way.  But how
much worse seems close to a constant multiple, or maybe a very low complexity
order difference.

The third loop does absolutely terrible for the test case.  The problem, of
course, is that insertion is O(1), but walking to the correct position for
insertion is still O(N).  Of course, if finding the insertion position is
cheap, so is the overall loop.  For example, substituting 'mid=0' or 'mid=i' in
the above loops has little effect on the first two loops, but makes the

With that, my quick LinkedList code.  It is pure Python, which is most of what
makes it very slow.  But the overall complexity issues would apply to an
extension module.  If there is anything I am missing in making my class
efficient, I would not be surprised, and would be interested to learn it.
Obviously, only a few of the interesting methods are implemented (__getslice__
and others would be worth adding if the class was worth having in the first
place).

--------------
def __init__(self, *items):
self.pos = 0
for item in items:
self.current.extend([item,[]])
self.current = self.current[1]

def next(self):
self.pos += 1
self.current = self.current[1]
self.val = self.current[0]
return self.val

def start(self):
self.pos = 0

def __getitem__(self, index):
if self.pos > index:
self.pos = 0
for i in xrange(self.pos, index):
self.next()
return self.val

def __setitem__(self, index, val):
self.__getitem__(index)
self.current[1] = self.current[:]
self.current[0] = val
self.pos += 1
--------------

Yours, Lulu...

```