diff options
Diffstat (limited to 'hw2/assignment_lists_f22-1(possible solutions).py')
| -rw-r--r-- | hw2/assignment_lists_f22-1(possible solutions).py | 309 |
1 files changed, 0 insertions, 309 deletions
diff --git a/hw2/assignment_lists_f22-1(possible solutions).py b/hw2/assignment_lists_f22-1(possible solutions).py deleted file mode 100644 index 4b9048e..0000000 --- a/hw2/assignment_lists_f22-1(possible solutions).py +++ /dev/null @@ -1,309 +0,0 @@ -# -*- coding: utf-8 -*- -"""assignment-lists-f22.ipynb - -Automatically generated by Colaboratory. - -Original file is located at - https://colab.research.google.com/drive/1x6L0YQtnlu96uhVtx4vXaPQIWLSICCZ6 - -### 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 lectures we implemented a few simple linear data structres: queue, list, deques, stacks. Now we expect you to implement one of these structures yourself. - -You are provided 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 PSADS book. - -## Constructing a Doubly Linked List - -The **Node** class implementation is already given: -""" - -class Node(object): - """Doubly linked node which stores an object""" - - def __init__(self, element, next_node=None, previous_node=None): - # The underscores are to prevent overwriting the variables if inherited and prevents access from outside of scope - self.element = element - self.next_node = next_node - self.previous_node = previous_node - - - def __repr__(self): - return str((self.element, self.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**. """ - -class DoublyLinkedList(object): - """Doubly linked node data structure""" - def __init__(self): - self.__size = 0 - self.__header = Node('Header') - self.__trailer = Node('Trailer') - self.__header.next_node = (self.__trailer) - self.__trailer.previous_node = (self.__header) - self.__current = None - - - def __repr__(self): - """This needs to work in order to pass the assertions below""" - out = '(' - node = self.__header.next_node - for i in range(self.__size): - out += f"({node.element}), " - node = node.next_node - return out[:-2]+')' - - def __iter__(self): - """Standard python iterator method""" - self.__current = None - return self - - def __next__(self): - """Standard python iterator method""" - if self.is_empty(): - raise StopIteration() - #beggingin - elif self.__current is None: - self.__current = self.__header - #midds - self.__current = self.__current.next_node - #endo - if self.__current == self.__trailer: - raise StopIteration() - else: - return self.__current - - - def map(self, function): - """Run function on every element in the list""" - pass - 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""" - 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""" - previous = existing.previous_node - previous.next_node = new - new.previous_node = previous - new.next_node = existing - existing.previous_node = new - self.__size += 1 - - 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""" - self.add_before(new,self.__trailer) - def remove(self, node): - """Remove the given node from the list""" - pass - -"""**Task 1 (5 points)**: Using the constructor from the **DoublyLinkedList**, create a new doubly linked list of integers between 0 and 3.""" - -dL = DoublyLinkedList() - -for i in range(4): - dL.add_last(Node(i)) - -for node in dL: - print(f"NODES: {node}") - -print(f"136: {dL}") - -# assert str(dL) == f"((0), (1), (2), (3))" - -"""## 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. - -**Task 2 (10 points)**: Implement the `size` method that returns the size of a doubly linked list. - - -""" - -#Test your implementation here -print(dL.size()) -assert dL.size() == 4 - -"""**Task 3 (5 points)**: Implement the `is_empty` method that checks -whether a doubly linked list is empty. - - -""" - -#Test your implementation here -print(dL.is_empty()) - -dL2 = DoublyLinkedList() -print(dL2.is_empty()) - - -assert dL.is_empty() == False -assert dL2.is_empty() == True -del dL2 - -"""**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. - -""" - -#Test your implementation here -print(dL.get_first()) -print(dL.get_last()) - -assert str(dL.get_first()) == f"(0, (1, (2, (3, ('Trailer', None)))))" -assert str(dL.get_last()) == f"(3, ('Trailer', None))" - -"""**Task 5 (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. - -""" - -#Test your implementation here -print(dL.get_last().get_previous()) -print(dL.get_first().get_next()) - -assert str(dL.get_last().get_previous()) == "(2, (3, ('Trailer', None)))" -assert str(dL.get_first().get_next()) == "(1, (2, (3, ('Trailer', None))))" - -"""**Task 6(10 points)**: Implement the methods `add_before` and `add_after` -to respectively insert new elements before and after a node of the list. - -""" - -#Test your implementation here -dL.add_after(Node(42),dL.get_first()) -dL.add_before(Node(34),dL.get_last()) - -print(dL) -assert str(dL) == f"((0), (42), (1), (2), (34), (3))" - -"""**Task 7 (10 points)**: Implement the methods `add_first` and `add_last` -to respectively insert new nodes in the beginning and in the end of a list. - -""" - -#Test your implementation here -dL.add_first(Node(7)) -dL.add_last(Node(-1)) -print(dL) -assert str(dL) == "((7), (0), (42), (1), (2), (34), (3), (-1))" - -"""**Task 8 (10 points)**: Implement the method `remove` to remove -a node from a list. - -""" - -#Test your implementation here -dL.remove(dL.get_first()) -print(dL.get_first()) - -assert dL.get_first().get_element() == 0 - -"""**Task 9 (10 points)**: Implement the method `map` to apply a function on -each element of a list. -""" - -#Test your implementation here -### USE THE MAP FUNCTION HERE - -print(dL) - -assert str(dL) == "((0), (1764), (1), (4), (1156), (9), (1))" - -"""**Task 10 (10 points)**: Implement the method `next` to iterate the elements -of a list. - - -""" - -#Test your implementation here -for node in dL: - print(node.get_element()) - -dL - -"""## 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. - -**Task 11 (5 points)**: Add 10 to each element of the list of integers in the twenties. - -_Hint_: Use the methods `map`. -""" - -# WRITE YOUR CODE HERE -print(twenties) -assert str(twenties) == "((20), (21), (22), (23), (24), (25), (26), (27), (28), (29))" - -##Write more code here to change the DLL - -print(twenties) -assert str(twenties) =="((30), (31), (32), (33), (34), (35), (36), (37), (38), (39))" - -""" -**Task 12 (5 points)**: Multiply each element of the list of integers in the twenties by 5. - -_Hint_: Use the methods `map`, `get_previous`, and `set_element`.""" - -# your code here -print(twentyBy5) -assert str(twentyBy5) == "((100), (105), (110), (115), (120), (125), (130), (135), (140), (145))" - -""" -**Task 13 (5 points)**: Remove elements that are multiples of 4. - -_Hint_: Use the methods `next` and `remove`.""" - -# Your code here - -assert str(twentyBy5) == '((105), (110), (115), (125), (130), (135), (145))' - -""" -**Task 14 (5 points)**: Remove elements from the list that are odd numbers. - -_Hint_: Use the methods `get_previous` and `remove`.""" - -# Your code here -assert str(twentyBy5) == '((110), (130))' - -"""## 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)$. -"""
\ No newline at end of file |