Two Ways to Sort a C++ Linked List
Comparison of Insertion Sorting and Regular Sorting Using C++ Code
Study of the application of insertion sorting and normal post-list creation sorting and the prerequisites, advantages and disadvantages of both techniques using C++ code
Introduction
Sorting a linked list can be done in several ways, but there are usually 2 possibilities:
- Sorting on creation (insertion sort);
- Sorting post-creation;
In the first instance, we sort the list as data is being added. In the second, we sort the list as an entity, by swapping nodes until they are in order. There are quite a few sorting algorithms in C++ programming to achieve this, including an insertion sort on a newly created list. These techniques and algorithms will be covered in the remainder of this linked list sorting article.
The Linked List Class
We assume that a linked list class exists for processing Integer data, called CLinkedList_Integer, with nodes storing integer data called CNode_Integer. This might be defined in a header file as follows:
{
private:
CNode_Integer * oNext;
CNode_Integer * oPrevious;
int nData;
public:
CNode_Integer();
~CNode_Integer();
int GetData();
void SetData(int nData);
CNode_Integer * GetNext();
CNode_Integer * GetPrevious();
void SetNext(CNode_Integer * oNext);
void SetPrevious(CNode_Integer * oPrevious);
};
class CLinkedList_Integer
{
private:
CNode_Integer * oHead;
public:
CLinkedList_Integer();
~CLinkedList_Integer();
CNode_Integer * InsertNode(CNode_Integer * oNode);
CNode_Integer * AddNode(CNode_Integer * oNode);
CNode_Integer * SwapNodes(CNode_Integer * oNodeLeft, CNode_Integer * oNodeRight);
int CompareNodes(CNode_Integer * oNodeLeft, CNode_Integer * oNodeRight);
CNode_Integer * RemoveNode(CNode_Integer * oNode);
};
The 4 functions that we will need for our sorting are:
- InsertNode - traverses the list and inserts the node at the appropriate place;
- AddNode - adds a node to the head of the list;
- SwapNodes - swaps two nodes;
- CompareNodes - returns strcmp compatible codes -1, 0, 1.
The last function in the list will return -1 if oNodeLeft is 'less' than oNodeRight, 0 if they are equal, and 1 if oNodeLeft is 'more' than oNodeRight. This mimics the string library, string.h, where the same codes are returned for strcmp and strcmpi string comparison.
Insertion Sorting
Insertion Sorting in this case means that we will be sorting the list data as it is added. The InsertNode member function is responsible for taking a populated node and inserting it at the right place. To do this, it must traverse the list, and decide where to add the node:
- Get the current node;
- Compare the nodes with ::CompareNodes;
- If the return value is -1 or 0 add the node before the current node, if 1 add after the current node;
- If the node has been added, stop.
- If the node has not been added, get the next node.
We have to make sure that we cater for the border cases:
- An empty list;
- Inserting before the Head element;
- Inserting after the Tail element;
Other than that, the insertion sort is fairly straightforward.
Post-List Creation Sorting
If we want to sort a list that has been built as an unsorted entity, we can use the CompareNodes and SwapNodes member functions to perform a bubble sort, as in the Alphabetizing a Linked List in C article. Readers unfamiliar with this simple sorting technique might like to go and read that now before continuing here. Essentially, the steps to follow are (starting from the Head node each time):
- Test the current node and the next node, using ::CompareNodes;
- If the result is -1, use ::SwapNodes to swap the nodes;
- Get the next node, until there are none left;
- If we performed no swaps, stop, otherwise repeat.
Again, we have to take care of the special empty list and borderline cases. There are also better sorting methods, such as QuickSort, which yield faster results. The implementation of the member functions CompareNodes and SwapNodes are complementary to the use of alternative sorting algorithms as they do not rely on the nodes being next to each other.
Choosing a Sorting Technique
In certain cases it is easy to choose between an algorithm to sort on list creation or after the list has been populated. If the result needs to be re-sorted, however, using different criteria (reverse the order, group by values, or sort on a different value of a complex data type etc.), then we might face a choice. Clearly, if we want to create a sorted version of an existing list, we can either sort it, or create a new list, and use insertion sorting to ensure that it is sorted using the correct criteria.
If the data set is particularly large, or memory constraints are in force, then we might not want to take this approach, in which case a regular bubble sorting or QuickSort algorithm must be used. The key advantages of an insertion sort using a parallel list are:
- Speed;
- The possibility to undo quickly.
There is a variation on these techniques for use when memory restrictions are in force, or processing speed is vital, which maintains a linked list of data, and a linked list of pointers to that data. The pointer list is very lightweight, and gives the ordering of the data retrieval. The individual nodes are never swapped, only references to them, and several lightweight sorted linked lists can be maintained at once, meaning that the data can be evaluated in many different ways, without resorting.
Links
Swapping
Sorting
