Data structure (Python)

profileTrist1111
CS261_Programming_Assignment3-v1.05.pdf
Home>Computer Science homework help>Data structure (Python)

CS261 Data Structures

Assignment 3 v 1.05 (revised 10/16/2020)  

Your Very Own Linked List

CS261 Data Structures Project 3: Your Very Own Linked List

Contents General Instructions ........................................................ 3 Part 1 - Singly Linked List

Summary and Specific Instructions ....................................... 4 add_front() ....................................................................... 5 add_back() ....................................................................... 5 insert_at_index() ............................................................... 6 remove_front() .................................................................. 7 remove_back() .................................................................. 8 remove_at_index() ............................................................ 9 get_front() ....................................................................... 10 get_back() ....................................................................... 10 remove() .......................................................................... 11 count() ............................................................................. 11 slice() ............................................................................... 12

Part 2 - Max Stack ADT Summary and Specific Instructions ....................................... 13 push(), pop(), top() ………...................................................... 14 get_max() ......................................................................... 16

Part 3 - Circular Doubly Linked List Summary and Specific Instructions ....................................... 17 swap_pairs() ...................................................................... 19 reverse() ........................................................................... 20 sort() ................................................................................ 22 rotate() ............................................................................. 23 remove_duplicates() ........................................................... 24 odd_even() ........................................................................ 25

Part 4 - Queue From Two Stacks Summary and Specific Instructions ....................................... 26 enqueue() ......................................................................... 27 dequeue() ......................................................................... 27

Page 2 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

General Instructions

1. Programs in this assignment must be written in Python v3 and submitted to Gradescope before the due date specified in the syllabus. You may resubmit your code as many times as necessary. Gradescope allows you to choose which submission will be graded.

2. In Gradescope, your code will run through several tests. Any failed tests will provide a brief explanation of testing conditions to help you with troubleshooting. Your goal is to pass all tests.

3. We encourage you to create your own test programs and cases even though this work won’t have to be submitted and won’t be graded. Gradescope tests are limited in scope and may not cover all edge cases. Your submission must work on all valid inputs. We reserve the right to test your submission with more tests than Gradescope.

4. Your code must have an appropriate level of comments. At a minimum, each method should have a descriptive docstring. Additionally, put comments throughout the code to make it easy to follow and understand.

5. You will be provided with a starter “skeleton” code, on which you will build your implementation. Methods defined in skeleton code must retain their names and input / output parameters. Variables defined in skeleton code must also retain their names. We will only test your solution by making calls to methods defined in the skeleton code and by checking values of variables defined in the skeleton code. You can add more helper methods and variables, as needed. However, certains classes and methods can not be changed in any way. Please see comments in the skeleton code for guidance. In particular, content of any methods pre-written for you as part of the skeleton code must not be changed.

6. Both the skeleton code and code examples provided in this document are part of assignment requirements. They have been carefully selected to demonstrate requirements for each method. Refer to them for the detailed description of expected method behavior, input / output parameters, and handling of edge cases. Code examples may include assignment requirements not explicitly stated elsewhere.

7. For each method, you can choose to implement a recursive or iterative solution. When using a recursive solution, be aware of maximum recursion depths on large inputs. We will specify the maximum input size that your solution must handle.

Page 3 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

Part 1 - Summary and Specific Instructions

1. Implement Deque and Bag ADT interfaces with a Singly Linked List data structure by completing provided skeleton code in the file sll.py . Once completed, your implementation will include the following methods:

add_front(), add_back() insert_at_index() remove_front(), remove_back() remove_at_index() get_front(), get_back() remove() count() slice()

2. We will test your implementation with different types of objects, not just integers. We guarantee that all such objects will have correct implementation of methods __eq__, __lt__, __gt__, __ge__, __le__ and __str__.

3. Number of objects stored in the list at any given time will be between 0 and 900, inclusive.

4. Variables in the SLNode and LinkedList classes are not marked as private. For this portion of the assignment you are allowed to access and change their values directly. You are not required to write getter or setter methods for them.

5. RESTRICTIONS: You are not allowed to use ANY built-in Python data structures and their methods.

6. This implementation must be done with the use of the front and back sentinel nodes.

