2
\$\begingroup\$

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
        self.link = None

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

    def create_list(self):
        """
        Creates the single linked list
        """
        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=' ')
            p = p.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

        p = self.start  
        while p.link is not None:
            p = p.link
        p.link = temp

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

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

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

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

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

    def reverse_list(self):
        """
        Reverses the linked list
        """
        prev = None
        p = self.start
        while p is not None:
            next = p.link
            p.link = prev
            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

        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

    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, list2):
        """
        Merges two already sorted single linked lists by creating new lists
        """
        merge_list = SingleLinkedList()
        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)
            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

    def merge2(self, list2):
        """
        Merges two already sorted single linked lists in place in O(1) of space
        """
        merge_list = SingleLinkedList()
        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
            p1 = p1.link
        else:
            StartM = p2
            p2 = p2.link
        pM = StartM

        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 StartM

# Testing

if __name__ == '__main__':

    LIST_ONE = SingleLinkedList()
    LIST_TWO = SingleLinkedList()

    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: 
💚 Single linked list includes: 
-1   0   47   30   -4   26   
2️⃣  The unsorted second list is: 
💚 Single linked list includes: 
-3   19   24   -120   -120   84   40   -50   0   
1️⃣  The sorted first list is: 
💚 Single linked list includes: 
-4   -1   0   26   30   47   
2️⃣  The sorted second list is: 
💚 Single linked list includes: 
-120   -120   -50   -3   0   19   24   40   84   
The merged list by creating a new list is: 
💚 Single linked list includes: 
-120   -120   -50   -4   -3   -1   0   0   19   24   26   30   40   47   84   
The in-place merged list is: 
💚 Single linked list includes: 
-120   -120   -50   -4   -3   -1   0   0   19   24   26   30   40   47   84
\$\endgroup\$
3
\$\begingroup\$
"""
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):
        """
        Creates the single linked list
        """

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

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:
            p = p.link
            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:
            self.start = self.start.link

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

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):
        ...
        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

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):
        """
        Merges two already sorted single linked lists by creating new lists
        """
        merge_list = SingleLinkedList()
        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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.