WEEK14: linked lists...deleteTail() and comparison with python lists
---------------------------------------------------------------
M: deleteTail method
REVIEW of QUIZ 6
LINKED-LISTS
- 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!
# start at head
curr = self.head
# 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.head = None
self.size = 0
return val
else:
val = self.tail.getData()
# set pointer to tail - 1 node
curr = self.head
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
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
summary:
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()
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