```
WEEK14: linked lists...deleteTail() and comparison with python lists
---------------------------------------------------------------
M: deleteTail method

REVIEW of QUIZ 6

- deleteTail algorithm:

> handle special cases (self.size = 0 or 1)
> for non-special cases:
get and save tail node value
find tail-1th node (node just before the tail node)
set tail-1th node next to None
set tail to point to tail-1th node
return value saved above

- so how do we get the tail-1th node from the linked-list???

- we have to start at the head node and move through the
list until we get to the tail-1th node

- it helps to have a specific example in mind...suppose
we have a 5-node list:

---    ---    ---    ---    ---
head--| |----| |----| |----| |----| | --- tail
---    ---    ---    ---    ---
^
want
this
node!

# move down 3 (for 5-node linked list)
for i in range(self.size-2):
curr = curr.getNext()
# now use curr, as it points to tail-1th node
curr.setNext(None)
self.tail = curr

- here's the full code for deleteTail():

def deleteTail(self):
if self.size == 0:
return None
elif self.size == 1:
val = self.tail.getData()
self.tail = None
self.size = 0
return val
else:
val = self.tail.getData()
# set pointer to tail - 1 node
for i in range(self.size - 2):
curr = curr.getNext()
# set tail - 1 node next = None
curr.setNext(None)
# reset self.tail to point to tail - 1 node
self.tail = curr
self.size = self.size - 1
return val

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

```