Week 13, Friday: Linked Lists

• Quiz 6

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:

1. save the item from the current head node
2. find what will eventually be the new head node
3. cut the link from the current head to the new head
4. reset the head to be the new head node
5. decrease the size of the list by one
6. 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?