CSC148H lab -- week 11

These are the instructions for the week 11 CSC148H lab. To earn your lab mark, you must actively participate in the lab. As always, you will work as a pair, taking turns being the driver and the navigator. The driver types, and the navigator watches for mistakes, thinking ahead. At the end of each exercise, show your TA what you've done, and then switch roles.

This week's exercises are on the topic of linked lists. Draw pictures like you saw during lecture: they're a huge help. Ask your TA for help if you're not sure how to do this.

Exercise 1: Linked List Deque

Begin by downloading the file ll.py, the implementation of linked lists from class. The file contains a queue class implemented using a linked list so that enqueue and dequeue are both O(1) operations. The goal of this exercise is to implement a deque ADT using linked lists. A deque (double-ended queue) supports the following operations; it's essentially a hybrid stack and queue:

add_front (item)
remove_front (item)
add_back (item)
remove_back (item)

Note how the deque allows items to be added or removed from both ends of the sequence. All of your operations should be O(1) except for remove_back which is allowed to be O(n). You are allowed to modify the linked list implementation in order to facilitate your deque code.

Add your deque implementation to ll.py.



Exercise 2: removing from the end

Once you're finished exercise 1, think about why it is difficult to implement remove_back in O(1) time. Brainstorm some possible solutions to the problem. Hint: what if nodes had previous pointers in addition to next pointers.

Once you understand the difficulty and its possible solutions, sketch the approach you would take to remove the last element of a linked list. Do not implement the method; just describe its operation using some sample lists and show your TA.

Exercise 3: Detecting and breaking cycles in a linked list
A properly constructed linked list should not contain any cycles. That
is, there should be no node in the list whose next reference points to
an item earlier in the list. 



Suppose you are given a list and told that it may have a cycle. Write
an iterative function that breaks the cycle:




  def break_cycle(llist): breaks a cycle in the
LinkedList llist if it exists.