Merging Two Bubble Sorted Linked Lists (Python)

Question

I'm following a tutorial on merging two bubble-sorted Single Linked Lists in Python.

• merge1 creates a new list and does the merging.

---

Other than naming conventions which are not the best and I'm just following the tutorial, any feedback would be appreciated. OOP, practical time-complexity, algorithms, and others.

class Node:
 # Instantiates the node class
 def __init__(self, value):
 self.info = value
 self.link = None
class SingleLinkedList:
 # Instantiates the single linked list class
 def __init__(self):
 self.start = None
 # Creates the single linked list
 def create_list(self):
 n = int(input("Enter the number of nodes in the list you wish to create: "))
 if n == 0:
 return
 for i in range(n):
 data = int(input("Enter the element to be inserted: "))
 self.insert_at_end(data)
 # Counts the nodes of the single linked list
 def count_nodes(self):
 p = self.start
 n = 0
 while p is not None:
 n += 1
 p = p.link
 print("💚 The number of nodes in single linked list is: " + str(n))
 # Searches the x integer in the linked list
 def search(self, x):
 position = 1
 p = self.start
 while p is not None:
 if p.info == x:
 print("💚 YAAAY! We found " + str(x) + " at position " + str(position))
 return True
 # Increment the position
 position += 1 
 # Assign the next node to the current node
 p = p.link
 else:
 print("💔 Sorry! We couldn't find " + str(x) + " at any position. Maybe, try again later!")
 return False
 # Displays the list
 def display_list(self):
 if self.start is None:
 print("💛 Single linked list is empty!")
 return
 else:
 print("💚 Single linked list includes: ")
 p = self.start
 while p is not None:
 print(p.info, " ", end=' ')
 p = p.link
 print()
 # Inserts an integer in the beginning of the linked list
 def insert_in_beginning(self, data):
 temp = Node(data)
 temp.link = self.start
 self.start = temp
 # Inserts an integer at the end of the linked list
 def insert_at_end(self, data):
 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
 # Inserts an integer after the x node
 def insert_after(self, data, x):
 p = self.start
 while p is not None:
 if p.info == x:
 break
 p = p.link
 if p is None:
 print("💔 Sorry! " + str(x) + " is not in the list.")
 else:
 temp = Node(data)
 temp.link = p.link
 p.link = temp
 # Inserts an integer before the x node
 def insert_before(self, data, x):
 # 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("💔 Sorry! " + str(x) + " is not in the list.")
 else:
 temp = Node(data)
 temp.link = p.link
 p.link = temp 
 # Inserts an integer in k position of the linked list
 def insert_at_position(self, data, k):
 # 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("💛 The max position is: " + i) 
 else: 
 temp = Node(data)
 temp.link = self.start
 self.start = temp
 # Deletes a node of a linked list
 def delete_node(self, x):
 # 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("💔 Sorry! " + str(x) + " is not in the list.")
 else:
 p.link = p.link.link
 # Deletes the first node of a linked list
 def delete_first_node(self):
 if self.start is None:
 return
 self.start = self.start.link
 # Deletes the last node of a linked list
 def delete_last_node(self):
 # 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 
 # Reverses the linked list
 def reverse_list(self):
 prev = None
 p = self.start
 while p is not None:
 next = p.link
 p.link = prev
 prev = p
 p = next
 self.start = prev
 # Bubble sorts the linked list with respect to data
 def bubble_sort_exdata(self):
 # 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
 # Bubble sorts the linked list with respect to links
 def bubble_sort_exlinks(self):
 # 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
 #Merges two already sorted single linked lists by creating new lists
 def merge1(self, list2):
 merge_list = SingleLinkedList()
 merge_list.start = self._merge1(self.start, list2.start)
 return merge_list
 def _merge1(self, p1, p2):
 if p1.info <= p2.info:
 StartM = Node(p1.info)
 p1 = p1.link
 else:
 StartM = Node(p2.info)
 p2 = p2.link 
 pM = StartM
 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 StartM
# Testing
list1 = SingleLinkedList()
list2 = SingleLinkedList()
list1.create_list()
list2.create_list()
list1.bubble_sort_exdata()
list2.bubble_sort_exdata()
print("1️⃣ The first list is: ")
list1.display_list()
print("2️⃣ The second list is: ")
list2.display_list()
list3 = list1.merge1(list2)
print("The merged list by creating a new list is: ")
list3.display_list()

Output

1️⃣ The first list is: 
💚 Single linked list includes: 
1 1 1 2 3 
2️⃣ The second list is: 
💚 Single linked list includes: 
1 3 6 6 
The merged list by creating a new list is: 
💚 Single linked list includes: 
1 1 1 1 2 3 3 6 6 

