Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


Like
0Likes
Dislike

Introduction to Pointers, Structures and Linked-Lists Part 9

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

class data list linked return node next struct
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



Alright, I promised to step through class design and I think I should first off show how other people like to set up their classes. It is likely that you will take up this approach as most people
seem to have gone this way in the past. Taking for example a linked list we will have a look at how classes are usually set up to handle data and abstraction.


Just to recap on exactly what data abstraction is, we shall look at the following example:



<span class="codekeyword">typedef class</span> LinkedList *LinkedListPtr_t;

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

{

<span class="codekeyword">public</span>:

    LinkedListPtr_t Next() { <span class="codekeyword">return</span> _Next; }

    LinkedListPtr_t Prev() { <span class="codekeyword">return</span> _Prev; }

<span class="codekeyword">private</span>:

    LinkedListPtr_t _Next;

    LinkedListPtr_t _Prev; 

}


Why we would do this may not be immediately obvious, but if your class always checks that pointers are valid before they are set then people cannot just go



myclass._Next = 0xCCCCCCCC;


This helps to protect your data and make your class handle all errors internally. This aids stability greatly.


Now, on to the way OTHER people handle classes for a Linked List. I have already used the basic format of their methods above in that the current point of the Linked List has points to Next and
Previous. All we really need to add to the current methodology is the AddLast and the Constructor and Destructor



<span class="codekeyword">typedef class</span> LinkedList *LinkedListPtr_t;

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

{

<span class="codekeyword">public</span>:

    <span class="codecomment">// Constructors</span>

    LinkedList() : _Next(NULL), _Prev(NULL) {}

    LinkedList(LinkedListPtr_t Prev) : _Next(NULL), _Prev(NULL)

    {

        <span class="codekeyword">if</span> (!Prev) <span class="codekeyword">return</span>;

        _Prev = Prev;

        <span class="codecomment">// if this is in the middle of two items, insert it</span>

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

        {

            _Next = Prev->_Next;

            _Next->_Prev = <span class="codekeyword">this</span>;

        }

        <span class="codecomment">// Add this node to the list</span>

        Prev->_Next = <span class="codekeyword">this</span>;

    } 

    ~LinkedList()

    {

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

        {

             _Next->_Prev = NULL;

            <span class="codekeyword">delete</span> _Next;

        } 

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

        {

             _Prev->_Next = NULL;

            <span class="codekeyword">delete</span> _Prev;

        } 

    } 

    LinkedListPtr_t AddLast()

    {

        if (_Next) return _Next->AddLast();

        _Next = <span class="codekeyword">new class</span> LinkedList;

        _Next->_Prev = <span class="codekeyword">this</span>;

        <span class="codekeyword">return</span> _Next;

    } 

    <span class="codekeyword">bool</span> Remove()

    {

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

        <span class="codekeyword">return</span> _Prev->_Remove(<span class="codekeyword">this</span>);

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

        <span class="codekeyword">return</span> _Next->_Remove(<span class="codekeyword">this</span>);

    }

    LinkedListPtr_t Next() { <span class="codekeyword">return</span> _Next; }

    LinkedListPtr_t Prev() { <span class="codekeyword">return</span> _Prev; }

<span class="codekeyword">private</span>:

    <span class="codekeyword">bool</span> _Remove(LinkedListPtr_t That)

    {

        <span class="codekeyword">if</span> (That->_Prev)

            That->_Prev->_Next = That->_Next;

        <span class="codekeyword">if</span> (That->_Next)

            That->_Next->_Prev = That->_Prev;

        That->_Next = NULL;

        That->_Prev = NULL;

        <span class="codekeyword">delete</span> That;

        <span class="codekeyword">return true</span>;

    } 

    LinkedListPtr_t _Next;

    LinkedListPtr_t _Prev; 

};


This linked list is just a shell and does not actually contain any real data but serves us as a demonstration. This Linked List only adds a new node to the end of the list, and does none of the
useful things that Linked Lists should do either, but it serves for the demonstration. One thing you will notice is that when you use this class as a new variable:



<span class="codekeyword">class</span> LinkedList MyLinkedList;