Page 4 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

add_front (self, value: object) -> None:   This method adds a new node at the beginning of the list (right after the front sentinel). Example #1: list = LinkedList() print(list) list.add_front('A') list.add_front('B') list.add_front('C') print(list) Output: SLL[] SLL[C -> B -> A]

add_back (self, value: object) -> None:   This method adds a new node at the end of the list (right before the back sentinel). Example #1: list = LinkedList() print(list) list.add_back('C') list.add_back('B') list.add_back('A') print(list) Output: SLL[] SLL[C -> B -> A]

Page 5 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

insert_at_index (self, index: int, value: object) -> None:   This method adds 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 (not including sentinel nodes in this count), valid indices for this method are [0, N] inclusive. Example #1: list = LinkedList() test_cases = [(0, 'A'), (0, 'B'), (1, 'C'), (3, 'D'), (-1, 'E'), (5, 'F')] for index, value in test_cases: print('Insert of', value, 'at', index, ': ', end='') try: list.insert_at_index(index, value) print(list) except Exception as e: print(type(e)) Output: Insert of A at 0 : SLL [A] Insert of B at 0 : SLL [B -> A] Insert of C at 1 : SLL [B -> C -> A] Insert of D at 3 : SLL [B -> C -> A -> D] Insert of E at -1 : <class '__main__.SLLException'> Insert of F at 5 : <class '__main__.SLLException'>

Page 6 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

remove_front (self) -> None:   This method removes the first node from the list. If the list is empty, the method raises a custom “SLLException”. Code for the exception is provided in the skeleton file. Example #1: list = LinkedList([1, 2]) print(list) for i in range(3): try: list.remove_front() print('Successful removal', list) except Exception as e: print(type(e)) Output: SLL[1 -> 2] Successful removal SLL[2] Successful removal SLL[] <class '__main__.SLLException'>

Page 7 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

remove_back (self) -> None:   This method removes the last node from the list. If the list is empty, the method raises a custom “SLLException”. Code for the exception is provided in the skeleton file. Example #1: list = LinkedList() try: list.remove_back() except Exception as e: print(type(e)) list.add_front('Z') list.remove_back() print(list) list.add_front('Y') list.add_back('Z') list.add_front('X') print(list) list.remove_back() print(list) Output: <class '__main__.SLLException'> SLL [] SLL [X -> Y -> Z] SLL [X -> Y]

Page 8 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

remove_at_index (self, index: int) -> None:   This method removes the node from the list given its index. Index 0 refers to the beginning of the list. 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, valid indices for this method are [0, N - 1] inclusive. Example #1: list = LinkedList([1, 2, 3, 4, 5, 6]) print(list) for index in [0, 0, 0, 2, 2, -2]: print('Removed at index:', index, ': ', end='') try: list.remove_at_index(index) print(list) except Exception as e: print(type(e)) print(list) Output: SLL [1 -> 2 -> 3 -> 4 -> 5 -> 6] Removed at index: 0 : SLL [2 -> 3 -> 4 -> 5 -> 6] Removed at index: 0 : SLL [3 -> 4 -> 5 -> 6] Removed at index: 0 : SLL [4 -> 5 -> 6] Removed at index: 2 : SLL [4 -> 5] Removed at index: 2 : <class '__main__.SLLException'> Removed at index: -2 : <class '__main__.SLLException'> SLL [4 -> 5]

Page 9 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

get_front (self) -> object:   This method returns value from the first node in the list without removing it. If the list is empty, the method raises a custom “SLLException”. Code for the exception is provided in the skeleton file. Example #1: list = LinkedList(['A', 'B']) print(list.get_front()) print(list.get_front()) list.remove_front() print(list.get_front()) list.remove_back() try: print(list.get_front()) except Exception as e: print(type(e)) Output: A A B <class '__main__.SLLException'>

get_back (self) -> object:   This method returns value from the last node in the list without removing it. If the list is empty, the method raises a custom “SLLException”. Code for the exception is provided in the skeleton file. Example #1: list = LinkedList([1, 2, 3]) list.add_back(4) print(list.get_back()) list.remove_back() print(list) print(list.get_back()) Output: 4 SLL [1 -> 2 -> 3] 3

