Single Linked List (Python)

Question

I'm following a tutorial on Single Linked List (SLL).

There are so many methods in the code, if you had time please feel free to review any part of it and I can work on it and repost it.

I'm especially interested in object-oriented, algorithms, design, logic, exception handling, and other programming side of it. Other developer-oriented issues such as variable namings, documenting, commenting, and such are not really a concern here since it's just for practicing algorithm and data structures, and have to follow the tutorial as much as possible.

Thanks so much for your time!

""" 🍎🍏🍎🍏🍎🍏🍎🍏🍎🍏🍎🍏🍎🍏🍎🍏 Single Linked List (SLL): A simple object-oriented implementation of Single Linked List (SLL) with some associated methods, such as create list, count nodes, delete nodes, and such. 🍎🍏🍎🍏🍎🍏🍎🍏🍎🍏🍎🍏🍎🍏🍎🍏 """ class Node: """ Instantiates a node """ def __init__(self, value): """ Node class constructor which sets the value and link of the node """ self.info = value self.link = None class SingleLinkedList: """ Instantiates the SLL class """ def __init__(self): """ SLL class constructor which sets the value and link of the node """ self.start = None def create_single_linked_list(self): """ Reads values from stdin and appends them to this list and creates a SLL with integer nodes """ try: number_of_nodes = int(input("👉 Enter a positive integer between 1-50 for the number of nodes you wish to have in the list: ")) if number_of_nodes <= 0 or number_of_nodes > 51: print("💛 The number of nodes though must be an integer between 1 to 50!") self.create_single_linked_list() except Exception as e: print("💛 Error: ", e) self.create_single_linked_list() try: for _ in range(number_of_nodes): try: data = int(input("👉 Enter an integer for the node to be inserted: ")) self.insert_node_at_end(data) except Exception as e: print("💛 Error: ", e) except Exception as e: print("💛 Error: ", e) def count_sll_nodes(self): """ Counts the nodes of the linked list """ try: p = self.start n = 0 while p is not None: n += 1 p = p.link if n >= 1: print(f"💚 The number of nodes in the linked list is {n}") else: print(f"💛 The SLL does not have a node!") except Exception as e: print("💛 Error: ", e) def search_sll_nodes(self, x): """ Searches the x integer in the linked list """ try: position = 1 p = self.start while p is not None: if p.info == x: print(f"💚 YAAAY! We found {x} at position {position}") return True #Increment the position position += 1 #Assign the next node to the current node p = p.link else: print(f"💔 Sorry! We couldn't find {x} at any position. Maybe, you might want to use option 9 and try again later!") return False except Exception as e: print("💛 Error: ", e) def display_sll(self): """ Displays the list """ try: if self.start is None: print("💛 Single linked list is empty!") return display_sll = "💚 Single linked list nodes are: " p = self.start while p is not None: display_sll += str(p.info) + "\t" p = p.link print(display_sll) except Exception as e: print("💛 Error: ", e) def insert_node_in_beginning(self, data): """ Inserts an integer in the beginning of the linked list """ try: temp = Node(data) temp.link = self.start self.start = temp except Exception as e: print("💛 Error: ", e) def insert_node_at_end(self, data): """ Inserts an integer at the end of the linked list """ try: temp = Node(data) if self.start is None: self.start = temp return p = self.start while p.link is not None: p = p.link p.link = temp except Exception as e: print("💛 Error: ", e) def insert_node_after_another(self, data, x): """ Inserts an integer after the x node """ try: p = self.start while p is not None: if p.info == x: break p = p.link if p is None: print(f"💔 Sorry! {x} is not in the list.") else: temp = Node(data) temp.link = p.link p.link = temp except Exception as e: print("💛 Error: ", e) def insert_node_before_another(self, data, x): """ Inserts an integer before the x node """ try: # If list is empty if self.start is None: print("💔 Sorry! The list is empty.") return # If x is the first node, and new node should be inserted before the first node if x == self.start.info: temp = Node(data) temp.link = p.link p.link = temp # Finding the reference to the prior node containing x p = self.start while p.link is not None: if p.link.info == x: break p = p.link if p.link is not None: print(f"💔 Sorry! {x} is not in the list.") else: temp = Node(data) temp.link = p.link p.link = temp except Exception as e: print("💛 Error: ", e) def insert_node_at_position(self, data, k): """ Inserts an integer in k position of the linked list """ try: # if we wish to insert at the first node if k == 1: temp = Node(data) temp.link = self.start self.start = temp return p = self.start i = 1 while i < k-1 and p is not None: p = p.link i += 1 if p is None: print(f"💛 The max position is {i}") else: temp = Node(data) temp.link = self.start self.start = temp except Exception as e: print("💛 Error: ", e) def delete_a_node(self, x): """ Deletes a node of a linked list """ try: # If list is empty if self.start is None: print("💔 Sorry! The list is empty.") return # If there is only one node if self.start.info == x: self.start = self.start.link # If more than one node exists p = self.start while p.link is not None: if p.link.info == x: break p = p.link if p.link is None: print(f"💔 Sorry! {x} is not in the list.") else: p.link = p.link.link except Exception as e: print("💛 Error: ", e) def delete_sll_first_node(self): """ Deletes the first node of a linked list """ try: if self.start is None: return self.start = self.start.link except Exception as e: print("💛 Error: ", e) def delete_sll_last_node(self): """ Deletes the last node of a linked list """ try: # If the list is empty if self.start is None: return # If there is only one node if self.start.link is None: self.start = None return # If there is more than one node p = self.start # Increment until we find the node prior to the last node while p.link.link is not None: p = p.link p.link = None except Exception as e: print("💛 Error: ", e) def reverse_sll(self): """ Reverses the linked list """ try: prev = None p = self.start while p is not None: next = p.link p.link = prev prev = p p = next self.start = prev except Exception as e: print("💛 Error: ", e) def bubble_sort_sll_nodes_data(self): """ Bubble sorts the linked list on integer values """ try: # If the list is empty or there is only one node if self.start is None or self.start.link is None: print("💛 The list has no or only one node and sorting is not required.") end = None while end != self.start.link: p = self.start while p.link != end: q = p.link if p.info > q.info: p.info, q.info = q.info, p.info p = p.link end = p except Exception as e: print("💛 Error: ", e) def bubble_sort_sll(self): """ Bubble sorts the linked list """ try: # If the list is empty or there is only one node if self.start is None or self.start.link is None: print("💛 The list has no or only one node and sorting is not required.") end = None while end != self.start.link: r = p = self.start while p.link != end: q = p.link if p.info > q.info: p.link = q.link q.link = p if p != self.start: r.link = q.link else: self.start = q p, q = q, p r = p p = p.link end = p except Exception as e: print("💛 Error: ", e) def sll_has_cycle(self): """ Tests the list for cycles using Tortoise and Hare Algorithm (Floyd's cycle detection algorithm) """ try: if self.find_sll_cycle() is None: return False else: return True except Exception as e: print("💛 Error: ", e) def find_sll_cycle(self): """ Finds cycles in the list, if any """ try: # If there is one node or none, there is no cycle if self.start is None or self.start.link is None: return None # Otherwise, slowR = self.start fastR = self.start while slowR is not None and fastR is not None: slowR = slowR.link fastR = fastR.link.link if slowR == fastR: return slowR return None except Exception as e: print("💛 Error: ", e) def remove_cycle_from_sll(self): """ Removes the cycles """ try: c = self.find_sll_cycle() # If there is no cycle if c is None: return print(f"💛 There is a cycle at node: ", c.info) p = c q = c len_cycles = 0 while True: len_cycles += 1 q = q.link if p == q: break print(f"💛 The cycle length is {len_cycles}") len_rem_list = 0 p = self.start while p != q: len_rem_list += 1 p = p.link q = q.link print(f"💛 The number of nodes not included in the cycle is {len_rem_list}") length_list = len_rem_list + len_cycles print(f"💛 The SLL length is {length_list}") # This for loop goes to the end of the SLL, and set the last node to None and the cycle is removed. p = self.start for _ in range(length_list-1): p = p.link p.link = None except Exception as e: print("💛 Error: ", e) def insert_cycle_in_sll(self, x): """ Inserts a cycle at a node that contains x """ try: if self.start is None: return False p = self.start px = None prev = None while p is not None: if p.info == x: px = p prev = p p = p.link if px is not None: prev.link = px else: print(f"💔 Sorry! {x} is not in the list.") except Exception as e: print("💛 Error: ", e) def merge_using_new_list(self, list2): """ Merges two already sorted SLLs by creating new lists """ merge_list = SingleLinkedList() merge_list.start = self._merge_using_new_list(self.start, list2.start) return merge_list def _merge_using_new_list(self, p1, p2): """ Private method of merge_using_new_list """ if p1.info <= p2.info: Start_merge = Node(p1.info) p1 = p1.link else: Start_merge = Node(p2.info) p2 = p2.link pM = Start_merge while p1 is not None and p2 is not None: if p1.info <= p2.info: pM.link = Node(p1.info) p1 = p1.link else: pM.link = Node(p2.info) p2 = p2.link pM = pM.link #If the second list is finished, yet the first list has some nodes while p1 is not None: pM.link = Node(p1.info) p1 = p1.link pM = pM.link #If the second list is finished, yet the first list has some nodes while p2 is not None: pM.link = Node(p2.info) p2 = p2.link pM = pM.link return Start_merge def merge_inplace(self, list2): """ Merges two already sorted SLLs in place in O(1) of space """ merge_list = SingleLinkedList() merge_list.start = self._merge_inplace(self.start, list2.start) return merge_list def _merge_inplace(self, p1, p2): """ Merges two already sorted SLLs in place in O(1) of space """ if p1.info <= p2.info: Start_merge = p1 p1 = p1.link else: Start_merge = p2 p2 = p2.link pM = Start_merge while p1 is not None and p2 is not None: if p1.info <= p2.info: pM.link = p1 pM = pM.link p1 = p1.link else: pM.link = p2 pM = pM.link p2 = p2.link if p1 is None: pM.link = p2 else: pM.link = p1 return Start_merge def merge_sort_sll(self): """ Sorts the linked list using merge sort algorithm """ self.start = self._merge_sort_recursive(self.start) def _merge_sort_recursive(self, list_start): """ Recursively calls the merge sort algorithm for two divided lists """ # If the list is empty or has only one node if list_start is None or list_start.link is None: return list_start # If the list has two nodes or more start_one = list_start start_two = self._divide_list(self_start) start_one = self._merge_sort_recursive(start_one) start_two = self._merge_sort_recursive(start_two) start_merge = self._merge_inplace(start_one, start_two) return start_merge def _divide_list(self, p): """ Divides the linked list into two almost equally sized lists """ # Refers to the third nodes of the list q = p.link.link while q is not None and p is not None: # Increments p one node at the time p = p.link # Increments q two nodes at the time q = q.link.link start_two = p.link p.link = None return start_two def concat_second_list_to_sll(self, list2): """ Concatenates another SLL to an existing SLL """ # If the second SLL has no node if list2.start is None: return # If the original SLL has no node if self.start is None: self.start = list2.start return # Otherwise traverse the original SLL p = self.start while p.link is not None: p = p.link # Link the last node to the first node of the second SLL p.link = list2.start def test_merge_using_new_list_and_inplace(self): """ """ LIST_ONE = SingleLinkedList() LIST_TWO = SingleLinkedList() LIST_ONE.create_single_linked_list() LIST_TWO.create_single_linked_list() print("1️⃣ The unsorted first list is: ") LIST_ONE.display_sll() print("2️⃣ The unsorted second list is: ") LIST_TWO.display_sll() LIST_ONE.bubble_sort_sll_nodes_data() LIST_TWO.bubble_sort_sll_nodes_data() print("1️⃣ The sorted first list is: ") LIST_ONE.display_sll() print("2️⃣ The sorted second list is: ") LIST_TWO.display_sll() LIST_THREE = LIST_ONE.merge_using_new_list(LIST_TWO) print("The merged list by creating a new list is: ") LIST_THREE.display_sll() LIST_FOUR = LIST_ONE.merge_inplace(LIST_TWO) print("The in-place merged list is: ") LIST_FOUR.display_sll() def test_all_methods(self): """ Tests all methods of the SLL class """ OPTIONS_HELP = """ 📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗 Select a method from 1-19: 🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒 ℹ️ (1) 👉 Create a single liked list (SLL). ℹ️ (2) 👉 Display the SLL. ℹ️ (3) 👉 Count the nodes of SLL. ℹ️ (4) 👉 Search the SLL. ℹ️ (5) 👉 Insert a node at the beginning of the SLL. ℹ️ (6) 👉 Insert a node at the end of the SLL. ℹ️ (7) 👉 Insert a node after a specified node of the SLL. ℹ️ (8) 👉 Insert a node before a specified node of the SLL. ℹ️ (9) 👉 Delete the first node of SLL. ℹ️ (10) 👉 Delete the last node of the SLL. ℹ️ (11) 👉 Delete a node you wish to remove. ℹ️ (12) 👉 Reverse the SLL. ℹ️ (13) 👉 Bubble sort the SLL by only exchanging the integer values. ℹ️ (14) 👉 Bubble sort the SLL by exchanging links. ℹ️ (15) 👉 Merge sort the SLL. ℹ️ (16) 👉 Insert a cycle in the SLL. ℹ️ (17) 👉 Detect if the SLL has a cycle. ℹ️ (18) 👉 Remove cycle in the SLL. ℹ️ (19) 👉 Test merging two bubble-sorted SLLs. ℹ️ (20) 👉 Concatenate a second list to the SLL. ℹ️ (21) 👉 Exit. 📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗 """ self.create_single_linked_list() while True: print(OPTIONS_HELP) UI_OPTION = int(input("👉 Enter an integer for the method you wish to run using the above help: ")) if UI_OPTION == 1: data = int(input("👉 Enter an integer to be inserted at the end of the list: ")) x = int(input("👉 Enter an integer to be inserted after that: ")) self.insert_node_after_another(data, x) elif UI_OPTION == 2: self.display_sll() elif UI_OPTION == 3: self.count_sll_nodes() elif UI_OPTION == 4: data = int(input("👉 Enter an integer to be searched: ")) self.search_sll_nodes(data) elif UI_OPTION == 5: data = int(input("👉 Enter an integer to be inserted at the beginning: ")) self.insert_node_in_beginning(data) elif UI_OPTION == 6: data = int(input("👉 Enter an integer to be inserted at the end: ")) self.insert_node_at_end(data) elif UI_OPTION == 7: data = int(input("👉 Enter an integer to be inserted: ")) x = int(input("👉 Enter an integer to be inserted before that: ")) self.insert_node_before_another(data, x) elif UI_OPTION == 8: data = int(input("👉 Enter an integer for the node to be inserted: ")) k = int(input("👉 Enter an integer for the position at which you wish to insert the node: ")) self.insert_node_before_another(data, k) elif UI_OPTION == 9: self.delete_sll_first_node() elif UI_OPTION == 10: self.delete_sll_last_node() elif UI_OPTION == 11: data = int(input("👉 Enter an integer for the node you wish to remove: ")) self.delete_a_node(data) elif UI_OPTION == 12: self.reverse_sll() elif UI_OPTION == 13: self.bubble_sort_sll_nodes_data() elif UI_OPTION == 14: self.bubble_sort_sll() elif UI_OPTION == 15: self.merge_sort_sll() elif UI_OPTION == 16: data = int(input("👉 Enter an integer at which a cycle has to be formed: ")) self.insert_cycle_in_sll(data) elif UI_OPTION == 17: if self.sll_has_cycle(): print("💛 The linked list has a cycle. ") else: print("💚 YAAAY! The linked list does not have a cycle. ") elif UI_OPTION == 18: self.remove_cycle_from_sll() elif UI_OPTION == 19: self.test_merge_using_new_list_and_inplace() elif UI_OPTION == 20: list2 = self.create_single_linked_list() self.concat_second_list_to_sll(list2) elif UI_OPTION == 21: break else: print("💛 Option must be an integer, between 1 to 21.") print() if __name__ == '__main__': # Instantiates a new SLL object SLL_OBJECT = SingleLinkedList() SLL_OBJECT.test_all_methods() 

