• 09/30/04 10:43 AM
    Sign in to follow this  

    Introduction to Pointers, Structures and Linked-Lists Part 5

    General and Gameplay Programming

    Myopic Rhino

    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)

    Author: Chris Bennett aka Dwarfsoft
    Contact: dwarfsoft@hotmail.com
    November 27, 2000
    (C) Copyright Chris Bennett, 2000-2001



      Report Article
    Sign in to follow this  


    User Feedback

    Create an account or sign in to leave a review

    You need to be a member in order to leave a review

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

    There are no reviews to display.