Tag: Sorting Algorithms

Categories
data structures and algorithms

Out of Place Sort a Singly Linked List in Python

While there are many sorting algorithms in computer science, there are just two ways to classify them. In place, and not in place (or out of place). In place sorting algorithms are ones that are run without an auxiliary data structure such as bubble sort. Out of place (or not in place) sorting algorithms are ones that need extra data structures like merge sort. In this post, we learn how to out of place sort a singly linked list.

We take an unordered singly linked list and create a sorted list out of it. I haven’t seen this algorithm anywhere else on the internet, this is an intuitive sorting algorithm I made up in my head. The time complexity of this algorithm is O(n^2). The space complexity of this algorithm is O(n) – the auxiliary data structure we create becomes the sorted list.

We cover:

  • What Functions Do You Need to Out of Place Sort on a Singly Linked List?
    • Finding the Minimum
    • Removing the Minimum
    • Full Code for a Custom Singly Linked List Class
  • Not In Place Sort Function for a Singly Linked List
    • Visualization of How to Sort a Singly Linked List
    • Code for How to Sort a Singly Linked List in Python
  • Sorting an Example Linked List
  • Summary of Out of Place Sort on a Singly Linked List in Python

What Functions Do You Need to Out of Place Sort on a Singly Linked List?

We cover linked lists and binary trees and sorting algorithms as parts of our introduction to data structures and algorithms series here on PythonAlgos. Now, we are combining the two to learn how to sort a singly linked list. Our original linked list implementation had helper functions to do things like get the size, run a search, delete a node, add a node, or traverse the list. We also had a linked list class separate from the Node class. 

Most of these functions are useless to us right now. For sorting a singly linked list out of place, let’s assume that we won’t bother individually deleting nodes, traversing the list, searching for specific values, or care about the size. We focus solely on the functions we need to actually get a sorted list. The functions that we need are a function to add nodes, a way to print the nodes (this is actually also a nice to have), a way to find the minimum, and a way to remove the minimum.

To start off the Node class, we create a simple __init__ method which takes the required self parameter and a value parameter. This __init__ method creates an initial Node out of the passed in value. We also set the next attribute to None – this is the attribute that makes the singly linked list linked.

Next, we create the append function. This function takes a value and appends it to the end of the linked list. Starting at the root Node, we iterate through until the next attribute is None, meaning we’ve reached the end of the list. Once we’ve reached the end of the list, we set the next value of the last Node to a Node with the passed in value.

The print_nodes function prints all the values of the nodes in one line separated by a space. Similar to the append function, we loop through all of the Nodes until we reach one where the next value is None. For each of the nodes, we print out the value, using an end parameter of a space so that each one does not print a newline before moving onto the next Node. Finally, we print out the value of the last node.

class Node(object):
   def __init__(self, value):
       self.value = value
       self.next = None
  
   def append(self, value):
       while self.next is not None:
           self = self.next
       self.next = Node(value)
 
   def print_nodes(self):
       while self.next is not None:
           print(self.value, end=" ")
           self = self.next
       print(self.value)

Finding the Minimum

The out of place sort algorithm for our singly linked list relies on repeatedly finding the minimum of the linked list. I actually refactored this code multiple times because there are a couple edge cases to consider here. The possible cases you could come across while looking for the minimum of a singly linked list include:

  • There is only one node and it is automatically the minimum
  • The first node is the minimum, and there are multiple nodes
  • The minimum is somewhere in the linked list, and it is not the first one

Handling all of these cases presents some nuance. In addition, we also return the parent when we find the minimum node. Remember that linked lists are only kept in memory by a reference to the root node. If we want to remove a node, we need to get a pointer to the parent of the node so we don’t lose access to the whole list.

The first case that we handle is the case that there is only one node. In this case, we don’t need to do anything but return the node. However, since we are also returning the parent for the last case, we need to return two objects. In this case, we will return a None type object as the parent, and the Node itself as the minimum. The other two cases can be handled with the same strategy.

To start off, we set the minimum node to the self, or the root node, and the parent node to None. Next, we loop through all the nodes until we reach a node that does not point to any other node (the second the last node). For each of the nodes, we check if the value of the next node is less than the value of the current minimum node. If it is, we set the parent node to the node we are on and the minimum node to the next node. Either way, we set the self to the next node to ensure we continue iterating. After we’ve looped through all the nodes, we return the parent and the minimum node.

   # keep track of min and parent
   def find_min(self):
       if self.next is None:
           return None, self
       min = self
       parent = None
       while self.next is not None:
           if self.next.value < min.value:
               parent = self
               min = self.next
           self = self.next
       return parent, min

Removing the Minimum

Now that we have a way to find the minimum node, we need a way to remove the minimum node. This function also has multiple cases to consider. The three cases that we need to consider when removing the minimum of a singly linked list, given that we have found the parent and the minimum already are:

  • There is no parent node to account for
  • The minimum node is the last node and does not have a next node
  • We’re removing a node in the middle and need to account for the next node

The first case happens when the minimum node is the first node or the only node. We handle this case first. When the parent node is None, we set the self object to the next node and the minimum node’s next pointer to None to remove it. Then we return the self object and the minimum node. Note that if the minimum node does not have a next object, we have emptied our original linked list.

