Part 1: Augmenting a DoublyLinkedList In this assignment you will add some more features to a doubly linked list. You will provide a class called DoublyLinkedList in a file called doublylinkedlist.py . If you want to start from the provided DonsDoublyLinkedList class, be sure to put the new methods in a class that extends that one. Don't copy the methods into your class. Your DoublyLinkedList class should implement the Deque ADT (recall that a deque is a doubly-ended queue). The Deque ADT addfirst(item) - add item to the front of the deque. addlast(item) - add item to the end of the deque. removefirst(item) - remove and return the first item in the deque. removelast(item) - remove and return the last item in the deque. __len__ - return the number of items in the deque. Your DoublyLinkedList class should support the following operations: insert(index, item) - adds item to the list at the the given index . remove(item) - removes the first occurrence of item from the list. Raise a ValueError if the item is not present. __getitem__(index) - returns the item with the given index in the list. __contains__(item) - returns true if there is an item of the list equal to item . __iter__ - returns an iterator over the list that yields the items in order starting from the beginning. __reversed__ - returns an iterator over the list that yields the items in reverse order starting from the end. Part 2: Implementing a SortedList In this part of the assignment, you will implement a class called LinkedSortedList in a file called linkedsortedlist.py . It should use your DoublyLinkedList class to implement the Sorted List ADT below. The Sorted List ADT add(item) - adds item to the sorted list. remove(item) - removes the first occurrence of item from the sorted list. Raise a ValueError if the item is not present. __getitem__(index) - returns the item with the given index in the sorted list. This is also known as selection. __contains__(item) - returns true if there is an item of the sorted list equal to item . __iter__ - returns an iterator over the sorted list that yields the items in sorted order. __len__ - returns the length of the sorted list. Implementing your own Iterators In this assignment, you will implement some methods on a doubly-linked list class in order to make it easier to use some common patterns including the ability to access items by their list index, check if the list contains a particular item, and iterate over the list. You may use your own doubly-linked list class or work with the provided DonsDoublyLinkedList class. If you use the provided code, do not include it in your doublylinkedlist.py file. Duck Typing In object-oriented programming, inheritance is used to model "is a" relationships between classes. In python, there is another, sometimes simpler, way to do this. It's called Duck Typing. If an object walks like a duck and talks like a duck, then it is a duck.

class FakeDuck: def walklikeaduck(self): pass def talklikeaduck(self): pass class DutchHookbill: def walklikeaduck(self): pass def talklikeaduck(self): pass

So, in the example above, we would say that instances of both classes "are ducks". We don't have to have a superclass called Duck that both classes extend (this would be required in some other object-oriented languages). We exploited this duck typing previously when we wrote our test code for the Queue ADT. We could run the same tests on different implementations of the Queue as long as they implemented the ADT methods ( enqueue , dequeue , and __len__ ). This means, that any class that has certain methods can be treated alike. This works in python because when we call a method on an object, it looks at the type of that object to figure out which method to call. In this assignment, you will make doubly-linked list class that behaves more like a python list. Specifically, it will behave like a sequential collection, by implementing some methods. You may use your own doubly-linked list or start from the provided one. Index access: __getitem__ Implement __getitem__ on the DoublyLinkedList class. This method takes a parameter which will be an index. Once implemented, the following code should work.

L = DoublyLinkedList() L.addlast(100) L.addlast(200) assert(L[0] == 100) assert(L[1] == 200)

Iterators and Iterables We have already seen that it is very easy to iterate over a collection in python. For example, if L is a list, we can write the following to print the items in L .

for item in L: print(item)

Syntax is exactly the same to iterate over the other standard collection classes.

for key in {1: 'one', 2: 'two'}: print(key) for character in 'This is a string': print(character) for element in {'a', 'set', 'of', 'strings'}: print(element)

We can iterate this way over a collection if it is iterable. In python, being iterable means implementing a magic method called __iter__ that returns an object called an iterator. Before, we explain what the iterator is, let's see one in action. As we have seen that a list is iterable, we can get an iterator for the list by calling this magic method. Like some other magic methods, such as __len__ , we call __iter__ "from the outside" (like a regular function instead of a method) as follows.

L = [1,2,3] myiterator = iter(L) print(next(myiterator)) print(next(myiterator)) print(next(myiterator)) print(next(myiterator))

Try running this little bit of code. It raises a StopIteration error, but first it prints 1 , 2 , and 3 . The most important thing about an iterator is that we can call the next function in order to return the next item in the collection. When there are none left, it raises the StopIteration exception. Just using this understanding, we could reimplement the for loop style of iterating through the list as follows.

myiterator = iter(L) while True: try: item = next(myiterator) except StopIteration: break print(item)

This code is more cumbersome, but it makes clear what is actually happening when you write for item in L .

First, an iterator object is instantiated. Then the code loops, updating the loop variable by calling next on the iterator, and break ing out of the loop if the StopIteration error is raised. As you might have guessed, the next function calls a magic method called __next__ on the iterator object. The only other requirement is that an iterator must be iterable. That means it needs to implement __iter__ . Often, this will just return the iterator itself. Here is an example where this could make sense.

myiterator = iter(L) maximum = next(iter) for number in myiterator: if number > maximum: maximum = number

Remember that for can also be used in comprehensions and generator expressions (see PEP 289). So, we can write functions like the following.

def allbiggerthanfirst(L): iterator = iter(L) next(iterator) # Skip the first element return all(i > L[0] for i in iterator)

The all function returns true if all of the expressions are true. In this case, there is one expression for each item returned by the iterator. You could do it other ways of course. What makes an Iterable? What makes an Iterator? An Iterable implements __iter__ An Iterator implements __iter__ and __next__ If you write your own class implementing these methods, you can make your own iterator and iterable objects. Write a DoublyLinkedListIterator class that iterates over a DoublyLinkedList . It should be possible to choose whether you want to iterate forwards from the head or backwards from the tail. Make your DoublyLinkedList class Iterable.

class ListNode: def __init__(self, data, prev = None, link = None): self.data = data self.prev = prev self.link = link

class DonsDoublyLinkedList: def __init__(self): self._head = None self._tail = None self._length = 0

def _addtoempty(self, item): self._head = self._tail = ListNode(item, None, None) self._length = 1

def addfirst(self, item): if len(self) == 0: self._addtoempty(item) else: newnode = ListNode(item, None, self._head) self._head.prev = newnode self._head = newnode self._length += 1

def addlast(self, item): if len(self) == 0: self._addtoempty(item) else: newnode = ListNode(item, self._tail, None) self._tail.link = newnode self._tail = newnode self._length += 1

def clear(self): self._head = self._tail = None self._length = 0

def _removeonly(self): item = self._head.data self.clear() return item

def removefirst(self): if len(self) == 1: return self._removeonly() item = self._head.data self._head = self._head.link self._head.prev = None self._length -= 1 return item

def removelast(self): if len(self) == 1: return self._removeonly() item = self._tail.data self._tail = self._tail.prev self._tail.link = None self._length -= 1 return item

def concattostart(self, other): other._tail.link = self._head self._head.prev = other._tail self._head = other._head self._length += len(other) other.clear() # Don't allow the same nodes in 2 linked lists.

def concattoend(self, other): self._tail.link = other._head other._head.prev = self._tail self._tail = other._tail self._length += len(other) other.clear() # Don't allow the same nodes in 2 linked lists.

def __len__(self): return self._length