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: 
🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒
 i️ (1) 👉 Create a single liked list (SLL).
 i️ (2) 👉 Display the SLL. 
 i️ (3) 👉 Count the nodes of SLL. 
 i️ (4) 👉 Search the SLL.
 i️ (5) 👉 Insert a node at the beginning of the SLL.
 i️ (6) 👉 Insert a node at the end of the SLL.
 i️ (7) 👉 Insert a node after a specified node of the SLL.
 i️ (8) 👉 Insert a node before a specified node of the SLL.
 i️ (9) 👉 Delete the first node of SLL.
 i️ (10) 👉 Delete the last node of the SLL.
 i️ (11) 👉 Delete a node you wish to remove. 
 i️ (12) 👉 Reverse the SLL.
 i️ (13) 👉 Bubble sort the SLL by only exchanging the integer values. 
 i️ (14) 👉 Bubble sort the SLL by exchanging links. 
 i️ (15) 👉 Merge sort the SLL.
 i️ (16) 👉 Insert a cycle in the SLL.
 i️ (17) 👉 Detect if the SLL has a cycle.
 i️ (18) 👉 Remove cycle in the SLL.
 i️ (19) 👉 Test merging two bubble-sorted SLLs.
 i️ (20) 👉 Concatenate a second list to the SLL. 
 i️ (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()

• greybeard: Seeing it's been seven weeks, this would be a great time to revise the code and post a follow-on question.

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.