Answer 1

Other developer-oriented issues such as variable namings, documenting, commenting, and such are not really a concern here since it's just for practicing algorithm and data structures, and have to follow the tutorial as much as possible.

I feel this is a bad idea, this is as it promotes detrimental core habits.

Myself and a friend used to play a purely skill based game. You had to click circles at specific points in time. My friend had discipline and decided to laboriously focus on improving their accuracy by playing on the easiest levels until they could reasonably 100% any easy level. After this they played harder and harder levels, focusing on building one skill at a time. They became one of the best at this game in the world.

I however found the easy levels boring, and decided to skip to harder levels. I would on average get 80%-90% when we were playing some of the easier levels together. But as my friend progressed this dropped to an average of 60%, it seemed nearly impossible to get higher or lower than this.

This is the same with programming. When you get in the zone you want to stay in it for the maximum amount of time. However if you don't have core skills then you'll likely trip up and leave it. This can be as simple as hitting a road block where you need to think of a name, and the more it takes to get the name you want the more you've left the zone. And then you have to build up to get in that zone again.

As for the code

I think adding hearts is 'cute', and if this were a professional project I'd recommend they go away. Currently however they look like there's no clear standard on what should be green, orange or red.

print("💛 Single linked list is empty!") print("💛 Error: ", e) 

