Description
Part 1 – Summary and Specific Instructions
1. Implement a Singly Linked List data structure by completing the skeleton code provided in the file sll.py. Once completed, your implementation will include the following methods: insert_front(), insert_back() insert_at_index(), remove_at_index() remove() count() find() slice()
2. We will test your implementation with different types of objects, not just integers. We guarantee that all such objects will have correct implementations of methods __eq__(), __lt__(), __gt__(), __ge__(), __le__(), and __str__().
3. The number of objects stored in the list at any given time will be between 0 and 900 inclusive.
4. Make sure that you include the provided SLNode class in your project. You do NOT upload this class to Gradescope.
5. The variable in the LinkedList class (_head) is marked as private, so it may only be accessed/changed directly inside the class. Variables in the SLNode class (provided in its own file, as it will also be used in Parts 4 and 5) are not marked as private. You are allowed to access/change their values directly wherever the SLNode class is used, and are not required to write getter or setter methods for them.
6. RESTRICTIONS: You are not allowed to use ANY built-in Python data structures or their methods.
7. This implementation must be done with the use of a front sentinel node. Page 4 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation insert_front(self, value: object) -> None: This method adds a new node at the beginning of the list (right after the front sentinel). It must be implemented with O(1) runtime complexity.
Example #1: test_case = [“A”, “B”, “C”] lst = LinkedList() for case in test_case: lst.insert_front(case) print(lst) Output: SLL [A] SLL [B -> A] SLL [C -> B -> A] insert_back(self, value: object) -> None: This method adds a new node at the end of the list. It must be implemented with O(N) runtime complexity. Example #1: test_case = [“C”, “B”, “A”] lst = LinkedList() for case in test_case: lst.insert_back(case) print(lst) Output: SLL [C] SLL [C -> B] SLL [C -> B -> A] Table of Contents Page 5 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation insert_at_index(self, index: int, value: object) -> None: This method inserts a new value at the specified index position in the linked list. Index 0 refers to the beginning of the list (right after the front sentinel). If the provided index is invalid, the method raises a custom “SLLException”.
Code for the exception is provided in the skeleton file. If the linked list contains N nodes (the sentinel node is not included in this count), valid indices for this method are [0, N] inclusive. It must be implemented with O(N) runtime complexity. Example #1: lst = LinkedList() test_cases = [(0, “A”), (0, “B”), (1, “C”), (3, “D”), (-1, “E”), (5, “F”)] for index, value in test_cases: print(“Inserted”, value, “at index”, index, “: “, end=””) try: lst.insert_at_index(index, value) print(lst) except Exception as e: print(type(e)) Output: Inserted A at index 0 : SLL [A]
Inserted B at index 0 : SLL [B -> A] Inserted C at index 1 : SLL [B -> C -> A] Inserted D at index 3 : SLL [B -> C -> A -> D] Inserted E at index -1 : <class ‘__main__.SLLException’> Inserted F at index 5 : <class ‘__main__.SLLException’> Page 6 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation remove_at_index(self, index: int) -> None: This method removes the node at the specified index position from the linked list. Index 0 refers to the beginning of the list (right after the front sentinel). If the provided index is invalid, the method raises a custom “SLLException”. Code for the exception is provided in the skeleton file.
If the list contains N elements (the sentinel node is not included in this count), valid indices for this method are [0, N – 1] inclusive. It must be implemented with O(N) runtime complexity. Example #1: lst = LinkedList([1, 2, 3, 4, 5, 6]) print(f”Initial LinkedList : {lst}”) for index in [0, 2, 0, 2, 2, -2]: print(“Removed at index:”, index, “: “, end=””) try: lst.remove_at_index(index) print(lst) except Exception as e: print(type(e)) print(lst) Output: Initial LinkedList : SLL [1 -> 2 -> 3 -> 4 -> 5 -> 6] Removed at index 0 : SLL [2 -> 3 -> 4 -> 5 -> 6] Removed at index 2 : SLL [2 -> 3 -> 5 -> 6] Removed at index 0 : SLL [3 -> 5 -> 6] Removed at index 2 : SLL [3 -> 5] Removed at index 2 : <class ‘__main__.SLLException’> Removed at index -2 : <class ‘__main__.SLLException’> Table of Contents Page 7 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation remove(self, value: object) -> bool:
This method traverses the list from the beginning to the end, and removes the first node that matches the provided “value” object. The method returns True if a node was removed from the list. Otherwise, it returns False. It must be implemented with O(N) runtime complexity. Example #1: lst = LinkedList([1, 2, 3, 1, 2, 3, 1, 2, 3]) print(f”Initial LinkedList, Length: {lst.length()}\n {lst}”) for value in [7, 3, 3, 3, 3]: print(f”remove({value}): {lst.remove(value}, Length: {lst.length()}” f”\n {lst}”) Output: Initial LinkedList, Length: 9 SLL [1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3] remove(7): False, Length: 9 SLL [1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3] remove(3):
True, Length: 8 SLL [1 -> 2 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3] remove(3): True, Length: 7 SLL [1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 3] remove(3): True, Length: 6 SLL [1 -> 2 -> 1 -> 2 -> 1 -> 2] remove(3): False, Length: 6 SLL [1 -> 2 -> 1 -> 2 -> 1 -> 2] Page 8 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation Example #2: lst = LinkedList([1, 2, 3, 1, 2, 3, 1, 2, 3]) print(f”Initial LinkedList, Length: {lst.length()}\n {lst}”) for value in [1, 2, 3, 1, 2, 3, 3, 2, 1]: print(f”remove({value}): {lst.remove(value), Length: {lst.length()}” f”\n {lst}”) Output: Initial LinkedList, Length: 9 SLL [1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3] remove(1): True, Length: 8 SLL [2 -> 3 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3] remove(2): True, Length: 7 SLL [3 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3] remove(3): True, Length: 6 SLL [1 -> 2 -> 3 -> 1 -> 2 -> 3] remove(1): True, Length: 5 SLL [2 -> 3 -> 1 -> 2 -> 3] remove(2): True, Length: 4 SLL [3 -> 1 -> 2 -> 3] remove(3): True, Length: 3 SLL [1 -> 2 -> 3] remove(3):
True, Length: 2 SLL [1 -> 2] remove(2): True, Length: 1 SLL [1] remove(1): True, Length: 0 SLL [] Table of Contents Page 9 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation count(self, value: object) -> int: This method counts the number of elements in the list that match the provided “value” object. The method then returns this number. It must be implemented with O(N) runtime complexity. Example #1: lst = LinkedList([1, 2, 3, 1, 2, 2]) print(lst, lst.count(1), lst.count(2), lst.count(3), lst.count(4)) Output: SLL [1 -> 2 -> 3 -> 1 -> 2 -> 2] 2 3 1 0 find(self, value: object) -> bool: This method returns a Boolean value based on whether or not the provided “value” object exists in the list. It must be implemented with O(N) runtime complexity. Example #1: lst = LinkedList([“Waldo”, “Clark Kent”, “Homer”, “Santa Claus”]) print(lst) print(lst.find(“Waldo”)) print(lst.find(“Superman”)) print(lst.find(“Santa Claus”)) Output: SLL [Waldo -> Clark Kent -> Homer -> Santa Claus]
True False True Page 10 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation slice(self, start_index: int, size: int) -> object: This method returns a new LinkedList object that contains the requested number of nodes from the original list, starting with the node located at the requested start index. If the original list contains N nodes, a valid start_index is in range [0, N – 1] inclusive.
The original list cannot be modified. The runtime complexity of your implementation must be O(N). You are allowed to directly access the variable (_head) of LinkedList objects you create. If the provided start index is invalid, or if there are not enough nodes between the start index and the end of the list to make a slice of the requested size, this method raises a custom “SLLException”. Code for the exception is provided in the skeleton file. Example #1: lst = LinkedList([1, 2, 3, 4, 5, 6, 7, 8, 9]) ll_slice = lst.slice(1, 3) print(“Source:”, lst) print(“Start: 1 Size: 3 :”, ll_slice) ll_slice.remove_at_index(0) print(“Removed at index 0 :”, ll_slice) Output: Source: SLL [1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9]
Start: 1 Size: 3 : SLL [2 -> 3 -> 4] Removed at index 0 : SLL [3 -> 4] Example #2: lst = LinkedList([10, 11, 12, 13, 14, 15, 16]) print(“Source:”, lst) slices = [(0, 7), (-1, 7), (0, 8), (2, 3), (5, 0), (5, 3), (6, 1)] for index, size in slices: print(“Start:”, index, “Size:”, size, end=””) try: print(” :”, lst.slice(index, size)) except: print(” : exception occurred.”) Output: Source: SLL [10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16] Start: 0 Size: 7 : SLL [10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16] Start: -1 Size: 7 : exception occurred. Start: 0 Size: 8 : exception occurred. Start: 2 Size: 3 : SLL [12 -> 13 -> 14] Start: 5 Size: 0 : SLL [] Start: 5 Size: 3 : exception occurred. Start: 6 Size: 1 : SLL [16] Table of Contents Page 11 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation Part 2 – Summary and Specific Instructions
1. Implement a Stack ADT class by completing the provided skeleton code in the file stack_da.py. You will use the Dynamic Array data structure that you implemented in Assignment 2 as the underlying storage for your Stack ADT. 2. Your Stack ADT implementation will include the following standard Stack methods: push() pop() top() 3. We will test your implementation with different types of objects, not just integers. We guarantee that all such objects will have correct implementations of methods __eq__(), __lt__(), __gt__(), __ge__(), __le__(), and __str__(). 4. The number of objects stored in the Stack at any given time will be between 0 and 1,000,000 inclusive. The stack must allow for the storage of duplicate objects.
5. RESTRICTIONS: You are not allowed to use ANY built-in Python data structures and/or their methods. You must solve this portion of the assignment by importing the DynamicArray class that you wrote in Assignment 2, and using class methods to write your solution. You are also not allowed to directly access any variables of the DynamicArray class (self._da._size, self._da._capacity, and self._da._data). All work must be done by only using class methods. Page 12 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation push(self, value: object) ->
None: This method adds a new element to the top of the stack. It must be implemented with O(1) amortized runtime complexity. Example #1: s = Stack() print(s) for value in [1, 2, 3, 4, 5]: s.push(value) print(s) Output: STACK: 0 elements. [] STACK: 5 elements. [1, 2, 3, 4, 5] pop(self) -> object: This method removes the top element from the stack and returns its value. It must be implemented with O(1) amortized runtime complexity. If the stack is empty, the method raises a custom “StackException”. Code for the exception is provided in the skeleton file. Example #1: s = Stack() try: print(s.pop()) except Exception as e: print(“Exception:”, type(e)) for value in [1, 2, 3, 4, 5]: s.push(value) for i in range(6): try: print(s.pop()) except Exception as e: print(“Exception:”, type(e)) Output: Exception: <class ‘__main__.StackException’> 5 4 3 2 1 Exception: <class ‘__main__.
StackException’> Table of Contents Page 13 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation top(self) -> object: This method returns the value of the top element of the stack without removing it. It must be implemented with O(1) runtime complexity. If the stack is empty, the method raises a custom “StackException”. Code for the exception is provided in the skeleton file. Example #1: s = Stack() try: s.top() except Exception as e: print(“No elements in stack”, type(e)) s.push(10) s.push(20) print(s) print(s.top()) print(s.top()) print(s) Output: No elements in stack <class ‘__main__.StackException’> STACK: 2 elements. [10, 20] 20 20 STACK: 2 elements. [10, 20] Page 14 of 26 CS261 Data Structures Assignment 3:
Linked List / ADT Implementation Part 3 – Summary and Specific Instructions 1. Implement a Queue ADT class that utilizes a circular buffer (as described in the Exploration) by completing the provided skeleton code in the file queue_sa.py. You will use the Static Array data structure from previous assignments as the underlying storage for your Queue ADT. 2. Once completed, your implementation will include the following methods: enqueue() dequeue() front() The following private helper method in the skeleton code is used by __str__() to handle the “wraparound” in the circular buffer. You may find it helpful for your methods: _increment() There is also a suggested (optional and private) helper method in the skeleton code that you may wish to implement, to assist with resizing: _double_queue() 3. We will test your implementation with different types of objects, not just integers.
We guarantee that all such objects will have correct implementations of methods __eq__(), __lt__(), __gt__(), __ge__(), __le__(), and __str__(). 4. The number of objects stored in the queue at any given time will be between 0 and 1,000,000 inclusive. The queue must allow for the storage of duplicate elements. 5. RESTRICTIONS: You are not allowed to use ANY built-in Python data structures and/or their methods. You must solve this portion of the assignment by importing the StaticArray class provided in Assignment 1, and using class methods to write your solution. You are also not allowed to directly access any variables of the StaticArray class (self._sa._size and self._sa._data). All work must be done by only using class methods. Table of Contents Page 15 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation enqueue(self, value: object) -> None: This method adds a new value to the end of the queue. It must be implemented with O(1) amortized runtime complexity. Example #1: q = Queue() print(q) for value in [1, 2, 3, 4, 5]: q.enqueue(value) print(q) Output: QUEUE: 0 elements. [] QUEUE:
5 elements. [1, 2, 3, 4, 5] Page 16 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation dequeue(self) -> object: This method removes and returns the value at the beginning of the queue. It must be implemented with O(1) runtime complexity. If the queue is empty, the method raises a custom “QueueException”. Code for the exception is provided in the skeleton file. Example #1: q = Queue() for value in [1, 2, 3, 4, 5]: q.enqueue(value) print(q) for i in range(q.size() + 1): try: print(q.dequeue()) except Exception as e: print(“No elements in queue”, type(e)) for value in [6, 7, 8, 111, 222, 3333, 4444]: q.enqueue(value) print(q) q.print_underlying_sa() Output: QUEUE: 5 elements. [1, 2, 3, 4, 5] 1 2 3 4 5 No elements in queue <class ‘__main__.QueueException’> QUEUE: 7 element(s). [6, 7, 8, 111, 222, 3333, 4444] STAT_ARR Size: 8 [111, 222, 3333, 4444, 5, 6, 7, 8] Table of Contents Page 17 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation front(self) -> object: This method returns the value of the front element of the queue without removing it.
It must be implemented with O(1) runtime complexity. If the queue is empty, the method raises a custom “QueueException”. Code for the exception is provided in the skeleton file. NOTE: The circular buffer tests utilize the action_and_print() function to perform various operations and display the results. You are encouraged to review this function’s code in the starter file to get a feel for how it works. For an explanation of circular buffers, please read Exploration: Queues. Example #1: q = Queue() print(q) for value in [‘A’, ‘B’, ‘C’, ‘D’]: try: print(q.front()) except Exception as e: print(“No elements in queue”, type(e)) q.enqueue(value) print(q) Output: QUEUE: 0 elements. []
No elements in queue <class ‘__main__.QueueException’> A A A QUEUE: 4 elements. [A, B, C, D] Testing for Circular Buffer print(“\n Circular buffer tests: #\n”) q = Queue() print(“# Enqueue: 2, 4, 6, 8”) test_case = [2, 4, 6, 8] for value in test_case: q.enqueue(value) print(q) q.print_underyling_sa() print() Page 18 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation Output: # Enqueue: 2, 4, 6, 8 QUEUE: 4 element(s). [2, 4, 6, 8] STAT_ARR Size: 4 [2, 4, 6, 8] action_and_print(“# Dequeue a value”, q.dequeue, [], q) Output: # Dequeue a value QUEUE: 3 element(s). [4, 6, 8] STAT_ARR Size: 4 [2, 4, 6, 8] action_and_print(“# Enqueue: 10”, q.enqueue, [10], q)
Output: # Enqueue: 10 QUEUE: 4 element(s). [4, 6, 8, 10] STAT_ARR Size: 4 [10, 4, 6, 8] action_and_print(“# Enqueue: 12”, q.enqueue, [12], q) Output: # Enqueue: 12 QUEUE: 5 element(s). [4, 6, 8, 10, 12] STAT_ARR Size: 8 [4, 6, 8, 10, 12, None, None, None] print(“# Dequeue until empty”) while not q.is_empty(): q.dequeue print(q) q.print_underlying_sa() print() Output: # Dequeue until empty QUEUE: 0 element(s). [] STAT_ARR Size: 8 [4, 6, 8, 10, 12, None, None, None] Table of Contents Page 19 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation action_and_print(“# Enqueue: 14, 16, 18”, q.enqueue, [14, 16, 18], q) Output: #
Enqueue: 14, 16, 18 QUEUE: 3 element(s). [14, 16, 18] STAT_ARR Size: 8 [4, 6, 8, 10, 12, 14, 16, 18] action_and_print(“# Enqueue: 20”, q.enqueue, [20], q) Output: # Enqueue: 20 QUEUE: 4 element(s). [14, 16, 18, 20] STAT_ARR Size: 8 [20, 6, 8, 10, 12, 14, 16, 18] action_and_print(“# Enqueue: 22, 24, 26, 28”, q.enqueue, [22, 24, 26, 28], q) Output: # Enqueue: 22, 24, 26, 28 QUEUE: 8 element(s). [14, 16, 18, 20, 22, 24, 26, 28] STAT_ARR Size: 8 [20, 22, 24, 26, 28, 14, 16, 18] action_and_print(“# Enqueue: 30”, q.enqueue, [30], q) Output: # Enqueue: 30 QUEUE: 9 element(s). [14, 16, 18, 20, 22, 24, 26, 28, 30] STAT_ARR Size: 16 [14, 16, 18, 20, 22, 24, 26, 28, 30, None, None, None, None, None, None, None] Page 20 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation Part 4 – Summary and Specific Instructions 1. Implement a Stack ADT class by completing the provided skeleton code in the file stack_sll.py.
You will use a chain of Singly-Linked Nodes (the provided SLNode) as the underlying storage for your Stack ADT. Be sure to review the Exploration on Stacks for an example. 2. Your Stack ADT implementation will include the following standard Stack methods: push() pop() top() 3. We will test your implementation with different types of objects, not just integers. We guarantee that all such objects will have correct implementations of methods __eq__(), __lt__(), __gt__(), __ge__(), __le__(), and __str__(). 4. The number of objects stored in the Stack at any given time will be between 0 and 1,000,000 inclusive. The stack must allow for the storage of duplicate objects.
5. RESTRICTIONS: You are not allowed to use ANY built-in Python data structures and/or their methods. You must solve this portion of the assignment by using the SLNode class provided with this assignment. Table of Contents Page 21 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation push(self, value: object) -> None: This method adds a new element to the top of the stack. It must be implemented with O(1) runtime complexity. Example #1: s = Stack() print(s) for value in [1, 2, 3, 4, 5]: s.push(value) print(s) Output: STACK [] STACK [5 -> 4 -> 3 -> 2 -> 1] pop(self) -> object: This method removes the top element from the stack and returns its value. It must be implemented with O(1) runtime complexity. If the stack is empty, the method raises a custom “StackException”.
Code for the exception is provided in the skeleton file. Example #1: s = Stack() try: print(s.pop()) except Exception as e: print(“Exception:”, type(e)) for value in [1, 2, 3, 4, 5]: s.push(value) for i in range(6): try: print(s.pop()) except Exception as e: print(“Exception:”, type(e)) Output: Exception: <class ‘__main__.StackException’> 5 4 3 2 1 Exception: <class ‘__main__.StackException’> Page 22 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation top(self) -> object: This method returns the value of the top element of the stack without removing it. It must be implemented with O(1) runtime complexity. If the stack is empty, the method raises a custom “StackException”. Code for the exception is provided in the skeleton file. Example #1: s = Stack() try: s.top() except
Exception as e: print(“No elements in stack”, type(e)) s.push(10) s.push(20) print(s) print(s.top()) print(s.top()) print(s) Output: No elements in stack <class ‘__main__.StackException’> STACK [20 -> 10] 20 20 STACK [20 -> 10] Table of Contents Page 23 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation Part 5 – Summary and Specific Instructions 1. Implement a Queue ADT class by completing the provided skeleton code in the file queue_sll.py. You will use a chain of Singly-Linked Nodes (the provided SLNode) as the underlying storage for your Queue ADT. Be sure to review the Exploration on Queues for an example
. 2. Once completed, your implementation will include the following methods: enqueue() dequeue() front() 3. We will test your implementation with different types of objects, not just integers. We guarantee that all such objects will have correct implementations of methods __eq__(), __lt__(), __gt__(), __ge__(), __le__(), and __str__(). 4. The number of objects stored in the queue at any given time will be between 0 and 1,000,000 inclusive. The queue must allow for the storage of duplicate elements. 5. RESTRICTIONS:
You are not allowed to use ANY built-in Python data structures and/or their methods. You must solve this portion of the assignment by using the SLNode class provided with this assignment. Page 24 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation enqueue(self, value: object) -> None: This method adds a new value to the end of the queue. It must be implemented with O(1) runtime complexity. Example #1: q = Queue() print(q) for value in [1, 2, 3, 4, 5]: q.enqueue(value)m print(q) Output: QUEUE [] QUEUE [1 -> 2 -> 3 -> 4 -> 5] dequeue(self) -> object: This method removes and returns the value from the beginning of the queue. It must be implemented with O(1) runtime complexity. If the queue is empty, the method raises a custom “QueueException”.
Code for the exception is provided in the skeleton file. Example #1: q = Queue() for value in [1, 2, 3, 4, 5]: q.enqueue(value) print(q) for i in range(6): try: print(q.dequeue()) except Exception as e: print(“No elements in queue”, type(e)) Output: QUEUE [1 -> 2 -> 3 -> 4 -> 5] 1 2 3 4 5 No elements in queue <class ‘__main__.QueueException’> Table of Contents Page 25 of 26 CS261 Data Structures Assignment 3: Linked List / ADT Implementation front(self) -> object: This method returns the value of the front element of the queue without removing it.
It must be implemented with O(1) runtime complexity. If the queue is empty, the method raises a custom “QueueException”. Code for the exception is provided in the skeleton file. Example #1: q = Queue() print(q) for value in [‘A’, ‘B’, ‘C’, ‘D’]: try: print(q.front()) except Exception as e: print(“No elements in queue”, type(e)) q.enqueue(value) print(q) Output: QUEUE [] No elements in queue <class ‘__main__.QueueException’> A A A QUEUE [A -> B -> C -> D] Page 26 of 26
