Week 14, Friday: Linked Lists, Last Class!!

questions about final exam?
class survey

the `deleteHead()` method

Last time we created methods to add nodes to the list. Today we want to write methods to delete nodes from the list. We will write two methods: deleteHead() and deleteTail(), the opposites of prepend and append. Later we will write methods to add and delete nodes from anywhere in the list.

Typically, when deleting a node or item from a list, we want to do something with that item. So for all delete methods, we want to return the item that is stored in the node we are deleting.

To delete the head node, we need to do these six steps:

save the item from the current head node
find what will eventually be the new head node
cut the link from the current head to the new head
reset the head to be the new head node
decrease the size of the list by one
return the item we saved in step 2

However, if there are 1 or fewer nodes in the list, we will have to take care of those special cases:

return None if there were zero nodes in the list (i.e., no nodes to delete)
set both head and tail to None if there was only one node in the list (which we just deleted)

See if you can write the deleteHead() method. Make sure you add lots of test code. Here is how we would like it to work:

LL = LinkedList()
LL.append("A")
LL.append("B")
LL.append("C")
item = LL.deleteHead()
assert item == "A"
assert len(LL) == 2
item = LL.deleteHead()
assert item == "B"
assert len(LL) == 1
item = LL.deleteHead()
assert item == "C"
assert len(LL) == 0
item = LL.deleteHead()
assert item == "None"
assert len(LL) == 0

If you are having trouble getting your method to work, try drawing the linked list on paper and working through your code by hand. Make sure you understand what is happening at each step.

the `deleteTail()` method

Deleting the tail node is very similar to deleting the head node. However, the second step above, finding what will be the new tail node, requires a list traversal. For example, if we have 5 nodes in a list, and we want to delete the tail node, the new tail will be the 4th node in the current list. And to get to the 4th node, we could do something like this:

newtail = self.head                # start at head
for i in range(self.size - 2):     # move over 3 times
  newtail = newtail.getNext()

Once you have what will be the new tail node, the rest is very similar to the deleteHead method. This includes the special cases when the size of the list is zero or one.

See if you can add the deleteTail method to your linked list class. Make sure you test it thoroughly!

LL = LinkedList()
LL.append("A")
LL.append("B")
LL.append("C")
item = LL.deleteTail()
assert item == "C"
assert len(LL) == 2
item = LL.deleteTail()
assert item == "B"
assert len(LL) == 1
item = LL.deleteTail()
assert item == "A"
assert len(LL) == 0
item = LL.deleteTail()
assert item == "None"
assert len(LL) == 0

analysis

Note, to delete the tail node, we need to find the node before the current tail node, which requires a list traversal. If the list is longer, the list traversal will take longer (more steps!). That makes deleteTail() an O(N) algorithm (where N is the number of nodes/items in the list). Is L.pop() also an O(N) algorithm?

Summary...Linked Lists vs Python lists

Now that we have a working LinkedList class, what are some of the pros and cons of linked lists vs python lists?

Remember, here is a picture of how each is stored/implemented in the computer's memory:

computer memory

append

To add an item to the end of a python list, we need to find the correct spot in memory (python does this for us). Since this is just a simple calculation (base address + len(L)), appending to a python list is an O(1) operation. That is, it doesn't matter how long the list is (assuming there is available free memory at the end of the list).

The same is true for a linked list: adding a node to the end of the list is O(1), since it doesn't depend on the size of the list. There are only a few steps required: create new node, connect it to the tail, reset the tail, increment the size.

So for appending to the list, both are the same.

prepend

To add an item to the beginning of a python list, if we want to preserve the current base address, requires moving all other items in the list over by one slot. This clearly depends on the size of the list, making it an O(N) operation.

You can see this by running some simple tests using append(item) and insert(0,item):

$ cat testpythonlists.py 
"""
test/time various python list operations
"""

from time import time

# ------------------------------------------------ #

def main():

  N = int(raw_input("N: "))

  L = []
  t1 = time()
  for i in range(N):
    L.append(i)
  t2 = time()
  total = t2 - t1
  print("append time:  %6.3f  (for L of size %d)" % (total, len(L)))

  L = []
  t1 = time()
  for i in range(N):
    L.insert(0, i)
  t2 = time()
  total = t2 - t1
  print("insert@0 time:  %6.3f  (for L of size %d)" % (total, len(L)))

# ------------------------------------------------ #

main()

Here's a simple run of the above program. Notice the difference between adding to the end and adding to the beginning of a python list:

$ python testpythonlists.py 
N: 100000
append time:   0.015  (for L of size 100000)
insert@0 time:   2.573  (for L of size 100000)

$ python testpythonlists.py 
N: 200000 
append time:   0.021  (for L of size 200000)
insert@0 time:  10.259  (for L of size 200000)

For the linked list, again, just a few steps needed to add a node to the beginning of a list: create node, connect it to the current head, reset the head, increase the size. This is clearly an O(1) operation, so the linked list does better here.

indexing

How about for indexing, or finding the ith item in a list? For the python list, that is an O(1) operation, since it is just a simple calculation to find the correct memory location (base address + i). For the linked list, to get to the ith node, we need to start at the head of the list and move over i times. This is an O(N) operation, so the python list does better at indexing (which we've used a lot this semester!).

summary

See if you can figure out whether each method we have written (e.g., deleteHead(), __str__(), deleteTail(), etc) is O(1), O(N), or something else. And compare that to the python list.