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

REVIEW of QUIZ 6

COMPARE PYTHON LISTS vs our LINKED-LIST class:

- 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

python list: put item in next memory location

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)

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.

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

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

summary:

-----------              -----------

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

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()
L.append(randrange(100))
t2 = time()
apptime = t2 - t1
print "    append(x) time = %0.7f" % (apptime)

L = range(N)
t1 = time()
L.insert(0,randrange(100))
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

```