Part 1: Augmenting a DoublyLinkedList In this assignment you will add some more
ID: 3800572 • Letter: P
Question
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
Explanation / Answer
;import java.util.NoSuchElementException;
public class DoublyLinkedListImpl {
private Node head;
private Node tail;
private int size;
public DoublyLinkedListImpl() {
size = 0;
}
private class Node {
E element;
Node next;
Node prev;
public Node(E element, Node next, Node prev) {
this.element = element;
this.next = next;
this.prev = prev;
}
}
public int size() { return size; }
/**
* return whether the list is empty or not
* @return
*/
public boolean isEmpty() { return size == 0; }
/**
* adds element at the starting of the linked list
* @param element
*/
public void addFirst(E element) {
Node tmp = new Node(element, head, null);
if(head != null ) {head.prev = tmp;}
head = tmp;
if(tail == null) { tail = tmp;}
size++;
System.out.println("adding: "+element);
}
/**
* adds element at the end of the linked list
* @param element
*/
public void addLast(E element) {
Node tmp = new Node(element, null, tail);
if(tail != null) {tail.next = tmp;}
tail = tmp;
if(head == null) { head = tmp;}
size++;
System.out.println("adding: "+element);
}
/**
* this method walks forward through the linked list
*/
public void iterateForward(){
System.out.println("iterating forward..");
Node tmp = head;
while(tmp != null){
System.out.println(tmp.element);
tmp = tmp.next;
}
}
/**
* this method walks backward through the linked list
*/
public void iterateBackward(){
System.out.println("iterating backword..");
Node tmp = tail;
while(tmp != null){
System.out.println(tmp.element);
tmp = tmp.prev;
}
}
/**
* this method removes element from the start of the linked list
* @return
*/
public E removeFirst() {
if (size == 0) throw new NoSuchElementException();
Node tmp = head;
head = head.next;
head.prev = null;
size--;
System.out.println("deleted: "+tmp.element);
return tmp.element;
}
/**
* this method removes element from the end of the linked list
* @return
*/
public E removeLast() {
if (size == 0) throw new NoSuchElementException();
Node tmp = tail;
tail = tail.prev;
tail.next = null;
size--;
System.out.println("deleted: "+tmp.element);
return tmp.element;
}
public static void main(String a[]){
DoublyLinkedListImpl<Integer> dll = new DoublyLinkedListImpl<Integer>();
dll.addFirst(10);
dll.addFirst(34);
dll.addLast(56);
dll.addLast(364);
dll.iterateForward();
dll.removeFirst();
dll.removeLast();
dll.iterateBackward();
}
}