Two Ways to Sort a C++ Linked List

Comparison of Insertion Sorting and Regular Sorting Using C++ Code

May 29, 2007

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:

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:

class CNode_Integer
{
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 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:

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

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:

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

The copyright of the article Two Ways to Sort a C++ Linked List in Computer Programming Tutorials is owned by Guy Lecky-Thompson. Permission to republish Two Ways to Sort a C++ Linked List in print or online must be granted by the author in writing.