The purpose of this assignment is to make you familiar with implementing a data structure in Python in an object oriented way. During the lectures, you were presented pseudo code of different basic data structures. Now we expect you to implement one of these structures yourself.

To make it clear what is needed, we will provide you with two classes: **Node** and **DoublyLinkedList**. The first one is already implemented (you don't need to modify it), the second one consist only a structure of empty methods defined. Your task is to come up with an implementation of these methods.

*Note*: If a list is doubly linked, each node contains a reference to the *previous* node in the chain and a reference to the *next* node.

You are expected to implement every function in DoublyLinkedList. Including the *next()* function, which is used by an iterator object in python. The *map(func)* function applies a function to every element in the list.
All other functions are available in the slides/book.

The **Node** class implementation is already given:

In [1]:

```
class Node(object):
"""Doubly linked node which stores an object"""
def __init__(self, element, next_node=None, previous_node=None):
self.__element = element
self.__next_node = next_node
self.__previous_node = previous_node
def get_element(self):
"""Returns the element stored in this node"""
return self.__element
def get_previous(self):
"""Returns the previous linked node"""
return self.__previous_node
def get_next(self):
"""Returns the next linked node"""
return self.__next_node
def set_element(self, element):
"""Sets the element stored in this node"""
self.__element = element
def set_previous(self, previous_node):
"""Sets the previous linked node"""
self.__previous_node = previous_node
def set_next(self, next_node):
"""Sets the next linked node"""
self.__next_node = next_node
```

The following code snippet is a constructor provided by the **DoublyLinkedList** Python class for the creation of a new doubly linked list. **Extend the snippet below with your implementation of the DoublyLinkedList**.

In [2]:

```
class DoublyLinkedList(object):
"""Doubly linked node data structure"""
def __init__(self):
self.__size = 0
self.__header = Node('Header')
self.__trailer = Node('Trailer')
self.__header.set_next(self.__trailer)
self.__trailer.set_previous(self.__header)
self.__current = None
def __iter__(self):
self.__current = None
return self
def __next__(self):
"""Standard python iterator method"""
if self.is_empty() or self.__current == self.__trailer:
raise StopIteration()
elif self.__current is None:
self.__current = self.__header
self.__current = self.__current.get_next()
return self.__current
def map(self, function):
"""Run function on every element in the list"""
for node in self:
if node != self.__trailer and node != self.__header:
node.set_element(function(node.get_element()))
def size(self):
"""Returns the number of elements in the list"""
return self.__size
def is_empty(self):
"""Returns the number of elements in the list"""
return self.__size == 0
def get_first(self):
"""Get the first element of the list"""
if self.is_empty():
raise Exception("List is empty")
else:
return self.__header.get_next()
def get_last(self):
"""Get the last element of the list"""
if self.is_empty():
raise Exception("List is empty")
else:
return self.__trailer.get_previous()
def get_previous(self, node):
"""Returns the node before the given node"""
if node == self.__header:
raise Exception("Cannot get the element before the header of this list")
else:
return node.get_previous()
def get_next(self, node):
"""Returns the node after the given node"""
if node == self.__trailer:
raise Exception("Cannot get the element after the trailer of this list")
else:
return node.get_next()
def add_before(self, new, existing):
"""Insert the new before existing"""
previous_existing = self.get_previous(existing)
new.set_previous(previous_existing)
new.set_next(existing)
existing.set_previous(new)
previous_existing.set_next(new)
self.__size += 1
def add_after(self, new, existing):
"""Insert the new after existing"""
next_existing = self.get_next(existing)
new.set_previous(existing)
new.set_next(next_existing)
existing.set_next(new)
next_existing.set_previous(new)
self.__size += 1
def add_first(self, new):
"""Insert the node at the head of the list"""
self.add_after(new, self.__header)
def add_last(self, new):
"""Insert the node at the tail of the list"""
self.add_before(new, self.__trailer)
def remove(self, node):
"""Removes the given node from the list"""
before = self.get_previous(node)
after = self.get_next(node)
before.set_next(after)
after.set_previous(before)
node.set_next(None)
node.set_previous(None)
self.__size -= 1
```

**T1 (5 points)**: Using the constructor from the **DoublyLinkedList**, create a new doubly linked list of integers from 1 to 10.

In [3]:

```
doubleList = DoublyLinkedList();
for i in range(1, 11):
doubleList.add_last(Node(i))
for i in doubleList:
print(i.get_element())
```

The given **DoublyLinkedList** Python class
contains helpful methods for using a doubly linked list.
Answer the following questions while implementing
the methods of the **DoublyLinkedList** class.

**T2 (10 points)**: Implement the `size`

method that returns the size of a doubly linked list.

```
def size(self):
"""Returns the number of elements in the list."""
pass
```

In [ ]:

```
#Test your implementation here
```

**T3 (5 points)**: Implement the `is_empty`

method that checks
whether a doubly linked list is empty.

```
def is_empty(self):
"""Returns the number of elements in the list"""
pass
```

In [ ]:

```
#Test your implementation here
```

**T4 (10 points)**: Implement the methods `get_first`

and `get_last`

to get the first and the last element of the list, respectively.

*Hint*: Return an exception in case the list is empty.

```
def get_first(self):
"""Get the first element of the list"""
pass
def get_last(self):
"""Get the last element of the list"""
pass
```

In [ ]:

```
#Test your implementation here
```

**T5 (10 points)**: Implement the methods `get_previous`

and `get_next`

to get the previous and the next node of the list, respectively.

*Hint*: Return an exception in case the list is empty.

```
def get_previous(self, node):
"""Returns the node before the given node"""
pass
def get_next(self, node):
"""Returns the node after the given node"""
pass
```

In [ ]:

```
#Test your implementation here
```

**T6 (10 points)**: Implement the methods `add_before`

and `add_after`

to respectively insert new elements before and after a node of the list.

```
def add_before(self, new, existing):
"""Insert the new before existing"""
pass
def add_after(self, new, existing):
"""Insert the new after existing"""
pass
```

In [ ]:

```
#Test your implementation here
```

**T7 (10 points)**: Implement the methods `add_first`

and `add_first`

to respectively insert new nodes in the beginning and in the end of a list.

```
def add_first(self, new):
"""Insert the node at the head of the list"""
pass
def add_last(self, new):
"""Insert the node at the tail of the list"""
pass
```

In [ ]:

```
#Test your implementation here
```

**T8 (10 points)**: Implement the method `remove`

to remove
a node from a list.

```
def remove(self, node):
"""Removes the given node from the list"""
pass
```

In [ ]:

```
#Test your implementation here
```

**T9 (10 points)**: Implement the method `map`

to apply a function on
each element of a list.

```
def map(self, function):
"""Run function on every element in the list"""
pass
```

In [ ]:

```
#Test your implementation here
```

**T10 (10 points)**: Implement the method `next`

to iterate the elements
of a list.

```
"""Standard methods for Python iterator"""
def __iter__(self):
pass
def __next__(self):
pass
```

In [ ]:

```
#Test your implementation here
```

Answer the following questions by using the implemented methods from the Node and DoublyLinkedList classes. Apply your operations on the list you created in T1.

**T11 (5 points)**: Add 2 to each element of the list.

*Hint*: Use the method `map`

.

In [4]:

```
doubleList.map(lambda x: x+2)
for i in doubleList:
print(i.get_element())
```

**T12 (5 points)**: Multiply each element of the list by 5.

*Hint*: Use the method `map`

.

In [6]:

```
doubleList.map(lambda x: x*5)
for i in doubleList:
print(i.get_element())
```

**T13 (5 points)**: Remove elements that are multiplies of 4.

*Hint*: Use the methods `next`

and `remove`

.

In [12]:

```
current = doubleList.get_first();
while(current != doubleList.get_last().get_next()):
next = current.get_next();
if (current.get_element() % 4 == 0):
doubleList.remove(current);
current = next;
for i in doubleList:
print(i.get_element())
```

**T14 (5 points)**: Remove elements from the list that are odd numbers.

*Hint*: Use the methods `get_previous`

and `remove`

.

In [13]:

```
current = doubleList.get_first();
while(current != doubleList.get_last().get_next()):
next = current.get_next();
if (current.get_element() % 2 == 1):
doubleList.remove(current);
current = next;
for i in doubleList:
print(i.get_element())
```

**T15 (5 points)**: Prove when the complexity to delete a node in a doubly linked list is $O(1)$ and $O(n)$

The following questions ask from you to apply set operations on elements.
Keep in mind that you should not use the ready *Sets* library of Python. **Extend the snippet below with your implementation of the Set data structure**.

**T16 (5 points)**: Given a list $L = [a, b, c, ...]$ you can create a set, $S$, of elements.
Implement a set constructor.

In [15]:

```
class Set(object):
"""Set data structure"""
def __init__(self, list):
self.list = list()
for element in list:
if element not in self.list:
self.list.append(element)
```

**T17 (5 points)**: Given two lists $L1 = [a1, b1, c1, ...]$ and $L2 = [a2, b2, c2, ...]$,
implement a $union$ method that returns to a new set $S$.

In [ ]:

```
def union(list1, list2):
"""Union of sets."""
return Set(list1 + list2)
```

In [ ]:

```
#Test your implementation here
```

**T18 (5 points)**: Given two lists $L1 = [a1, b1, c1, ...]$ and $L2 = [a2, b2, c2, ...]$,
implement a $difference$ method that returns to a new set $S$.

In [ ]:

```
def difference(list1, list2):
"""Difference between sets."""
set_list = list()
for element in list1:
if element not in set_list and element not in list2:
set_list.append(element)
return Set(set_list)
```

In [ ]:

```
#Test your implementation here
```

**T19 (5 points)**: Given two lists $L1 = [a1, b1, c1, ...]$ and $L2 = [a2, b2, c2, ...]$,
implement a $intersection$ method that returns to a new set $S$.

In [ ]:

```
def intersection(list1, list2):
"""Intersection between sets."""
set_list = list()
for element in list1:
if element not in set_list and element in list2:
set_list.append(element)
return Set(set_list)
```

In [ ]:

```
#Test your implementation here
```

A dictionary is an abstract data type that represents a collection of (key, value) pairs. Given two lists of elements, such as the following, we can use a dictionary to reduce complexity of searching for a specific element in the data structure.

**T20 (10 points)**: Implement a dictionary as a collection of (key, value) pairs.

*Hint*: You should not use the *dict* from Python.

$Names = [``Max", ``David", ``Sophie", ``Anne", ... ]$

$Grades = [``10", ``7", ``8", ``10", ... ]$

In [17]:

```
class Dictionary(object):
"""Dictionary data structure"""
def __init__(self, keys, values):
self.pairs = list(zip(keys,values));
def get(self, key):
return [y for x,y in self.pairs if x == key][0]
def add(self, key, value):
old_value = [y for x,y in self.pairs if x == key]
if len(old_value) != 0:
self.pairs.remove((key, old_value[0]))
self.pairs.append((key,value))
```

In [ ]:

```
#Test your implementation here
```

**T21 (10 points)**: Implement the `add`

and the `get`

method. (Note: if an existing key is added again the corresponding value should be updated to the new value)

In [19]:

```
names = ["Max", "David", "Sophie", "Anne"];
grades = [10, 7, 8, 10];
dictionary = Dictionary(names, grades);
print(dictionary.get("David"));
dictionary.add("Rick", 9);
print(dictionary.get("Rick"));
dictionary.add("David", 6);
print(dictionary.get("David"));
```