Doubly Linked List

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.

Constructing a Doubly Linked List

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):
        """Standard python iterator method"""
        pass

    def __next__(self):
        """Standard python iterator method"""
        pass

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

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

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

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

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

    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

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

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

    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

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

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

Using a Doubly Linked List

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

Applying methods of the DoublyLinkedList and Node classes

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 methods next, add_before, and add_after.

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

Hint: Use the methods map, get_previous, and set_element.

T13 (5 points): Remove elements that are multiplied by 5.

Hint: Use the methods next and remove.

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

Hint: Use the methods get_previous and remove.

Proving performance properties

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

Sets

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 [3]:
class Set(object):
    """Set data structure"""
    def __init__(self, list):
        pass
In [ ]:
#Test your implementation here

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."""
    pass
In [ ]:
#Test your implementation here

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

In [ ]:
def difference(list1, list2):
    """Difference between sets."""
    pass
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."""
    pass
In [ ]:
#Test your implementation here

Dictionaries

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 [ ]:
class Dictionary(object):
    """Dictionary data structure"""
    
    def __init__(self, keys, values):
        pass
    
    def get(self, key):
        pass
    
    def add(self, key, value):
        pass
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 [ ]:
#You can test your implementation here