Finished hw2

2 files changed, 39 insertions, 0 deletions

diff --git a/hw2/__pycache__/assignment_lists_sp23.cpython-310.pyc b/hw2/__pycache__/assignment_lists_sp23.cpython-310.pyc
index cac7ac9..9dac05f 100644
--- a/hw2/__pycache__/assignment_lists_sp23.cpython-310.pyc
+++ b/hw2/__pycache__/assignment_lists_sp23.cpython-310.pyc
diff --git a/hw2/assignment_lists_sp23.py b/hw2/assignment_lists_sp23.py
index 4aeca33..7f80177 100644
--- a/hw2/assignment_lists_sp23.py
+++ b/hw2/assignment_lists_sp23.py
@@ -150,6 +150,22 @@ class DoublyLinkedList(object):
         node.previous_node = None
         self.__size -= 1
 
+    def __getitem__(self, index):
+        """Move to a given index in the list"""
+        assert index < self.__size
+        if index < (self.__size // 2):
+            pos = self.__header.next_node
+            for _ in range(index):
+                pos = pos.next_node
+        else:
+            pos = self.__trailer
+            for _ in range(self.__size - index):
+                pos = pos.previous_node
+
+        return pos
+
+
+
 """**Task 1 (5 points)**: Using the constructor from the **DoublyLinkedList**, create a new doubly linked list of integers between 0 and 3."""
 
 dL = DoublyLinkedList()
@@ -357,3 +373,26 @@ assert str(twenties) == '((110), (130))'
 **T15 (5 points)**: Prove when the complexity to delete a node in a doubly linked list is $O(1)$
 and $O(n)$.
 """
+
+from time import time
+
+def make_n(n=1000000):
+    dll = DoublyLinkedList()
+    for i in range(n):
+        dll.add_last(Node(i))
+    return dll
+n = 1000000
+dll = make_n(n)
+times = []
+samples = 21
+for i in range(samples):
+    t0 = time()
+    _ = dll[n//2//samples*i]
+    times.append(time() - t0)
+
+print(times)
+
+import matplotlib.pyplot as plt
+plt.plot(times)
+plt.show()
+