• dfhwze: where is merge2 ? :( 💔
• dfhwze: Ah ok, I was about to add the comparative review tag, but it's no longer required. By the way, I'm out of votes :s

Answer 1

Docstrings

You should have a docstring at the beginning of every module, class, and method you write. This will allow documentation to identify what your code is supposed to do. You're on the right track, having comments above the classes and methods. Now, just move those comments inside these classes and methods at the very beginning, inside triple quote comments (""" ... """). I've gone and done this for you.

Meaningful Variable Naming

You have many variables like p, q, x, k, etc. While this may be convenient for sorting algorithms, you should provide more meaningful names for these variables.

_ for unused loop variable(s)

You have this code:

for i in range(n):
 data = int(input("Enter the element to be inserted: "))
 self.insert_at_end(data)

You don't use the i at all in this loop. You should use a _ instead. This makes it clear that the loop variable is to be ignored. The loop should now look like this:

for _ in range(n):
 data = int(input("Enter the element to be inserted: "))
 self.insert_at_end(data)

String Concatenation / Formatting

You have this code all throughout your program:

print("💚 The number of nodes in single linked list is: " + str(n))
print("💚 YAAAY! We found " + str(x) + " at position " + str(position))
print("💔 Sorry! " + str(x) + " is not in the list.")
...

Changing the type of the variable to a string, then adding it to the string, is unnecessary. You can simply use f"" or "".format() to directly incorporate these variables into your strings, without having to type cast them. Here are both ways:

f""

print(f"💚 The number of nodes in single linked list is: {n}")
print(f"💚 YAAAY! We found {x} at position {position}")
print(f"💔 Sorry! {x} is not in the list.")

"".format()

print("💚 The number of nodes in single linked list is: {}".format(n))
print("💚 YAAAY! We found {} at position {}".format(x, position))
print("💔 Sorry! {} is not in the list.".format(x))

Personally, I go with f"" because it makes the code cleaner, and allows me to see exactly what variables are in the string, without having to call .format() at the end. I use this in the updated version of your code at the bottom of this answer, but you can choose.

Unreachable Code

Here is your search method:

def search(self, x):
 position = 1
 p = self.start
 while p is not None:
 if p.info == x:
 print("💚 YAAAY! We found " + str(x) + " at position " + str(position))
 return True
 # Increment the position
 position += 1 
 # Assign the next node to the current node
 p = p.link
 else:
 print("💔 Sorry! We couldn't find " + str(x) + " at any position. Maybe, try again later!")
 return False

After you return True, it exits this method. So, the four lines of code after never get run. Ever. This code should be removed. The else is also unnecessary; I speak on that in the next section.

Unnecessary else after return

After you return something in a body of an if, you don't need an else. If the if isn't executed, it will automatically go to the next code, which will execute that code. Take your display_list method:

def display_list(self):
 if self.start is None:
 print("💛 Single linked list is empty!")
 return
 else:
 print("💚 Single linked list includes: ")
 p = self.start
 while p is not None:
 print(p.info, " ", end=' ')
 p = p.link
 print()

Since you return in the initial if statement, the else is unnecessary. That code won't be run if the if is True, since the method will be exited after the return statement. This method should now look like this:

def display_list(self):
 if self.start is None:
 print("💛 Single linked list is empty!")
 return
 print("💚 Single linked list includes: ")
 p = self.start
 while p is not None:
 print(p.info, " ", end=' ')
 p = p.link
 print()

Redefining built in keywords

You have a variable named next in your code. Since this is a name of a function in the Python Standard Library, it should be avoided. You shouldn't use built in keywords as variable names. They can cause collision and other errors in your code. You can use a text editor such as Sublime Text 3, which will highlight these words at built in keywords.

Constant Variable Naming

Constants in your program should be UPPER_CASE, to identify them as such.

Updated Code

"""
Method Docstring
A description of your program goes here
"""
class Node:
 """
 Node Class Docstring
 A description of this class goes here
 """
 def __init__(self, value):
 """
 Instantiates the node class
 """
 self.info = value
 self.link = None
class SingleLinkedList:
 """
 SingleLinkedList Class Docstring
 A description of this class goes here
 """
 def __init__(self):
 """
 Instantiates the single linked list class
 """
 self.start = None
 def create_list(self):
 """
 Creates the single linked list
 """
 num_nodes = int(input("Enter the number of nodes in the list you wish to create: "))
 if num_nodes == 0:
 return
 for _ in range(num_nodes):
 data = int(input("Enter the element to be inserted: "))
 self.insert_at_end(data)
 def count_nodes(self):
 """
 Counts the nodes of the single linked list
 """
 start = self.start
 count = 0
 while start is not None:
 count += 1
 start = start.link
 print(f"💚 The number of nodes in single linked list is: {count}")
 def search(self, number):
 """
 Searches the x integer in the linked list
 """
 position = 1
 start = self.start
 while start is not None:
 if start.info == number:
 print(f"💚 YAAAY! We found {number} at position {position}")
 return True
 print(f"💔 Sorry! We couldn't find {number} at any position. Maybe, try again later!")
 return False
 def display_list(self):
 """
 Displays the list
 """
 if self.start is None:
 print("💛 Single linked list is empty!")
 return
 print("💚 Single linked list includes: ")
 start = self.start
 while start is not None:
 print(start.info, " ", end=' ')
 start = start.link
 print()
 def insert_in_beginning(self, data):
 """
 Inserts an integer in the beginning of the linked list
 """
 temp = Node(data)
 temp.link = self.start
 self.start = temp
 def insert_at_end(self, data):
 """
 Inserts an integer at the end of the linked list
 """
 temp = Node(data)
 if self.start is None:
 self.start = temp
 return
 start = self.start
 while start.link is not None:
 start = start.link
 start.link = temp
 def insert_after(self, data, number):
 """
 Inserts an integer after the x node
 """
 start = self.start
 while start is not None:
 if start.info == number:
 break
 start = start.link
 if start is None:
 print(f"💔 Sorry! {number} is not in the list.")
 else:
 temp = Node(data)
 temp.link = start.link
 start.link = temp
 def insert_before(self, data, number):
 """
 Inserts an integer before the x node
 """
 # 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 number == self.start.info:
 temp = Node(data)
 temp.link = number.link
 number.link = temp
 # Finding the reference to the prior node containing x
 start = self.start
 while start.link is not None:
 if start.link.info == number:
 break
 start = start.link
 if start.link is not None:
 print(f"💔 Sorry! {number} is not in the list.")
 else:
 temp = Node(data)
 temp.link = start.link
 start.link = temp
 def insert_at_position(self, data, pos):
 """
 Inserts an integer in k position of the linked list
 """
 # if we wish to insert at the first node
 if pos == 1:
 temp = Node(data)
 temp.link = self.start
 self.start = temp
 return
 start = self.start
 i = 1
 while i < pos - 1 and start is not None:
 start = start.link
 i += 1
 if start is None:
 print("💛 The max position is: " + i)
 else:
 temp = Node(data)
 temp.link = self.start
 self.start = temp
 def delete_node(self, node):
 """
 Deletes a node of a linked list
 """
 # 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 == node:
 self.start = self.start.link
 # If more than one node exists
 start = self.start
 while start.link is not None:
 if start.link.info == node:
 break
 start = start.link
 if start.link is None:
 print(f"💔 Sorry! {node} is not in the list.")
 else:
 start.link = start.link.link
 def delete_first_node(self):
 """
 Deletes the first node of a linked list
 """
 if self.start is None:
 return
 self.start = self.start.link
 def delete_last_node(self):
 """
 Deletes the last node of a linked list
 """
 # 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
 start = self.start
 # Increment until we find the node prior to the last node
 while start.link.link is not None:
 start = start.link
 start.link = None
 def reverse_list(self):
 """
 Reverses the linked list
 """
 prev = None
 start = self.start
 while start is not None:
 next_ = start.link
 start.link = prev
 prev = start
 start = next_
 self.start = prev
 def bubble_sort_exdata(self):
 """
 Bubble sorts the linked list with respect to data
 """
 # 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:
 start = self.start
 while start.link != end:
 q = start.link
 if start.info > q.info:
 start.info, q.info = q.info, start.info
 start = start.link
 end = start
 def bubble_sort_exlinks(self):
 """
 Bubble sorts the linked list with respect to links
 """
 # 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
 def merge1(self, list_two):
 """
 Merges two already sorted single linked lists by creating new lists
 """
 merge_list = SingleLinkedList()
 merge_list.start = self._merge1(self.start, list_two.start)
 return merge_list
 def _merge1(self, p1, p2):
 """
 A description of this method goes here
 """
 if p1.info <= p2.info:
 start_m = Node(p1.info)
 p1 = p1.link
 else:
 start_m = Node(p2.info)
 p2 = p2.link
 p_m = start_m
 while p1 is not None and p2 is not None:
 if p1.info <= p2.info:
 p_m.link = Node(p1.info)
 p1 = p1.link
 else:
 p_m.link = Node(p2.info)
 p2 = p2.link
 p_m = p_m.link
 # If the second list is finished, yet the first list has some nodes
 while p1 is not None:
 p_m.link = Node(p1.info)
 p1 = p1.link
 p_m = p_m.link
 # If the second list is finished, yet the first list has some nodes
 while p2 is not None:
 p_m.link = Node(p2.info)
 p2 = p2.link
 p_m = p_m.link
 return start_m
# Testing
if __name__ == '__main__':
 LIST_ONE = SingleLinkedList()
 LIST_TWO = SingleLinkedList()
 LIST_ONE.create_list()
 LIST_TWO.create_list()
 LIST_ONE.bubble_sort_exdata()
 LIST_TWO.bubble_sort_exdata()
 print("1️⃣ The first list is: ")
 LIST_ONE.display_list()
 print("2️⃣ The second list is: ")
 LIST_TWO.display_list()
 LIST_THREE = LIST_ONE.merge1(LIST_TWO)
 print("The merged list by creating a new list is: ")
 LIST_THREE.display_list()