15-121 SPRING 2010 [CORTINA]

LAB 4

image by Una Woodruff

In this lab, you will implement methods for a circularly singly-linked list. In this type of list, there is one reference to the head of the list. The last node of the list has a next reference that points back to the head of the list.

EXERCISES

Download the CircularlyLinkedList.zip project file. This project contains a CircularlyLinkedList class that will model a circular singly-linked list as shown above. The constructor is given for you, creating an empty circular list. There is also a private inner class to represent a node in the list.

The project also includes a class ListTester that tests the methods that you will write. Read this file over quickly to see what tests are performed and determine what the expected output should be for each set of instructions.

In the CircularlyLinkedList class, complete the add method that inserts the new entry into the circular list. Insert the new entry into the list so that the insert operation is always O(1), regardless of the length of the list.
- Look at the picture above and ask yourself, if you were to insert a node in constant time, where is the only place you can do this?
- Think about special cases. What if the list is empty? What if the list has only one element? Do you need extra code for each case?
In the CircularlyLinkedList class, complete the display method that displays the contents of the entire list starting from the given index. (The head of the list is at index 0.) If the index is greater than or equal to the number of entries in the list, this is now valid since you can just wrap around back to the head and continue counting until you get to the correct starting node. If the index is negative, then display a simple error message only.
- Try to implement your method so you only traverse the list at most twice, regardless of the size of the given index.

HANDIN

If you worked with another student, put both of your names in a comment at the beginning of your program. At the end of lab, create a zip file of your program and submit it to the handin server http://handin.intro.cs.cmu.edu/v1. (If you worked together, you only have to submit one program.)

FUTURE WORK: FUN STUFF FOR LATER

Implement the remove method so that it runs in constant time. Which node must you remove to get a constant time operation? Are there special cases?

Modify the add method so it adds the entry into the circular list so that all entries are in increasing order, without duplicates. (Note: you'll need to change the type of the list to be <E extends Comparable<E>>.)

Modify the circular list and tester to solve the Josephus Problem described in the first edition of the textbook on page 254 (#5).