The list will never be empty, there will always be a variable in the list linked to by the MyLinkedList variable. The way that I propose to write a feature like
this would be to use data encapsulation to completeness. Basically it treats the class as a handler for all the Linked List functions while having the actual Linked List hidden from the user. They
just interact with the class.


First of all we create a Data type outside of the class, which will make it easy for us to transfer data between the class and the calling program.



<span class="codekeyword">typedef struct</span>

{

    <span class="codekeyword">char</span> Name[50];

} Data_t;


There is nothing entirely special about the data, its just an example, now we get into the mechanics of the class. First we look at the linked list itself.



<span class="codekeyword">typedef struct</span> sLinkedList

{

   <span class="codekeyword">struct</span> sLinkedList *Next;

   <span class="codekeyword">struct</span> sLinkedList *Prev;

   Data_t Data;

} LinkedList_t, *LinkedListPtr_t;


Usually I use some form of Identifier for each node so that I can implement a quick search. What I usually use as a matter of preference alone is both a Name value and an Index value. The Name
value is mainly used for User searches and allows for a fairly descriptive title of the Node, where Index provides pure functionality within the program by allowing quicker searches and more direct
addressing methods for the node. Usually I try to keep the two from contradicting each other by doing a sort either on loading the data, or upon saving the data. This way they are sorted
Alphabetically for the Naming, and I reissue the Index based on their position in the list.


As for why using some kind of Identifier is a good idea at this point in a project, well we will get on to Saving and Loading Files later on, but as it is there is very little good that Pointers
will do for referencing, and although we are only using a linked list at the moment, where everything is linked incrementally and saved incrementally, later if you choose to have nodes that reference
arbitrary nodes all over the list, then how do you go about referencing them? Try to keep a name that a User can interact with along with a Computer oriented referencing system (like an Index
number).


Now on to using this Linked List structure in our encapsulating class.



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

{

<span class="codekeyword">private</span>:

   <span class="codecomment">//Typedefs</span>

   <span class="codekeyword">typedef struct</span> sLinkedList

   {

      <span class="codekeyword">struct</span> sLinkedList *Next;

      <span class="codekeyword">struct</span> sLinkedList *Prev;

      Data_t Data;

   } LinkedList_t, *LinkedListPtr_t;

<span class="codekeyword">public</span>:



   cLinkedList() : _Root(NULL)

   { }

   ~cLinkedList()

   {

      LinkedListPtr_t Temp, Cur = _Root;

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

      {

         Temp = Cur->Next;

         <span class="codekeyword">delete</span> Cur;

         Cur = Temp;

      }

      _Root = NULL;

   }

   <span class="codekeyword">bool</span> AddLast()

   {

      LinkedListPtr_t Cur = _Root;

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

         Cur = Cur->Next;

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

      {

         Cur->Next = <span class="codekeyword">new</span> LinkedList_t;

         Cur->Next->Prev = Cur;

         <span class="codekeyword">return true</span>;

      }

      <span class="codekeyword">return false</span>;

   }

<span class="codekeyword">private</span>:

   <span class="codecomment">//Variables</span>

   LinkedListPtr_t _Root;

};


Now that we have the basic Add and a generic delete (on destruction of the host class) you can feel free to add anything else you would like in. Suggestions at this point are for


  1. Search for specific node
  2. Sorting
  3. Deleting of specific node
  4. Editing of data of a specific node.

Usually what would happen to make the class usable is under the private variables you would add a "SelectedNode" which would be a NULL pointer if nothing had been selected, or after a Search it
would hold a reference to that node.


To build in Editability you would then have a function along the lines of "GetCurrentData" which would return the address of the Node's Data. That way the class only allows access to the Data and
nothing that is not relevant to the application. Basically, the linked list itself is not whats important, its only the data that it contains. This is what we mean by Data Encapsulation.


Alright, I think there has been enough food for thought on this article, so pace yourself with the homework I have set you, and get ready for the next article on Inheritance.


Author: Chris Bennett aka Dwarfsoft
Contact: dwarfsoft@hotmail.com
June 7th, 2003
© Copyright Chris Bennett, 2003








Comments

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




PARTNERS