Page 10 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

remove (self, value: object) -> bool:   This method traverses the list from the beginning to the end and removes the first node in the list that matches the provided “value” object. Method returns True if some node was actually removed from the list. Otherwise it returns False. Example #1: list = LinkedList([1, 2, 3, 1, 2, 3, 1, 2, 3]) print(list) for value in [7, 3, 3, 3, 3]: print(list.remove(value), list.length(), list) Output: SLL [1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3] False 9 SLL [1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3] True 8 SLL [1 -> 2 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3] True 7 SLL [1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 3] True 6 SLL [1 -> 2 -> 1 -> 2 -> 1 -> 2] False 6 SLL [1 -> 2 -> 1 -> 2 -> 1 -> 2]

count (self, value: object) -> int:   This method counts the number of elements in the list that match the provided “value” object. Example #1: list = LinkedList([1, 2, 3, 1, 2, 2]) print(list, list.count(1), list.count(2), list.count(3), list.count(4)) Output: SLL [1 -> 2 -> 3 -> 1 -> 2 -> 2] 2 3 1 0

Page 11 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

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, valid start_index is in range [0, N - 1] inclusive. Runtime complexity of your implementation must be O(N). If the provided start index is invalid, or if there are not enough nodes between start index and end of the list to make the slice of requested size, this method raises a custom “SLLException”. Code for the exception is provided in the skeleton file. Example #1: list = LinkedList([1, 2, 3, 4, 5, 6, 7, 8, 9]) ll_slice = list.slice(1, 3) print(list, ll_slice, sep="\n") ll_slice.remove_at_index(0) print(list, ll_slice, sep="\n") Output: SLL [1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9] SLL [2 -> 3 -> 4] SLL [1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9] SLL [3 -> 4] Example #2: list = LinkedList([10, 11, 12, 13, 14, 15, 16]) print("SOURCE:", list) slices = [(0, 7), (-1, 7), (0, 8), (2, 3), (5, 0), (5, 3), (6, 1)] for index, size in slices: print("Slice", index, "/", size, end="") try: print(" --- OK: ", list.slice(index, size)) except: print(" --- exception occurred.") Output: SOURCE: SLL [10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16] Slice 0 / 7 --- OK: SLL [10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16] Slice -1 / 7 --- exception occurred. Slice 0 / 8 --- exception occurred. Slice 2 / 3 --- OK: SLL [12 -> 13 -> 14] Slice 5 / 0 --- OK: SLL [] Slice 5 / 3 --- exception occurred. Slice 6 / 1 --- OK: SLL [16]

Page 12 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

Part 2 - Summary and Specific Instructions

1. Implement a Stack ADT class by completing provided skeleton code in the file max_stack_sll.py . You will use the LinkedList data structure that you have implemented in part 1 of this assignment as underlying data storage for your Stack ADT.

2. Your Stack ADT implementation will include standard Stack methods and also one

new method - get_max(): push() pop() top() get_max()

3. We will test your implementation with different types of objects, not just integers. We guarantee that all such objects will have correct implementation of methods __eq__, __lt__, __gt__, __ge__, __le__ and __str__.

4. Number of objects stored in the Stack at any given time will be between 0 and 900 inclusive. Stack must allow for storage of duplicate objects.

5. RESTRICTIONS: You are not allowed to use ANY built-in Python data structures and their methods. You must solve this portion of the assignment by importing the LinkedList class that you wrote in part 1 and using class methods to write your solution. You are also not allowed to directly access any variables of the LinkedList or SLNode classes. All work must be done by only using class methods.

