# Merging Two Bubble Sorted Linked Lists (Python)

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

# 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
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
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=' ')
print()

# Inserts an integer in the beginning of the linked list
def insert_in_beginning(self, data):
temp = Node(data)
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

# 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

if p is None:
print("💔 Sorry! " + str(x) + " is not in the list.")
else:
temp = Node(data)

# 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)

# Finding the reference to the prior node containing x
p = self.start
break

print("💔 Sorry! " + str(x) + " is not in the list.")
else:
temp = Node(data)

# 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)
self.start = temp
return

p = self.start
i = 1

while i < k-1 and p is not None:
i += 1

if p is None:
print("💛 The max position is: " + i)
else:
temp = Node(data)
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:

# If more than one node exists
p = self.start
break

print("💔 Sorry! " + str(x) + " is not in the list.")
else:

# Deletes the first node of a linked list
def delete_first_node(self):
if self.start is None:
return

# 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
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

def reverse_list(self):
prev = None
p = self.start
while p is not None:
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

p = self.start
if p.info > q.info:
p.info, q.info = q.info, p.info
end = p

# 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

r = p = self.start
if p.info > q.info:
if  p != self.start:
else:
self.start = q
p, q = q, p
r = p
end = p

def merge1(self, list2):
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)
else:
StartM = Node(p2.info)
pM = StartM

while p1 is not None and p2 is not None:
if p1.info <= p2.info:
else:

# If the second list is finished, yet the first list has some nodes
while p1 is not None:

# If the second list is finished, yet the first list has some nodes
while p2 is not None:

return StartM

# Testing

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:
1   1   1   2   3
2️⃣  The second list is:
1   3   6   6
The merged list by creating a new list is:
1   1   1   1   2   3   3   6   6

• where is merge2 ? :( 💔 – dfhwze Aug 27 '19 at 21:14
• 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 – dfhwze Aug 27 '19 at 21:17

# 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
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=' ')
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=' ')
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

"""
A description of this class goes here
"""

def __init__(self):
"""
Instantiates the single linked list class
"""
self.start = None

def create_list(self):
"""
"""
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
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=' ')
print()

def insert_in_beginning(self, data):
"""
Inserts an integer in the beginning of the linked list
"""
temp = Node(data)
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

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

if start is None:
print(f"💔 Sorry! {number} is not in the list.")
else:
temp = Node(data)

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)

# Finding the reference to the prior node containing x
start = self.start
break

print(f"💔 Sorry! {number} is not in the list.")
else:
temp = Node(data)

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)
self.start = temp
return

start = self.start
i = 1

while i < pos - 1 and start is not None:
i += 1

if start is None:
print("💛 The max position is: " + i)
else:
temp = Node(data)
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:

# If more than one node exists
start = self.start
break

print(f"💔 Sorry! {node} is not in the list.")
else:

def delete_first_node(self):
"""
Deletes the first node of a linked list
"""
if self.start is None:
return

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
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

def reverse_list(self):
"""
"""
prev = None
start = self.start
while start is not None:
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

start = self.start
if start.info > q.info:
start.info, q.info = q.info, start.info
end = start

"""
"""
# 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

r = p = self.start
if p.info > q.info:
if  p != self.start:
else:
self.start = q
p, q = q, p
r = p
end = p

def merge1(self, list_two):
"""
"""
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)
else:
start_m = Node(p2.info)
p_m = start_m

while p1 is not None and p2 is not None:
if p1.info <= p2.info:
else:

# If the second list is finished, yet the first list has some nodes
while p1 is not None:

# If the second list is finished, yet the first list has some nodes
while p2 is not None:

return start_m

# Testing

if __name__ == '__main__':

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()