Programming Assignment #3: Deque

Introduction

One weakness of the built-in Python list class is that insertions and deletions at the beginning of the list are much less efficient than modifications at the end. This makes Python lists inappropriate for applications that require frequent modifications at both ends of a sequence. The double-ended queue, or deque, is sequence type that supports O(1) append and pop operations at either end of a sequence.

The objective of this assignment is to implement a deque type using a doubly-linked list as the underlying data structure. The functionality of our Deque class will be almost the same as the functionality of the deque class included in the collections module of the Python standard library.

The Deque ADT

Refer to the documentation of Python's deque class for a detailed description of the Deque ADT.

You should use the following file as a starting point:

deque.py

Some methods in that file are already completed, and other methods include tips on implementation. Each method should be completed so that the functionality is consistent with with Python's deque type. Note that not all methods of Python's deque type are included in this file. You only need to complete the included methods.

Efficiency

All of the operations of the Deque class should be O(1) or O(n) in the worst case. You will lose points if your implementation of an operation is in a slower-than-optimal complexity class. For example d[-1] should require O(1) steps, not O(n) steps.

That said, you should focus on writing clear, concise, maintainable code. Don't make your code more complicated than necessary for small (constant factor) gains in efficiency.

Testing

Part of your grade for this assignment will be based on developing unit tests for your code. More information coming soon.

Handing In

You should submit two .py files through blackboard before the deadline: a module named deque.py containing your completed Deque class, and an updated version of the unit testing module. As always, your code should conform to the CS240 Python Coding Conventions. You do not need to provide docstrings for the methods in the unit testing class.