Introduction to Pointers, Structures and Linked-Lists Part 5
Sorting
by Chris Bennett aka Dwarfsoft

Introduction

Well, now you should be familiar with Linked Lists and Dynamic Memory Allocation. These two things combine quite well to being very beneficial in databasing. Until now, we have covered single linked lists, but now I would like to introduce the double linked list, for use with sorting data.

Double Linked Lists The double linked list has similar properties to the single linked list, but it also contains a 'Prev' pointer in addition to its 'Next' pointer.

Figure 1 - A Visualisation of a Double-Linked List with 2 Elements

The added benefit of this is that you can remove temporary pointers that save the address of the previous element when you are freeing memory. Another benefit is that you don't need to have a pointer referencing the beginning of the list (although it is a good idea) as you can search back through the list for the beginning. The freeing function then becomes like this

int CleanUp (AddressPtr_t Cur)
{
  // Search for the beginning
  while (Cur && Cur->Prev)
    Cur = Cur->Prev;

  // Free the memory
  while (Cur && Cur->Next)
  {
    Cur = Cur->Next;

    free(Cur->Prev);
  }

  if (Cur) free(Cur);
}

This may look more complicated, but the added benefit of being able to PROVE that you are at the beginning of the list is definitely a benefit, as you don't have as many leaks in memory. This also saves you from defining a temporary variable, but it almost doesn't seem worth it for that.

Anyway, I will be assuming from now on that our above Address List is a double linked list. Now, let us move on to more interesting topics.

Sorting Linked Lists

One very good reason for using linked lists is for sorting. Sorting linked lists is possibly one of the simplest (in theory) sorting algorithms that you can ever develop. It looks fairly complex, but the basis behind it is "Check if this element should be before that other element" "If yes, then swap pointers around so that it is before that element, and not in its current position". Using a bubble search algorithm, you can move through the entire list, and organise them by whatever method that you want.

int SortByName(AddressPtr_t Cur)
{
  // The middle loop iteration pointer
  AddressPtr_t Iter = Cur;

  // A boolean value for remembering whether
  // the list was modified or not
  bool Changed;

  //Get to the beginning again
  while (Cur && Cur->Prev)
    Cur = Cur->Prev;

  // Start the Sort
  // If there exists an element, Iter is the
  // next element
  if (Iter) Iter->Next;

  // Basically keeps iterating until there
  // are no changes and Cur = NULL
  while (Changed || Cur)
  {
    // Reset the Modified switch for this iteration
    Changed = false;

    while (Iter)
    {
      // If it belongs before Cur, put it there
      if (strcmp(Cur->Name,Iter->Name) > 0)
      {
        // Remove Iter from its location
        if (Iter->Next)
          Iter->Next->Prev = Iter->Prev;
        Iter->Prev->Next = Iter->Next;

        // Insert Iter before Cur
        Iter->Prev = Cur->Prev;
        if (Iter->Prev)
          Iter->Prev->Next = Iter;
        Iter->Next = Cur;
        Cur->Prev = Iter;

        // Set modified flag
        Changed = true;
      }

      // Next iteration
      Iter = Iter->Next;
    }

    if (Changed)
    {
      // Start sorting from the beginning again
     // Get to the beginning again
      while (Cur && Cur->Prev)
        Cur = Cur->Prev;

      // If an element exists, Iter is the
     // next element
      if (Cur) Iter = Cur->Next;
    }
    else
    {
      // Go to the next value
      if (Cur) Cur = Cur->Next;
      if (Cur) Iter = Cur->Next;
    }
  }
  return 0;
}

Well, there are only 2 different pointers. I could have done a more simplistic sort, but this sort also takes into account assertions. This should be fairly easy to follow with comments in it. It definitely works, so if you can't understand it you can fiddle around with the values and see what effects they have (not advised, if you wish not to have to deal with crashes). You could also just ask somebody in the Beginner Programming forum, and I will probably be able to answer any questions either there or if you email me (dwarfsoft@crosswinds.net) I will see what I can do to sort out discrepancies. Try to follow through a step at a time in the sort, as it really isn't that difficult to understand if you just follow what the comments tell you.

One good element of double linked lists is the ability to use indirection to itself. To explain this more clearly I just need to use the following code.

if (Address->Prev)
  Address->Prev->Next = Address;

What does this code do? NOTHING! First, it checks to see if the current element has a reference to a previous element (just to avoid assertion violations) and then it sets the pointer to itself… To itself! Then, you can have fun like this

if (Address->Prev)
  Address->Prev->Next->Prev->Next = Address;

And you can keep adding in those pointers. The previous code does exactly the same thing as the original line. This is just some useful trivia, and it may help you when it comes to rearranging. I used this in the sorting algorithm that was written earlier. Here is a sequence of pictures of what happens in the "if (strcmp(Cur->Name,Iter->Name) > 0)" block:

Figure 2 - The Original Setup of our Linked List, Just entering the if() block

Figure 3 - Reassigning the links between the second and fourth elements

Figure 3 is the state of our list after the following code

if (Iter->Next) Iter->Next->Prev = Iter->Prev;

Figure 4 - Reassigning the links between the second and fourth elements

Figure 4 is the state of our list after the following code

Iter->Prev->Next = Iter->Next;

Figure 5 - Linking Iter to the element before Cur

Figure 5 is the state of our list after the following code

Iter->Prev = Cur->Prev;

Figure 6 - Inserting Iter after the element at Cur->Prev

Figure 6 is the state of our list after the following code

if (Iter->Prev) Iter->Prev->Next = Iter;

Figure 7 - Making Cur the Next value of Iter

Figure 7 is the state of our list after the following code

Iter->Next = Cur;

Figure 8 - The finished order of our list, Cur and Iter have been swapped

Figure 8 is the state of our list after the following code

Cur->Prev = Iter;

I hope that the sequence will help you to better visualise what is happening. The main thing to beware of with pointers is that you don't lose a link at any point. If I had have started out with inserting Iter before Cur without changing Iter->Prev->Next to Iter->Next then the element (and all following elements) after Iter would have been lost. It is good to visualise pointers like this, so that you are better able to ensure your programs consistency. If the pointers had been reassigned like I just stated, a memory leak would have occurred. The only way to get back memory leaks is to use a memory-cleaning program or to restart your computer.

Conclusion

Now that we have an understanding of sorting, we can use this knowledge to make an alphabetised address book. The sort that I showed above is a (slightly) optimised bubble sort. In a following article I will introduce you to recursion and recursive functions. We will then rewrite our sort to be a recursive function, as the above function just reeks of recursion. Look forward to the next set of articles in this online tutorial to linked lists.

Cheers, Chris Bennett (aka. Dwarfsoft)

Discuss this article in the forums

Date this article was posted to GameDev.net: 9/30/2004
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
General