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   

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