Programming project 6

Download the archive pp6.zip. It contains all the files for this project.

Part 1: Doubly-Linked List

In this project, you should add several interesting methods to the doubly-linked list that we developed for our Josephus program in the lecture.

Your task is to implement the following methods of the DoublyLinkedList class. All of them must run in \(O(n)\) time:

• find_first(x) returns the first node containing an element equal to x, or None if there is no such node;
• find_last(x) returns the last node containing an element equal to x, or None if there is no such node;
• count(x) returns the number of elements equal to x in the list;
• remove_first(x) removes the first node containing an element equal to x (and does nothing if there is no such node);
• remove_last(x) removes the last node containing an element equal to x (and does nothing if there is no such node);
• remove_all(x) removes all nodes containing elements equal to x from the list;

Finally, implement the method takeout(n, m). It removes the part of the list from node n up to node m from the list, and returns it as a new DoublyLinkedList object. The operation must run in constant time (\(O(1)\) time), no matter how long the piece being removed is. Do not create any new nodes - you just use the nodes of the original list for the new list.

You can use the client script client.py to perform a number of operations on DoublyLinkedList objects. It will also show you what the expected result is in each case.

Use the unit tests in test_doublylinked.py for more stringent testing of your implementation.

Submission: Upload your file doublylinked.py to the submission server.

Part 2: Circular List

In the Josephus program discussed in the class, we used a doubly-linked list to store the circle of participants.

Your task is to implement a circular linked list to simplify the implementation of the Josephus program.

In a circular list, the prev field of the first list node refers to the last list node, and the next field of the last list node refers to the first list node. (What does this mean when there is only one list node?)

There is no need for sentinels in a circular list. To simplify the design, we do not allow empty circular lists, so the constructor of the CircularList class takes an element argument and creates a circular list with one node.

Your task is to complete the implementation of the following methods:

• CircularList(el) constructs a circular list with one element;
• first() returns some node of the circular list. This must always be the node containing the element given in the list constructor if that node has not yet been deleted;
• string conversion returns a string with the contents of the list in the format [A, B, C] (with one space between list elements);
• remove(p) removes the given node from the list (but raises a ValueError if this is the only node of the list);
• insert(p, el) inserts element el in front of node p;
• append(el) appends element el at the end of the circular list (this is the same as insert(first(), el);
• __len__() returns the number of elements.

Note that there is no prepend function, since for circular lists prepend and append are the same operation.

The script josephus2.py uses the CircularList class instead of the DoublyLinkedList class. Check that it returns the same results as josephus1.py from our lecture!

You can use the unit tests test_circular.py to test your implementations. Note that you must get string conversion working for the tests to work at all!

Submission: Upload your file circular.py to the submission server.