# In-Place Merging of Two Bubble Sorted Linked Lists (Python)

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

• merge1 does the merging by creating a new list with maybe $$\O(N+M)\$$ memory complexity that I'm guessing, and has been also reviewed here.
• merge2 does an in-place merging with $$\O(1)\$$ constant space complexity that I'm guessing.

Other than naming conventions which are not the best here and is not a concern and I have to just follow the tutorial, any feedback would be appreciated, especially about the best practices in object-orinted programming, practical as opposed to theoretical time and complexities, and algorithms.

"""
Module Docstring
This is a simple object-oriented implementation of merging two Single Linked Lists with some associated methods,
such as bubble sorting, create list, and such.

"""

class Node:
def __init__(self, value):
"""
Instantiates the node class
"""
self.info = value

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

def create_list(self):
"""
"""
n = int(input("Enter the number of nodes in the list you wish to create: "))

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

def display_list(self):
"""
Displays the list
"""
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()

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

p = self.start

def insert_after(self, data, x):
"""
Inserts an integer after the x node
"""
p = self.start

while p is not None:
if p.info == x:
break

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

def insert_before(self, data, x):
"""
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 x == self.start.info:
temp = Node(data)

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

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

def insert_at_position(self, data, k):
"""
Inserts an integer in k position of the linked list
"""

#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

def delete_node(self, x):
"""
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 == x:

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

print(f"💔 Sorry! {x} 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
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

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

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):
"""
Private method of merge1
"""
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

def merge2(self, list2):
"""
Merges two already sorted single linked lists in place in O(1) of space
"""
merge_list.start = self._merge2(self.start, list2.start)
return merge_list

def _merge2(self, p1, p2):
"""
Merges two already sorted single linked lists in place in O(1) of space
"""
if p1.info <= p2.info:
StartM = p1
else:
StartM = p2
pM = StartM

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

if p1 is None:
else:

return StartM

# Testing

if __name__ == '__main__':

LIST_ONE.create_list()
LIST_TWO.create_list()

print("1️⃣  The unsorted first list is: ")
LIST_ONE.display_list()

print("2️⃣  The unsorted second list is: ")
LIST_TWO.display_list()

LIST_ONE.bubble_sort_exdata()
LIST_TWO.bubble_sort_exdata()

print("1️⃣  The sorted first list is: ")
LIST_ONE.display_list()

print("2️⃣  The sorted 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()

LIST_FOUR = LIST_ONE.merge2(LIST_TWO)

print("The in-place merged list is: ")
LIST_FOUR.display_list()


### Output

Enter the number of nodes in the list you wish to create: 6
Enter the element to be inserted: -1
Enter the element to be inserted: 0
Enter the element to be inserted: 47
Enter the element to be inserted: 30
Enter the element to be inserted: -4
Enter the element to be inserted: 26
Enter the number of nodes in the list you wish to create: 9
Enter the element to be inserted: -3
Enter the element to be inserted: 19
Enter the element to be inserted: 24
Enter the element to be inserted: -120
Enter the element to be inserted: -120
Enter the element to be inserted: 84
Enter the element to be inserted: 40
Enter the element to be inserted: -50
Enter the element to be inserted: 0
1️⃣  The unsorted first list is:
-1   0   47   30   -4   26
2️⃣  The unsorted second list is:
-3   19   24   -120   -120   84   40   -50   0
1️⃣  The sorted first list is:
-4   -1   0   26   30   47
2️⃣  The sorted second list is:
-120   -120   -50   -3   0   19   24   40   84
The merged list by creating a new list is:
-120   -120   -50   -4   -3   -1   0   0   19   24   26   30   40   47   84
The in-place merged list is:
-120   -120   -50   -4   -3   -1   0   0   19   24   26   30   40   47   84


"""
Module Docstring
This is a simple object-oriented implementation of merging two Single Linked Lists with some associated methods,
such as bubble sorting, create list, and such.

"""


The line Module Docstring is probably a placeholder which you're meant to remove, but it's good to see that the methods are documented.

    def create_list(self):
"""
"""


What's the difference between create and instantiate? I think this is best described as Reads values from stdin and appends them to this list.

    def insert_in_beginning(self, data):
"""
Inserts an integer in the beginning of the linked list
"""
temp = Node(data)
self.start = temp


There's an insert_at_position below: why not just call that with position 0?

        if self.start is None:


Thumbs up for using the right comparison operator.

    def insert_before(self, data, x):
"""
Inserts an integer before the x node
"""

#If list is empty
if self.start is None:
print("💔 Sorry! The list is empty.")
return


In general, raising an exception is more useful than printing something to stdout.

        #If x is the first node, and new node should be inserted before the first node
if x == self.start.info:
temp = Node(data)


I think this is extremely buggy. p doesn't exist yet, self.start should be updated to temp, and it shouldn't fall through and potentially insert the value twice.

    def insert_at_position(self, data, k):
"""
Inserts an integer in k position of the linked list
"""

#if we wish to insert at the first node
if k == 1:


1-indexing in Python? That's going to confuse people...

        p = self.start
i = 1

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


I suggest refactoring this to decrement k and eliminate the variable i entirely.

    def delete_node(self, x):
...
#If there is only one node
if self.start.info == x:


The comment describes a different condition to the one which the code actually tests. This would be clearer without the comment.

    def reverse_list(self):
...
prev = p
p = next


Here Python's simultaneous assignment prev, p = p, next can be useful.

This seems like a good point to ask the question: do you know what a sentinel is? A linked list using a sentinel node for start could avoid the special cases of most of the methods above.

    def bubble_sort_exdata(self):
"""
Bubble sorts the linked list with respect to data
"""


The meaning of "with respect to data" is not transparent to me. I only figured it out once I looked at the implementation.

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


So far I've resisted the temptation to comment on names, because you said that they're following the tutorial, but I find end to be very misleading. I would expect it to be the last node in the list, whereas in effect it's a sentinel for the end of the unsorted portion of the list.

    def bubble_sort_exlinks(self):
...
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


This is rather complex. I could use some comments to explain the loop invariants and the meanings of p,q,r.

    def merge1(self, list2):
"""
"""
merge_list.start = self._merge1(self.start, list2.start)
return merge_list

def _merge1(self, p1, p2):
"""
Private method of merge1
"""
if p1.info <= p2.info:


What if p1 is None or p2 is None? I don't see anything which would prevent those cases arising.

            StartM = Node(p1.info)


This could be just self.start instead of StartM if called with a different self. At present the method doesn't use self at all.

    def merge2(self, list2):
"""
Merges two already sorted single linked lists in place in O(1) of space
"""


This should say something about the process being destructive to this and list2. And it would arguably make more sense to merge list2 into self and not return anything.

    def _merge2(self, p1, p2):
"""
Merges two already sorted single linked lists in place in O(1) of space
"""
if p1.info <= p2.info:


Same bug as _merge1.

# Testing

if __name__ == '__main__':


That's good, but it might be better to use doctest.