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.
- 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.
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
- How to Automatically Transcribe a Notion MP3 File
- Nested Lists in Python
- Python String Manipulation Guide
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.
Make a one-time donation
Make a monthly donation
Make a yearly donation
Choose an amount
Or enter a custom amount
Your contribution is appreciated.
Your contribution is appreciated.
Your contribution is appreciated.DonateDonate monthlyDonate yearly
4 thoughts on “Out of Place Sort a Singly Linked List in Python”
I’m struggling to see how the time complexity is O(nlogn).
The find_mind function would take O(n) each time to traverse the list and find the mininum, and then traverse the new list and append the new element at the last node.
The sort_nodes function would call find_min n times, making the complexity O(n^2).
Did I miss something? The algorithm should be the same as a selection sort, except the value is moved to a new list instead of switching it with the slow pointer value.
Hi V, great observation, the sort_nodes function would indeed call find_min n times, however, the size of the list is changing, and on average we traverse the list log(n) times because we are removing the minimum each time, thus I believe the big O time complexity should be n*log(n) – does that make sense?
I think that it falls back to this case: https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF
As the last while iteration will have only 1 element in the list, the second to last has 2 elements, then 3, then 4… and the first one has n (the initial list), so you can see it as the 1 to n sum, as you can’t find the new minimum unless you traverse the whole list every time you remove an element.
Oh yeah, that seems right, thanks for pointing this out, I’ve made the change