WEEK14: linked lists...comparison with python lists
 M: compare to python lists



 - now that we have a working linked-list class, let's
   go back and compare this to python's list implementation

 - note: something that depends on the size of the list (N), like
   the time needed to do a linear search, is called order(N)
   or O(N).  If N doubles, the time for a linear search doubles.

   some operation that does *not* depend on the size of the list
   is called order(1), O(1), or constant time. If the size of
   the list doubles, this operation still takes the same amount
   of time as it did when the list size was smaller.

 - how does the append operation compare for both python lists
   and our linked list?

   python list: put item in next memory location
   linked-list: add node and reset tail

   neither one of these depends on the size of the list, so
   they are both O(1) (unless, for the python list, the next memory
   location is already used. This might mean we have to copy the
   whole list to a new area of free memory that has enough space.
   Copying the whole list would obviously depend on the size of
   the list, which would make it an O(N) operation)

 - how about indexing??

   remember, for arrays or lists, most languages store them in 
   consecutive memory locations. If I have a python list of names
   like this: L = ["jeff", "lisa", "rich", "adam"], those strings
   might be stored in consecutive locations like 13, 14, 15, 16:

  computer memory
  |1     |2     |3     |4     |5     |6     |7     |8     |and so on...
  |      |      |      |      |      |      |      |      |
  |11    |12    |13    |14    |15    |16    |17    |18    |
  |      |      |jeff  |lisa  |rich  |adam  |      |      |
  |21    |22    |23    |24    |25    |26    |27    |28    |
  |      |      |      |      |      |      |      |      |
  |31    |32    |33    |34    |35    |36    |37    |38    |
  |      |      |      |      |      |      |      |      |

     python list: easy to find ith data item stored in memory using simple
     calculation...base memory location + i*offset (for the above
     simplified example, calculating where L[3] is stored would
     just be 13 + 3, since 13 is the base address of the list)

   linked-list: need to traverse list to find ith node

   so here the python list wins, since it's a simple calculation to
   find the position of the ith node. It doesn't matter how large the
   list is, it's still easy to calculate where the ith item in the 
   list is stored in memory

   the linked-list needs to traverse the list one node at a time until
   we get to the ith node. If N is very large, this will take a long time.
   For the linked-list, indexing is an order(N) operation.

 - what about memory usage??

   python lists need consecutive slots in memory to hold all list values.
   this could be a problem if the list is large or the computer doesn't
   have large chunks of unused memory available

   the linked list just puts nodes wherever there is free memory and links
   the nodes together into a list, so this might be a win for linked-lists

 - what about adding a node to the middle of the list:

   python list: must move all following items down one slot
   linked-list: must find correct spot, then reset links to add new node

   both of these are O(N) operations. For the python list, moving all
   following items down one slot clearly depends on N (a larger N means
   more items to move down). For the linked-list, finding the correct
   spot to insert the node also depends on N


               python list              linked-list
               -----------              -----------

append         O(1) if space available  O(1)

add to middle  O(N)                     O(N)

delete tail    O(1)                     O(N) (needs to find tail - 1 node)

memory usage   might be hard to         easy to put nodes wherever
               find enough consecutive  there is free space
               free memory. could also
               be tricky if list grows
               in size

indexing       O(1)                     O(N)

 - what does the following program do, why do the results for 
   insert(0,x) take longer than append(), and why do they seem to
   increase linearly with N?

$ cat listops.py 

from random import randrange
from time import time

N = input("N: ")

L = range(N)
t1 = time()
t2 = time()
apptime = t2 - t1
print "    append(x) time = %0.7f" % (apptime)

L = range(N)
t1 = time()
t2 = time()
instime = t2 - t1
print "  insert(0,x) time = %0.7f" % (instime)

$ python listops.py 
N: 1000000
    append(x) time = 0.0000849
  insert(0,x) time = 0.0016949

$ python listops.py 
N: 2000000
    append(x) time = 0.0001290
  insert(0,x) time = 0.0038590