celebrity writers

Alphabetizing a linked list in C

A hands-on tutorial covering C programming techniques for linked lis

Sep 15, 2006

Tutorial explaining how a linked list can be alphabetized in C using a simple bubble sort technique; great for new and intermediate computer programmers.

Introduction

Sorting is one of the trickiest tasks in computer programming, and is also one of the most useful. There are many different types and algorithms, but to keep things simple, we are going to consider simple alphabetizing using a bubble sort algorithm.

We shall assume that:

Each word is in lower case
Each word is a null-terminated array of characters

We are also using the C programming language, which means that we cannot encapsulate any of the abstract data types in a class. C++ programmers and budding C programmers hoping to move to C++ will appreciate the differences between this tutorial and a class-based implementation.

The theory, however, remains the same.

Alphabetizing Theory

To sort a list of words into alphabetically ascending order, we need to be able to compare them. Since C provides a library known as string.h, we should use this. In string.h there is a simple comparison function called strcmp. The strcmp function takes two strings and returns:

-1 if string A is less than string B
0 if the strings are equal
1 if string B is less than string A

In other words, if string A were to come before string B in a dictionary, then strcmp would return -1. Thus, the majority of the hard work in alphabetizing is done for us. There is, however, a caveat - if the strings are not both in the same case, then the strcmpi (the i standing for insensitive) should be used.

Alphabetizing in Practice : Bubble Sort

A bubble sort algorithm is one of the simplest forms of sorting known to programmers. It basically allows high values to 'bubble' up through the rest, by repeatedly comparing neighboring values, and swapping them. Consider the list:

If we wanted to sort this list to yield 'ABCD', we could use a bubble sort and compare neighbors, swapping the values if one was 'less' than the other. In the first pass, we would end up with the following:

This list is the result of swapping neighbors successively, starting at the first item in the list, and progressing through it until the last pair has been compared. The 'D' has bubbles up (or down) through the values, being swapped each time because each other value was 'less' than 'D':

D B C A : Swap D & B
B D C A : Swap D & C
B C D A : Swap D & A
B C A D : End

This, however, is not the end of the story, since the list is now better sorted than it was before, but not quite correctly sorted. In fact, we need to apply the bubble sort algorithm repeatedly, until no more swaps take place.

In C, this might look akin to:

do
{
Swap = 0;
for (i = 1, i < nStrings; i++)
{
  if (swap(szStrings[i-1], szStrings[i], -1) == 1)
  {
   nSwap++;
  }
}
} while (nSwap == 0);

We assume that the swap function performs a compare and swap based on two strings and a direction. This function would be different depending on the elements of the list that we wish to sort.

The Linked List Implementation

The above is fine, but it only provides a way of sorting a two dimensional list : a list of strings. What we need is a linked list, and so we need to redefine the data structures and algorithms used to manipulate the list.

To do this, we create a node structure in C, containing:

The string
A pointer to the next node

Each node is then initialized with the string that it needs to contain, and a NULL pointer. When we need to add a node, all that has to be done is to create a new node, and point the 'next' member to the head of the existing list.

Swapping then becomes a case of redirecting these pointers such that the nodes are reversed in their order within the list. This will require two steps:

Point the next member of Node A to the node after Node B
Point the next member of Node B to Node A

Note that, unlike processing an array, no copy of the data to be swapped is taken, as only a reference to the data elemnt is retained. This makes the bubble sort process marginally more efficient, but still far less efficient than other, more specialized, sorting algorithms.

Conclusion

The C++ version of this tutorial, were it to exist, would no doubt describe a linked list class, and encapsulate much of the comparison and sorting algorithms inside it. Feel free to request such a tutorial in the dicussions below, or by email to the author.

For some more articles in the area of list management, please see:

The copyright of the article Alphabetizing a linked list in C in Computer Programming is owned by Guy Lecky-Thompson. Permission to republish Alphabetizing a linked list in C in print or online must be granted by the author in writing.