Recursively traverse linked list -- help!

[Oivvio Polite]

> 
> That's a misconception.  One of the main reasons for using linked
> lists is to be able to insert stuff in the middle taking a constant
> amount of time.  If you do that with a built-in list, the time needed
> is proportional to the size of the list, which can be very large.
> -- 
> http://mail.python.org/mailman/listinfo/python-list
> 

Sure, granted that you keep track of the middle link of your list, so
that you don't have to traverse up to that point. But even if keep track
of it you'll have to be doing pretty large lists before the linked list
will outperform the builtin list.



-----------
program
import time
class LinkedList:

    def __init__(self):
        self.start = None

    def append(self, value = None):
        new = ListElement(value)
        if self.start:
            new.next = self.start
        self.start = new


    
    def insert(self, position, value):
        new = ListElement(value)
        
        if self.start:
            i = 0
            current = self.start
            while current and position > i:
                i += 1
                current = current.next
            new.next = current.next
            current.next = new
        else:
            self.start = new

        
    def pop(self):
        result = None
        if self.start:
            result = self.start.data
            self.start = self.start.next
        return result
    
    def __str__(self):
        result = ""
        current = self.start
        while current:
            result += "%s " % (str(current))
            current = current.next
        return result

class ListElement:
    def __init__(self, value = None):
        self.data = value
        self.next = None

    def __str__(self):
        return str(self.data)


def do_many_inserts(list, count1, count2):
    length = 0
    for j in range(count1):
        t1 = time.time()
        for i in range(count2):
            list.insert(length / 2, i)
            length += 1

        print time.time() - t1
    
def do_many_pushes(list, count1, count2):    
    for j in range(count1):
        t1 = time.time()
        for i in range(count2):
            list.append(i)
        print time.time() - t1

    
if __name__ == '__main__':


    print "inserts at start of LinkedList"
    do_many_pushes(LinkedList(), 10, 20000)
    print
    
    print "inserts at start of builtin list"
    do_many_pushes([], 10, 20000)
    print
    
    print "inserts in middle of LinkedList"
    do_many_inserts(LinkedList(), 10,200)
    print

    print "inserts in middle of builtin list"
    do_many_inserts([], 10,200)
    

-----------
output
python2.2 /tmp/linked.py
inserts at start of LinkedList
1.11887598038
1.11088299751
1.35213696957
1.5195029974
1.95533299446
1.17704892159
1.64089500904
1.10084593296
1.29115998745
1.82064199448

inserts at start of builtin list
0.14047896862
0.140606999397
0.145263075829
0.133972048759
0.206911921501
0.145354986191
0.132588028908
0.147331953049
0.141435980797
0.138702988625

inserts in middle of LinkedList
0.235688090324
0.61442399025
0.989964962006
1.43489098549
1.76089990139
2.27561497688
2.53811192513
3.29149603844
3.56963992119
3.98600196838

inserts in middle of builtin list
0.00191104412079
0.00234496593475
0.0030529499054
0.00247895717621
0.00264799594879
0.00436305999756
0.00301098823547
0.00318598747253
0.00469303131104
0.00358402729034
-----------

-- 
oivvio polite

cell +46 (0)709 30 40 30 / phone +46 (0)8 669 64 18 / fax +46 (0)8 84 00
18
varvsgatan 10A / s-117 29 stockholm / sweden