Finished up to the last question

2 files changed, 33 insertions, 316 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
diff --git a/hw2/assignment_lists_sp23.py b/hw2/assignment_lists_sp23.py
index a339f1f..4aeca33 100644
--- a/hw2/assignment_lists_sp23.py
+++ b/hw2/assignment_lists_sp23.py
@@ -72,12 +72,12 @@ class DoublyLinkedList(object):
 
     def __next__(self):
         """Standard python iterator method"""
-        if self.__current is self.__trailer:
-            raise StopIteration
-
         if self.__current is None:
             self.__current = self.__header
 
+        if self.__current.next_node is self.__trailer:
+            raise StopIteration
+
         self.__current = self.__current.next_node
         return self.__current
 
@@ -263,6 +263,9 @@ each element of a list.
 #Test your implementation here
 ### USE THE MAP FUNCTION HERE
 
+g = lambda a: a ** 2
+dL.map(g)
+
 print(dL)
 
 assert str(dL) == "((0), (1764), (1), (4), (1156), (9), (1))"
@@ -292,10 +295,16 @@ it might be used a few times.
 """
 
 # WRITE YOUR CODE HERE
+twenties = DoublyLinkedList()
+for i in range(20,30):
+    n = Node(i)
+    twenties.add_last(n)
+
 print(twenties)
 assert str(twenties) == "((20), (21), (22), (23), (24), (25), (26), (27), (28), (29))"
 
 ##Write more code here to change the DLL
+twenties.map(lambda x: x + 10)
 
 print(twenties)
 assert str(twenties) =="((30), (31), (32), (33), (34), (35), (36), (37), (38), (39))"
@@ -304,10 +313,12 @@ assert str(twenties) =="((30), (31), (32), (33), (34), (35), (36), (37), (38), (
 **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`."""
+# Subtracting 10 to undo the last question
+twenties.map(lambda x: (x - 10) * 5)
 
 # your code here
-print(twentyBy5)
-assert str(twentyBy5) == "((100), (105), (110), (115), (120), (125), (130), (135), (140), (145))"
+print(twenties)
+assert str(twenties) == "((100), (105), (110), (115), (120), (125), (130), (135), (140), (145))"
 
 """
 **Task 13 (5 points)**: Remove elements that are multiples of 4.
@@ -315,16 +326,31 @@ assert str(twentyBy5) == "((100), (105), (110), (115), (120), (125), (130), (135
 _Hint_: Use the methods `next` and `remove`."""
 
 # Your code here
+cur = twenties.get_first()
+end = twenties.get_last().next_node # idk why but python is saying there is no attribute __trailer fora dll
+while cur != end:
+    next = cur.next_node
+    if cur.element % 4 == 0:
+        twenties.remove(cur)
+    cur = next
+
 
-assert str(twentyBy5) == '((105), (110), (115), (125), (130), (135), (145))'
+assert str(twenties) == '((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`."""
+cur = twenties.get_first()
+end = twenties.get_last().next_node # idk why but python is saying there is no attribute __trailer fora dll
+while cur != end:
+    next = cur.next_node
+    if not (cur.element % 2 == 0):
+        twenties.remove(cur)
+    cur = next
 
 # Your code here
-assert str(twentyBy5) == '((110), (130))'
+assert str(twenties) == '((110), (130))'
 
 """## Proving performance properties