Sort linked list Python

In this post, Im going to implement the linked list from scratch and build important functionality such as insertion [and insert_at], deletion, swap, and sort. As data science graduate student, I find that the lions share of the material focuses on the statistics and mathematics behind machine learning. Undoubtedly, success here is paramount to a career in data science. However, the importance of computer science fundamentals is often marginalized.

So what is a linked list?

A linked list is an object composed of nodes, which are [you guessed it] also objects. Both of which we need to implement. Each node contains a value and a link to the subsequent node. This much is mandatory. A doubly linked list [something well only cover in qualitative terms here] is a similar object where its nodes also contain links to their previous nodes. A head is essential. Its the first entry in a linked list. By default, its next node attribute is set to none. When we add a second item, we instantiate a node object and set the heads next attribute to reference the [new] node weve just created. If we add a third node to the linked list, we instantiate a new node object, and set the second nodes next attribute to reference the newly created node. And this process is repeated for whatever number of values we wish to insert into the linked list.

Things get trickier when we want to insert a value into the middle of the list. Lets say we have a linked list composed of three elements 0,2,3 and we wish to insert the value 1 into index position 1. Currently, the head is 0 and its next attribute references 2. We need to instantiate a node object, setting the value to 1. From here, we need to set the heads next attribute to 1 and set the next attribute of 1 to 2.

Sounds easy so far, right? Youll notice that in order to reach a node by its index, we need to traverse all previous nodes, starting with the head. It hasnt been said in explicit terms, but we need to define a class method called get_next[] which will reference the following node. What happens when were on the last node? Unless we account for this, well trigger an error. It becomes necessary to account for both the length of the linked list and how far weve traveled since the head. Well do this by creating a class attribute called count which will either reference the length of the linked list or the index of the final item in it [Ive opted for the latter option in this implementation.]

When we delete a value we need to reduce the count by 1; likewise, when we insert a value, we need to increase the count by 1. This process becomes even trickier when we swap values. We need to both delete and insert values; as a consequence, the count and relative position within the linked list can vary depending on the order which we execute these procedures. Keeping track of where were at takes attention to detail.

The most difficult task is sorting the linked list. Ive opted to use selection sort as the algorithm of choice. Superior sorting algorithms do exist, but well focus on selection sort because its relatively simple among sorting algorithms. The algorithm works by establishing an index position of sorted values. When we start, this index is set to 0. We set selection as the subsequent value and traverse the remainder of the list, looking for the minimum vale to the right of the sorted_idx. If a nodes value is smaller than selection then we set selection to this value and keep track of its index. After traversing the linked list and finding the minimum value, we delete this node, instantiate a new node with a value equal to the selection, and insert this node at the sorted_idx. Lastly, we increment the sorted_idx by 1 and repeat until this index equals the count attribute minus 1 [because theres no nodes available to traverse after weve reached the last node.]

As youll notice, this process starts by setting the sorted_idx equal to 0, and the selection equal to the value of the node immediately following the head. In cases where the head is the maximum value, it will be pushed to the end of the list when the process terminates, which is fine. But if the head is not the maximum value, it will still be pushed to end; but this is an incomplete sort. We need to build a final step to account for the value of the final entry and traverse the entire linked list. At each step, the nodes value will be compared to the final entry. If greater than the nodes value, we will traverse to the following node and compare again. This process repeats until we arrive at a node where the value is greater than the value of the final of entry, which we noted earlier. Upon reaching a higher value [and because all previous values were smaller], we now know where the final entrys real home is. We delete the final entry and insert its value into the index proceeding the first value greater than our selection. If we traverse the length of the list [excepting for the final entry] and all values were smaller, then we can safely conclude that the final entry was the maximum value and is already in its appropriate home. Whew!

Lets take a look at the code!

The full repository can be located here: //github.com/jdmoore7/linked_list/blob/master/LinkedList.py

Thanks for reading!