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