Once again, we handle the other two cases together using if statements. Instead of branching on the parent node though, we use a condition on the minimum node. If the minimum node’s next object is not None, we set the parent node’s next pointer to the minimum node’s original next object. Then, we set the minimum node’s next pointer to None to remove the node out of the linked list.

Otherwise, the minimum node’s next object is None, and we are removing the last node. We can simply remove the last node by setting the parent node’s next object to None. Once again, we set the minimum node’s next object to None. We can actually make this code cleaner/less repetitive by setting the min.next = None line outside of the if/else conditional. I’m not sure that makes it more clear, but it does make the file smaller.

   # find minimum and parent
   # point parent.next to min.next if it exists
   # point min.next to None to officially remove
   def remove_min(self):
       parent, min = self.find_min()
       if parent is None:
           self = min.next
           min.next = None
           return self, min
 
       if min.next is not None:
           parent.next = min.next
           min.next = None
       else:
           parent.next = None
           min.next = None
       return self, min

Full Code for a Custom Singly Linked List Class

We’ve covered the logic for each part of the Node class for a singly linked list separately. Here is the full code we use for this implementation.

class Node(object):
   def __init__(self, value):
       self.value = value
       self.next = None
  
   def append(self, value):
       while self.next is not None:
           self = self.next
       self.next = Node(value)
 
   def print_nodes(self):
       while self.next is not None:
           print(self.value, end=" ")
           self = self.next
       print(self.value)
  
   # keep track of min and parent
   # while parent has next
   # # if next value is
   def find_min(self):
       if self.next is None:
           return self, self
       min = self
       parent = None
       while self.next is not None:
           if self.next.value < min.value:
               parent = self
               min = self.next
           self = self.next
       return parent, min
  
   # find minimum and parent
   # point parent.next to min.next if it exists
   # point min.next to original root
   def remove_min(self):
       parent, min = self.find_min()
       if parent is None:
           self = min.next
           min.next = None
           return self, min
 
       if min.next is not None:
           parent.next = min.next
           min.next = None
       else:
           parent.next = None
           min.next = None
       return self, min

Not In Place Sort Function for a Singly Linked List

Now that we have a Node class to create a singly linked list, let’s write our sorting algorithm. As mentioned above, this sorting algorithm is not an in-place sorting algorithm. We actually build an entirely new linked list to sort our original one. I made this sorting algorithm on the fly as an intuitive way to sort a singly linked list. 

This algorithm passes through the linked list once for each element. Each pass through of the linked list consists of removing the current minimum element and appending that element to a new, sorted linked list. In the next two subsections we see a visualization and the code with an explanation of how this sorting algorithm works.

Visualization of How to Sort a Singly Linked List

Let’s visualize how this out of place sorting algorithm works on a simple three element linked list. Assuming we start with a totally out of order list of 8, 4, 2, our algorithm will take three passes. Round one finds the minimum of 2, removes it from the original list, and starts a new singly linked list from it. The second pass looks at the new list of just 8, 4, finds the minimum of 4, and appends it to the new list we made in round one. Finally, we remove the last element, 8, and append that to the new list. Now we are left with a sorted singly linked list: 2, 4, 8.

Code for How to Sort a Singly Linked List in Python

I debated with myself over whether or not this sorting function should be a standalone function that acts on the class, or whether it should be a function in the class. I decided that it should be a standalone function because we are creating a totally new data structure. This sort function takes one parameter, the starting root node of the original list. It returns the new root of the sorted linked list.

As I break down in the comments above the function, this function does two things. First, remove the minimum and put it into a new linked list. Second, repeat step one until the original linked list is empty. Start by getting the parent and current minimum from the passed in root. Then, set the new root of the sorted singly linked list to the returned minimum. While the modified original linked list has a next node, repeatedly remove the minimum and append the new root to the new list. Finally, append the last remaining value in the linked list and return the root of the newly created linked list.

# 1. remove minimum and put it into a new linked list
# 2. repeat 1 until original linked list no longer exists
def sort_nodes(root: Node):
   new_list, min = root.remove_min()
   new_root = min
   while new_list.next is not None:
       new_list, min = new_list.remove_min()
       new_root.append(min.value)
   new_root.append(new_list.value)
   return new_root

Sorting an Example Linked List

Let’s test our function with three examples. The first example is the three element example shown in the visualization: 8, 4, 2. Next, we also append 1 and 5 and sort, and then 7 and sort. The resulting sorted lists should be: 2, 4, 8, then 1, 2, 4, 5, 8, and 1, 2, 4, 5, 7, 8. The example code to test the sort function is shown below.

root = Node(8)
root.append(4)
root.append(2)
root = sort_nodes(root)
root.print_nodes()
 
root.append(1)
root.append(5)
root = sort_nodes(root)
root.print_nodes()
 
root.append(7)
root = sort_nodes(root)
root.print_nodes()

When we run the code above, we get an output that matches the expected sorted lists as shown below.

Summary of Out of Place Sort on a Singly Linked List in Python

In this post, we created a custom linked list implementation and an out of place sorting algorithm. The sorting algorithm we created runs in O(n^2) time and requires O(n) space. It works by finding and removing the minimum element from the original linked list, and then appending it to a new, sorted linked list.

More by the Author

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.