Jump to content

  • Log In with Google      Sign In   
  • Create Account

Like
0Likes
Dislike

Introduction to Pointers, Structures and Linked-Lists Part 5

By Chris Bennett aka Dwarfsoft | Published Sep 30 2004 04:43 AM in General Programming

list iter figure linked cur element code sorting lists
If you find this article contains errors or problems rendering it unreadable (missing images or files, mangled code, improper text formatting, etc) please contact the editor so corrections can be made. Thank you for helping us improve this resource



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



<span class="codekeyword">int</span> CleanUp (AddressPtr_t Cur)

{

  <span class="codecomment">// Search for the beginning</span>

  <span class="codekeyword">while</span> (Cur && Cur->Prev)

    Cur = Cur->Prev;



  <span class="codecomment">// Free the memory</span>

  <span class="codekeyword">while</span> (Cur && Cur->Next)

  {

    Cur = Cur->Next;



    free(Cur->Prev);

  }



  <span class="codekeyword">if</span> (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.



<span class="codekeyword">int</span> SortByName(AddressPtr_t Cur)

{

  <span class="codecomment">// The middle loop iteration pointer</span>

  AddressPtr_t Iter = Cur;



  <span class="codecomment">// A boolean value for remembering whether

  // the list was modified or not</span>

  <span class="codekeyword">bool</span> Changed;



  <span class="codecomment">//Get to the beginning again</span>

  <span class="codekeyword">while</span> (Cur && Cur->Prev)

    Cur = Cur->Prev;



  <span class="codecomment">// Start the Sort

  // If there exists an element, Iter is the

  // next element</span>

  <span class="codekeyword">if</span> (Iter) Iter->Next;



  <span class="codecomment">// Basically keeps iterating until there

  // are no changes and Cur = NULL</span>

  <span class="codekeyword">while</span> (Changed || Cur)

  {

    <span class="codecomment">// Reset the Modified switch for this iteration</span>

    Changed = false;



    <span class="codekeyword">while</span> (Iter)

    {

      <span class="codecomment">// If it belongs before Cur, put it there</span>

      <span class="codekeyword">if</span> (strcmp(Cur->Name,Iter->Name) > 0)

      {

        <span class="codecomment">// Remove Iter from its location</span>

        <span class="codekeyword">if</span> (Iter->Next)

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

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



        <span class="codecomment">// Insert Iter before Cur</span>

        Iter->Prev = Cur->Prev;

        <span class="codekeyword">if</span> (Iter->Prev)

          Iter->Prev->Next = Iter;

        Iter->Next = Cur;

        Cur->Prev = Iter;



        <span class="codecomment">// Set modified flag</span>

        Changed = true;

      }



      <span class="codecomment">// Next iteration</span>

      Iter = Iter->Next;

    }



    <span class="codekeyword">if</span> (Changed)

    {

      <span class="codecomment">// Start sorting from the beginning again

     // Get to the beginning again</span>

      <span class="codekeyword">while</span> (Cur && Cur->Prev)

        Cur = Cur->Prev;



      <span class="codecomment">// If an element exists, Iter is the

     // next element</span>

      <span class="codekeyword">if</span> (Cur) Iter = Cur->Next;

    }

    <span class="codekeyword">else</span>

    {

      <span class="codecomment">// Go to the next value</span>

      <span class="codekeyword">if</span> (Cur) Cur = Cur->Next;

      <span class="codekeyword">if</span> (Cur) Iter = Cur->Next;

    }

  }

  <span class="codekeyword">return</span> 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.



<span class="codekeyword">if</span> (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



<span class="codekeyword">if</span> (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



<span class="codekeyword">if</span> (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



<span class="codekeyword">if</span> (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
© Copyright Chris Bennett, 2000-2001








Comments

Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS