CSE331 Project 1: Doubly Linked Lists & Recursion Solution

This is not a team project, do not copy someone else’s work.

Assignment Overview
Linked Lists
A Linked List is a sequence data structure that provides association between objects through links.

Singly linked list implementation
A well known current application of this is within the blockchain space. In a more general sense, you could think of a music playlist as a doubly linked list where each song is a node and there is a previous and next option as the links to navigate to each neighboring song in the playlist.
Linked Lists have underlying applications in abstract data structures such as trees and graphs (upcoming projects!). They are relatively simple to implement and provide easy insertions and deletions by managing pointers that does not require shifting elements like an array does. Because a linked list can increase and decrease on runtime, it only allocates memory when needed providing no memory wastage.
Project
You will be creating a cyclic doubly linked list. In this context, cyclic refers to the list forming a circular dependency or in other words forming a circle/cycle.
This will represent the underlying implementation of a c++ List. I implore you to look at the core code that c++ uses for their list and use this to help you in your project. You can find an example of this here: STL_List. Download this page, and open it up in an editor. This is not necessary, but can be helpful and pretty interesting.
This is what our data looks like. Here, we have a root node that provides access to the front and back of the list.

Doubly linked list implementation
Recursion
Recursion is a technique that involves a function calling itself directly or indirectly. You will be implementing recursive functions within your List class when specified.

Fun Fact: Type the word "recursion" into google. It is spelled correctly, but still says "Did you mean: recursion". When you click on it, the page will redirect to the same page. This resembles an infinite loop and exemplifies the meaning of recursion!

Turning It In
Be sure to submit your project as a zipped folder named "Project1" and include inside:
List.py, a Python3 file
Node.py, a Python3 file
__init__.py, a Python3 file
README.txt, a text file that includes:
Your name
Feedback on the project
How long it took to complete
Resources used

Assignment Notes
Docstrings have been provided for you in this project only. Refer back to this project in order to reference how functions should be documented (description + parameter(s) + return).
Test cases will not test mismatching types. Example: List(container=[1, "a"]), and they should be able to handle any defined type as they are type-agnostic.
The methods below are given in a suggested logical order of implementation. Hint: perhaps you can utilize some methods presented earlier in the later...
Types:
T: Generic Type c++ List nodes' values are type-agnostic and also homogenous in type
Node: DoublyLinkedListNode ... types? What is Python Typing??
Mimics strongly typed languages such as C++ and Java, but does not enforce the types (new in Python 3.5) Example: def foo(var: Generic[T]) -> int:
This indicates we have a template parameter type of T with an int type as the return
Benefits: aids in debugging by indicating mismatching types for parameters and returns. It also provides cleaner code and documentation.
For those of you who use LeetCode's Python3 IDE this should look familiar Try this out on your own and reference the starter code for more clarity Resources to learn more about Python Typing:
1. Python Typing Docs
2. Real Python - Good descriptive analysis
3. Generics
Inner Functions:
We will be utilizing inner functions within some methods:
def foo(x): def inner_foo():
print(x) # I can access x!
inner_foo()
Fibonacci Example (not very practical, but relatable): def fib(n):
def inner_fib(num): if num <= 1: return num
return inner_fib(num - 1) + inner_fib(num - 2) return inner_fib(n)
Additional reference: Real Python - Inner Functions

Assignment Specifications
class SinglyLinkedListNode:
DO NOT MODIFY this class
Attributes val: value of self nxt: SinglyLinkedListNode - links next node
__init__(self, val, nxt=None)
val: T
nxt: SinglyLinkedListNode
Assigns value of val and next node of nxt
__str__(self)
Representation of val as a string Return: str
__repr__(self)
Representation as a string utilizing __str__ Return: str
__eq__(self, other) other: SinglyLinkedListNode
Compares this node for equality with another node by evaluating each val Return: bool
class DoublyLinkedListNode(SinglyLinkedListNode):
DO NOT MODIFY this class
Attribute prev: DoublyLinkedListNode - links previous node
__init__(self, val, nxt=None, prev=None)
val: T
nxt: DoublyLinkedListNode prev: DoublyLinkedListNode
Assigns value of val, next node of nxt, and the previous node of prev
Calls upon the constructor of its super class, SinglyLinkedListNode to assign val and nxt
Note: Doubly Linked List Node derives from Singly Linked List Node to emphasize differences and overlaps between the two class List:
Represents an adaptation of a the c++ List implementation with the underlying data structure being a cyclic doubly linked list
DO NOT MODIFY the following attribute/functions
Root node having a value of None
Serves as the head and tail as well as the access point for the lists' nodes
Note: The root is not identified by the value of None. Any node can technically have a value of None. The root is identified by reference using the keyword "is"
example: node is self.node
__init__(self, num=None, val=None, container=None)
num: int val: T
container: Python list containing elements of T type
Creates root node and sets its prev and next member variable to itself
Assigns list with param values given (see assign method below for num, val, and container parameter meanings) Time Complexity: O(n) --> parameter n
__repr__(self)
Represents the list as a string utilizing __str__ Return: str
Time Complexity: O(N)
__eq__(self, other)
Compares this List for equality with another List
Return: bool
Time Complexity: O(min(N, M)) --> M is size of other assign(self, num=None, val=None, container=None)
container: Python list containing elements of T type Populates self with nodes using the given parameters num represents the number of occurrences of val to assign to list. If val is not given, None is used.
container is used to generate nodes based on its contents Only valid combinations of use: assign(num) assign(num, val) assign(container)
Note: This method is mainly used for testing or in other words to quickly generate nodes for a List. Take a look at the code given in the __init__ as well as the visible testcases to understand more Time Complexity: O(len(container)) || O(num)
Resets list by reassigning root nodes' references to itself Time Complexity: O(1)
IMPLEMENT the following functions
empty(self)
Return: bool - if List contains any additional nodes other than the root node, return False else True
Time Complexity: O(1) front(self)
Return: Node - first node in the list or root node if empty
Time Complexity: O(1) back(self)
Return: Node - last node in the list or root node if empty
Time Complexity: O(1) swap(self, x)
x: List
Swaps contents of lists
Hint: what holds references to all the nodes in a List? Time Complexity: O(1)
__str__(self)
MUST BE WRITTEN RECURSIVELY Must call inner function to_string(node) which is to be implemented recursively
Represents the list as a string
1 <-> 2 <-> ... i.e., node.val <-> node.val <-> ... Return: str
Time Complexity: O(N^2) ... python strings are immutable, think about string concatenation's time complexity.
size(self)
MUST BE WRITTEN RECURSIVELY Must call inner function size_list(node) which is to be implemented recursively Return: int - size of list or number of nodes not including the root node
Time Complexity: O(N) insert(self, position, val, num=1) position: Node val: T num: int
MUST BE WRITTEN RECURSIVELY
Places node before given position node with a val of val
When num is given, insert num occurrences of node
Return: Node - node that points to the first of the newly inserted nodes
Time Complexity: O(num) erase(self, first, last=None) first: Node
last: Node
Erases node or nodes in list from first to, but not including last: [first, last). When last is not given, erase only first node Return: Node - node that followed the last node erased
Example: 0 <-> 1 <-> 2 first = Node(1) --> 0 <-> 2 return node 2
first = Node(1) , last = Node(2) --> 0 <-> 2 return node 2
Time Complexity: O(1) push_front(self, val) val: T
Inserts new Node with value of val in the front of the list Time Complexity: O(1)
push_back(self, val) val: T
Inserts new Node with value of val in the back of the list Time Complexity: O(1)
pop_front(self)
Erases Node in the front of the list Time Complexity: O(1)
pop_back(self)
Erases Node in the back of the list
Time Complexity: O(1) remove(self, val) val: T
MUST BE WRITTEN RECURSIVELY Must call inner function remove_node(node) which is to be implemented recursively Removes all nodes in the List containing a value of val
CANNOT call erase
Time Complexity: O(N)
remove_if(self, pred) pred: Predicate function
Simply said, a predicate function is a function that returns a bool. In this instance, it is a unary predicate that takes in one parameter.
Feel free to create your own predicate functions in testing & google them. Also, reference the visible test case.
Example: pred(node.val)
Click here to learn more.
MUST BE WRITTEN RECURSIVELY Must call inner function remove_if(node) which is to be implemented recursively Removes all Nodes when pred returns True
CANNOT call erase
Time Complexity: O(N)
MUST BE WRITTEN RECURSIVELY Must call inner function reverse_list(node) which is to be implemented recursively Reverses linked list in place, without using additional memory or in other words the addition of new List/Node objects.
Time Complexity: O(N)
MUST BE WRITTEN RECURSIVELY Must call inner function unique_list(node) which is to be implemented recursively Removes all but one element from every consecutive group of equal elements in the container Examples:
1 <-> 1 <-> 2 <-> 1 results in 1 <-> 2 <-> 1
5 <-> 3 <-> 2 <-> 2 <-> 3 <-> 3 <-> 3 results in 5 <-> 3 <-> 2 <-> 3 CANNOT call erase
Time Complexity: O(N)

Application
You are a co-creator of a music player app, and there is a bug in your code that corrupted some users' playlists and left others untouched. As mentioned earlier, a music playlist can be a representation of a doubly linked list.
There are three ways this bug affected your doubly linked lists*:
1. Proper - no change
2. Broken - unconnected Linked List that is linear

3. Improper - creates an incorrect cycle

*Proper, broken and improper are names created just for this context and do not represent terms for linked lists in general

Task: Create a program using Floyd's Cycle Finding Algorithm that will correct the given playlists by fixing the linked lists that do not make a cycle (2), or identifying those linked lists that create incorrect circular dependencies (3) to let your co-creator fix those with his program.
Floyd's Cycle Finding Algorithm
Simple algorithm that uses two pointers, slow and fast in order to detect a cycle in a linked list. The slow moves at an increment of one node, while the fast moves at an increment of two. The nodes will either reach the end of the list or will run into each other confirming a cyclic linked list.

For our application problem, this is an example of how floyd's algorithm could identify an improper linked list.
Wiki Resource on Floyd's Algorithm
Video on Floyd's Algorithm

fix_playlist(lst)
lst: List
Must call inner function fix_playlist_helper(slow, fast) which MUST BE WRITTEN RECURSIVELY Checks if the given lst is proper(1), broken(2), or improper(3)
It is broken when there is no cycle
It is improper when lst forms a cycle with a node other than the root node If proper or broken, return True. If improper, return False
MUST
fix Lists that are broken in place
use Floyd's Cycle Finding Algorithm (above)
CANNOT
call any List methods create any new Nodes or Lists
read prev values on nodes, you can only assign them example that is not allowed: if lst.node.prev is None
Note1 : Fixing an improper list was not included in order to reduce the problem's difficulty level. I would suggest looking it up if you are curious on the possible implementations for this.
Return: bool
Time Complexity: O(N)

Grading
Visible / Hidden Tests: __/80
Time Complexity: __/18 front, back, swap, empty, push_front, push_back, pop_front, pop_back: 0.5 each (4 total) size, string, insert, erase: 1 each (4 total)
remove, remove_if, reverse, unique, fix_playlist : 2 each (10 total) README Included: __/2

Project designed by Anna De Biasi