Personally I'd make a couple of functions info, warn and error that print the message with the correct heart prepended. This could be something simple like:

def info(*args, sep=None, **kwargs): print('💚', *args, **kwargs) 

• create_single_linked_list should be a class method. This is as it is creating the linked list, and so you should be initializing the LL in the function.
• create_single_linked_list shouldn't have printing in it, and it shouldn't have any reading input from users. This is not what a Linked List does, this is something independent of the linked list.

• Don't use recursion unless you know it's reasonably safe. Python limits how deep a function call stack can be, and so this is like creating a bomb. You never know when your code may just break.

  There's ways to increase this limit, but I'd advise against them as they don't solve the problem. It's like having bomb defuser hide bombs in the middle of nowheer. Sure it's less likely to kill anybody, but there's still a chance.

• The lack of magic methods is very alarming. What's the point in making an abstract data type, if you can't even use it via standard means?

• Adding an __iter__ magic method would make the majority of your functions very simple. You could define search_sll_nodes (which is a very poor name) as simply return x in iter(self). You could make count_sll_nodes, return sum(1 for _ in self).

  This is a large oversight, and makes the code longer and harder to understand for seemingly no reason.

• except Exception as e: print("💛 Error: ", e) is really bad form. You shouldn't be ignoring potentially fatal errors in your linked list class. This is just another example on how your code has merged the calling code with the linked list implementation.

  Also the pure magnitude of these makes me either think you have the worlds most error prone linked list, in which case you should probably focus on fixing the issues you have. Or that your code is just an example of the boy who cried wolf. Are there actually any errors here, or will the calling code handle the issue if I allow it to propagate?

  Either way I'd get rid of most of them.

• You can implement pretty much everything you need by inheriting collections.abc.MutableSequence.

I would go through the code in more depth, but I'm only a tenth of the way through and I've come to the conclusion that I'd be rewriting the entire of your code as you've not decoupled your user interactions from your implementation.

Conclusion

You should implement the entire linked list again, I'd advise inheriting from MutableSequence to ease the creation of this list.

Your main code should be built in a way that you can test a list and your SingleLinkedList. This has the benefit that you can make a DoubleLinkedList and not have to duplicate nearly a thousand lines, which is long.