Page 13 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

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 = MaxStack() print(s) for value in [1, 2, 3, 4, 5]: s.push(value) print(s) Output: MAX STACK: 0 elements. SLL [] MAX STACK: 5 elements. SLL [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”. Example #1: s = MaxStack() 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 14 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

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”. Example #1: s = MaxStack() 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'> MAX STACK: 2 elements. SLL [20 -> 10] 20 20 MAX STACK: 2 elements. SLL [20 -> 10]

Page 15 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

get_max (self) -> object:   This method returns the maximum value currently stored in the stack. It must be implemented with O(1) runtime complexity. If the stack is empty, the method raises a custom “StackException”. Example #1: s = MaxStack() for value in [1, -20, 15, 21, 21, 40, 50]: print(s, ' ', end='') try: print(s.get_max()) except Exception as e: print(type(e)) s.push(value) while not s.is_empty(): print(s.size(), end='') print(' Pop value:', s.pop(), ' get_max after: ', end='') try: print(s.get_max()) except Exception as e: print(type(e)) Output: MAX STACK: 0 elements. SLL [] <class '__main__.StackException'> MAX STACK: 1 elements. SLL [1] 1 MAX STACK: 2 elements. SLL [-20 -> 1] 1 MAX STACK: 3 elements. SLL [15 -> -20 -> 1] 15 MAX STACK: 4 elements. SLL [21 -> 15 -> -20 -> 1] 21 MAX STACK: 5 elements. SLL [21 -> 21 -> 15 -> -20 -> 1] 21 MAX STACK: 6 elements. SLL [40 -> 21 -> 21 -> 15 -> -20 -> 1] 40 7 Pop value: 50 get_max after: 40 6 Pop value: 40 get_max after: 21 5 Pop value: 21 get_max after: 21 4 Pop value: 21 get_max after: 15 3 Pop value: 15 get_max after: 1 2 Pop value: -20 get_max after: 1 1 Pop value: 1 get_max after: <class '__main__.StackException'>

Page 16 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

Part 3 - Summary and Specific Instructions

1. Implement Deque and Bag ADT interfaces with a circular doubly linked list data structure by completing provided skeleton code in the file cdll.py . Once completed, your implementation will include the following methods:

Methods identical to Singly Linked List in Part 1: add_front(), add_back() insert_at_index() remove_front(), remove_back() remove_at_index() get_front(), get_back() remove() count() ** Note that you do not need to implement the slice() method. Additional methods: swap_pairs(), reverse(), sort() rotate(), remove_duplicates() odd_even()

2. We will test your implementation with different types of objects, not just integers. We guarantee that all such objects will have correct implementation of methods __eq__, __lt__, __gt__, __ge__, __le__ and __str__.

3. Number of objects stored in the list at any given time will be between 0 and 900, inclusive.

4. This implementation must be done with the use of a single sentinel node.

Page 17 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

5. Variables in t he DLNode and CircularList classes are not m arked as private. For this

portion of the assignment you are allowed to access and change their values directly. You 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 and their methods.

7. Methods get_front(), get_back(), add_front(), add_back(), remove_front() and remove_back() must be implemented so they have O(1) runtime complexity.

8. All methods that are identical names as in Part 1 must work the same way as methods you have implemented for a Singly Linked List in Part 1 of this assignment. Please refer to part 1 of this document for the detailed description of each method and its expected input and output values. Note that in case an exception needs to be raised, the name of the exception should be CDLLException, not SLLException. Code for the exception is provided in the skeleton file.

9. When using code examples provided in part 1 of this document, your list must be created from class CircularList, not from LinkedList. Also, note that __str__ method uses different characters for separating nodes (to reflect the fact that this is a Doubly Linked List).

For example, if a code sample from part 1 says:

list = LinkedList([1, 2, 3]) list.add_back(4) print(list) Output: SLL [1 -> 2 -> 3 -> 4] Then for purposes of part 3 you would change it as follows (also note a slightly different output format):

list = CircularList([1, 2, 3]) list.add_back(4) print(list) Output: CDLL [1 <-> 2 <-> 3 <-> 4]

Page 18 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

swap_pairs (self, index1: int, index2: int) -> None:   This method swaps two nodes given their indices. Swapping must be done by changing node pointers. You are not allowed to just swap values of the two nodes. If any of the provided indices is invalid, the method raises a custom “CDLLException”. If the linked list contains N nodes (not including sentinel nodes in this count), valid indices for this method are [0, N - 1] inclusive. Example #1: list = CircularList([0, 1, 2, 3, 4, 5, 6]) test_cases = ((0, 6), (0, 7), (-1, 6), (1, 5), (4, 2), (3, 3), (1, 2), (2, 1)) for i, j in test_cases: print('Swap nodes ', i, j, ' ', end='') try: list.swap_pairs(i, j) print(list) except Exception as e: print(type(e)) Output: Swap nodes 0 6 CDLL [6 <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 0] Swap nodes 0 7 <class '__main__.CDLLException'> Swap nodes -1 6 <class '__main__.CDLLException'> Swap nodes 1 5 CDLL [6 <-> 5 <-> 2 <-> 3 <-> 4 <-> 1 <-> 0] Swap nodes 4 2 CDLL [6 <-> 5 <-> 4 <-> 3 <-> 2 <-> 1 <-> 0] Swap nodes 3 3 CDLL [6 <-> 5 <-> 4 <-> 3 <-> 2 <-> 1 <-> 0] Swap nodes 1 2 CDLL [6 <-> 4 <-> 5 <-> 3 <-> 2 <-> 1 <-> 0] Swap nodes 2 1 CDLL [6 <-> 5 <-> 4 <-> 3 <-> 2 <-> 1 <-> 0]

Page 19 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

reverse (self) -> None:   This method reverses the order of the nodes in the list. The reversal must be done “in place” without creating any copies of existing nodes or an entire existing list. You are not allowed to swap values of the nodes, the solution must change node pointers. Your solution must have O(n) runtime complexity. You can use swap_pairs() method in your implementation, but only do so if you’re sure you can achieve O(n) for the overall solution. Example #1: test_cases = ( [1, 2, 3, 3, 4, 5], [1, 2, 3, 4, 5], ['A', 'B', 'C', 'D'] ) for case in test_cases: list = CircularList(case) list.reverse() print(list) Output: CDLL [5 <-> 4 <-> 3 <-> 3 <-> 2 <-> 1] CDLL [5 <-> 4 <-> 3 <-> 2 <-> 1] CDLL [D <-> C <-> B <-> A] Example #2: list = CircularList() print(list) list.reverse() print(list) list.add_back(2) list.add_back(3) list.add_front(1) list.reverse() print(list) Output: CDLL [] CDLL [] CDLL [3 <-> 2 <-> 1]

Page 20 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

Example #3: class Student: def __init__(self, name, age): self.name, self.age = name, age def __eq__(self, other): return self.age == other.age def __str__(self): return str(self.name) + ' ' + str(self.age) s1, s2 = Student('John', 20), Student('Andy', 20) list = CircularList([s1, s2]) print(list) list.reverse() print(list) print(s1 == s2) Output: CDLL [John 20 <-> Andy 20] CDLL [Andy 20 <-> John 20] True

Example #4: list = CircularList([1, 'A']) list.reverse() print(list) Output:

CDLL [A <-> 1]

Page 21 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

sort (self) -> None:   This method sorts the content of the list in non-descending order. The sorting must be done “in place” without creating any copies of existing nodes or an entire existing list. You are not allowed to swap values of the nodes, the solution must change node pointers. You can implement any sort method of your choice. Sorting does not have to be very efficient or fast, a simple insertion or bubble sort will suffice. However, runtime complexity of your implementation can not be worse than O(n^2). You can use swap_pairs() method in your implementation, but only do so if you’re sure you can achieve at least O(n^2) for the overall solution. Duplicates in the list can be placed in any relative order in the sorted list (in other words, your sort does not have to be ‘stable’). For this method, you may assume that elements stored in linked list are all of the same type (either all numbers, or strings, or custom objects, but never a mix of those). You do not need to write checks for this condition. Example #1: test_cases = ( [1, 10, 2, 20, 3, 30, 4, 40, 5], ['zebra2', 'apple', 'tomato', 'apple', 'zebra1'], [(1, 1), (20, 1), (1, 20), (2, 20)] ) for case in test_cases: list = CircularList(case) print(list) list.sort() print(list) Output: CDLL [1 <-> 10 <-> 2 <-> 20 <-> 3 <-> 30 <-> 4 <-> 40 <-> 5] CDLL [1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 10 <-> 20 <-> 30 <-> 40] CDLL [zebra2 <-> apple <-> tomato <-> apple <-> zebra1] CDLL [apple <-> apple <-> tomato <-> zebra1 <-> zebra2] CDLL [(1, 1) <-> (20, 1) <-> (1, 20) <-> (2, 20)] CDLL [(1, 1) <-> (1, 20) <-> (2, 20) <-> (20, 1)]

Page 22 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

rotate (self, steps: int) -> None:   This method ‘rotates’ the linked list by shifting positions of its elements right or left steps number of times. If steps is a positive integer, elements should be rotated right. Otherwise, rotation is to the left. All work must be done “in place” without creating any copies of existing nodes or an entire existing list. You are not allowed to swap values of the nodes, the solution must change node pointers. Solution’s time complexity must be O(N). Example #1: source = [_ for _ in range(-20, 20, 7)] for steps in [1, 2, 0, -1, -2, 28, -100]: list = CircularList(source) list.rotate(steps) print(list, steps) Output: CDLL [15 <-> -20 <-> -13 <-> -6 <-> 1 <-> 8] 1 CDLL [8 <-> 15 <-> -20 <-> -13 <-> -6 <-> 1] 2 CDLL [-20 <-> -13 <-> -6 <-> 1 <-> 8 <-> 15] 0 CDLL [-13 <-> -6 <-> 1 <-> 8 <-> 15 <-> -20] -1 CDLL [-6 <-> 1 <-> 8 <-> 15 <-> -20 <-> -13] -2 CDLL [-6 <-> 1 <-> 8 <-> 15 <-> -20 <-> -13] 28 CDLL [8 <-> 15 <-> -20 <-> -13 <-> -6 <-> 1] -100 Example #2: list = CircularList([10, 20, 30, 40]) for j in range(-1, 2, 2): for _ in range(3): list.rotate(j) print(list) Output: CDLL [20 <-> 30 <-> 40 <-> 10] CDLL [30 <-> 40 <-> 10 <-> 20] CDLL [40 <-> 10 <-> 20 <-> 30] CDLL [30 <-> 40 <-> 10 <-> 20] CDLL [20 <-> 30 <-> 40 <-> 10] CDLL [10 <-> 20 <-> 30 <-> 40] Example #3: list = CircularList() list.rotate(10) print(list) Output: CDLL []

Page 23 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

remove_duplicates (self) -> None:   This method deletes all nodes that have duplicate values from a sorted linked list, leaving only nodes with distinct values. All work must be done “in place” without creating any copies of existing nodes or an entire existing list. You are not allowed to change values of the nodes, the solution must change node pointers. Solution’s time complexity must be O(N). You may assume that the list is sorted, no need to write checks for that. You may also assume that all elements in the list are of the same type and can be compared with each other using a == operator. Example #1: test_cases = ( [1, 2, 3, 4, 5], [1, 1, 1, 1, 1], [], [1], [1, 1], [1, 1, 1, 2, 2, 2], [0, 1, 1, 2, 3, 3, 4, 5, 5, 6], list("abccd"), list("005BCDDEEFI") ) for case in test_cases: lst = CircularList(case) print('INPUT :', lst) lst.remove_duplicates() print('OUTPUT:', lst) Output: INPUT : CDLL [1 <-> 2 <-> 3 <-> 4 <-> 5] OUTPUT: CDLL [1 <-> 2 <-> 3 <-> 4 <-> 5] INPUT : CDLL [1 <-> 1 <-> 1 <-> 1 <-> 1] OUTPUT: CDLL [] INPUT : CDLL [] OUTPUT: CDLL [] INPUT : CDLL [1] OUTPUT: CDLL [1] INPUT : CDLL [1 <-> 1] OUTPUT: CDLL [] INPUT : CDLL [1 <-> 1 <-> 1 <-> 2 <-> 2 <-> 2] OUTPUT: CDLL [] INPUT : CDLL [0 <-> 1 <-> 1 <-> 2 <-> 3 <-> 3 <-> 4 <-> 5 <-> 5 <-> 6] OUTPUT: CDLL [0 <-> 2 <-> 4 <-> 6] INPUT : CDLL [a <-> b <-> c <-> c <-> d] OUTPUT: CDLL [a <-> b <-> d] INPUT : CDLL [0 <-> 0 <-> 5 <-> B <-> C <-> D <-> D <-> E <-> E <-> F <-> I] OUTPUT: CDLL [5 <-> B <-> C <-> F <-> I]

Page 24 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

odd_even (self) -> None:   This method regroups list nodes by first grouping all ODD nodes together followed by all EVEN nodes (references are to node numbers in the list, starting from 1, not their values). Please see code examples below for additional details. All work must be done “in place” without creating any copies of existing nodes or an entire existing list. You are not allowed to change values of the nodes, the solution must change node pointers. Solution’s time complexity must be O(N). Example #1: test_cases = ( [1, 2, 3, 4, 5], list('ABCDE'), [], [100], [100, 200], [100, 200, 300], [100, 200, 300, 400], [10, 'A', 20, 'B', 30, 'C', 40, 'D', 50, 'E'] ) for case in test_cases: lst = CircularList(case) print('INPUT :', lst) lst.odd_even() print('OUTPUT:', lst) Output: INPUT : CDLL [1 <-> 2 <-> 3 <-> 4 <-> 5] OUTPUT: CDLL [1 <-> 3 <-> 5 <-> 2 <-> 4] INPUT : CDLL [A <-> B <-> C <-> D <-> E] OUTPUT: CDLL [A <-> C <-> E <-> B <-> D] INPUT : CDLL [] OUTPUT: CDLL [] INPUT : CDLL [100] OUTPUT: CDLL [100] INPUT : CDLL [100 <-> 200] OUTPUT: CDLL [100 <-> 200] INPUT : CDLL [100 <-> 200 <-> 300] OUTPUT: CDLL [100 <-> 300 <-> 200] INPUT : CDLL [100 <-> 200 <-> 300 <-> 400] OUTPUT: CDLL [100 <-> 300 <-> 200 <-> 400] INPUT : CDLL [10 <-> A <-> 20 <-> B <-> 30 <-> C <-> 40 <-> D <-> 50 <-> E] OUTPUT: CDLL [10 <-> 20 <-> 30 <-> 40 <-> 50 <-> A <-> B <-> C <-> D <-> E]

Page 25 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

Part 4 - Summary and Specific Instructions

1. Implement a Queue ADT class by completing provided skeleton code in the file queue_from_stacks.py . You will use the MaxStack ADT that you have implemented in part 2 of this assignment as underlying data storage for your Queue ADT.

2. Your Queue ADT implementation will include the following methods:

enqueue() dequeue()

3. We will test your implementation with different types of objects, not just integers.

We guarantee that all such objects will have correct implementation of methods __eq__, __lt__, __gt__, __ge__, __le__ and __str__.

4. Number of objects stored in the Queue at any given time will be between 0 and 900 inclusive. Queue must allow for storage of duplicate elements.

5. RESTRICTIONS: You are not allowed to use ANY built-in Python data structures and their methods. You must solve this portion of the assignment by importing the MaxStack class that you wrote in part 2 and using class methods to write your solution. You are also not allowed to directly access any variables of the MaxStack class. All work must be done by only using class methods (push(), pop(), top(), size() and is_empty()). You don’t need to use the method get_max() in your implementation.

Page 26 of 27

CS261 Data Structures Project 3: Your Very Own Linked List

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) print(q) Output: QUEUE: 0 elements. MAX STACK: 0 elements. SLL [] QUEUE: 5 elements. MAX STACK: 5 elements. SLL [5 -> 4 -> 3 -> 2 -> 1]

dequeue (self) -> object:   This method removes and returns the value from the beginning of the queue. It must be implemented with the runtime complexity of not worse than O(n). 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(), q) except Exception as e: print("No elements in queue", type(e)) Output: QUEUE: 5 elements. MAX STACK: 5 elements. SLL [5 -> 4 -> 3 -> 2 -> 1] 1 QUEUE: 4 elements. MAX STACK: 4 elements. SLL [5 -> 4 -> 3 -> 2] 2 QUEUE: 3 elements. MAX STACK: 3 elements. SLL [5 -> 4 -> 3] 3 QUEUE: 2 elements. MAX STACK: 2 elements. SLL [5 -> 4] 4 QUEUE: 1 elements. MAX STACK: 1 elements. SLL [5] 5 QUEUE: 0 elements. MAX STACK: 0 elements. SLL [] No elements in queue <class '__main__.QueueException'>

Page 27 of 27