Introduction to Pointers, Structures and Linked-Lists Part 9

Introduction to Pointers, Structures and Linked-Lists Part 9
Class Design
by Chris Bennett aka Dwarfsoft

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:

typedef class LinkedList *LinkedListPtr_t;
class LinkedList
{
public:
    LinkedListPtr_t Next() { return _Next; }
    LinkedListPtr_t Prev() { return _Prev; }
private:
    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

typedef class LinkedList *LinkedListPtr_t;
class LinkedList
{
public:
    // Constructors
    LinkedList() : _Next(NULL), _Prev(NULL) {}
    LinkedList(LinkedListPtr_t Prev) : _Next(NULL), _Prev(NULL)
    {
        if (!Prev) return;
        _Prev = Prev;
        // if this is in the middle of two items, insert it
        if (Prev->_Next)
        {
            _Next = Prev->_Next;
            _Next->_Prev = this;
        }
        // Add this node to the list
        Prev->_Next = this;
    } 
    ~LinkedList()
    {
        if (_Next)
        {
             _Next->_Prev = NULL;
            delete _Next;
        } 
        if (_Prev)
        {
             _Prev->_Next = NULL;
            delete _Prev;
        } 
    } 
    LinkedListPtr_t AddLast()
    {
        if (_Next) return _Next->AddLast();
        _Next = new class LinkedList;
        _Next->_Prev = this;
        return _Next;
    } 
    bool Remove()
    {
        if (_Prev)
        return _Prev->_Remove(this);
        if (_Next)
        return _Next->_Remove(this);
    }
    LinkedListPtr_t Next() { return _Next; }
    LinkedListPtr_t Prev() { return _Prev; }
private:
    bool _Remove(LinkedListPtr_t That)
    {
        if (That->_Prev)
            That->_Prev->_Next = That->_Next;
        if (That->_Next)
            That->_Next->_Prev = That->_Prev;
        That->_Next = NULL;
        That->_Prev = NULL;
        delete That;
        return true;
    } 
    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:

class 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.

typedef struct
{
    char 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.

typedef struct sLinkedList
{
   struct sLinkedList *Next;
   struct 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.

class cLinkedList
{
private:
   //Typedefs
   typedef struct sLinkedList
   {
      struct sLinkedList *Next;
      struct sLinkedList *Prev;
      Data_t Data;
   } LinkedList_t, *LinkedListPtr_t;
public:

   cLinkedList() : _Root(NULL)
   { }
   ~cLinkedList()
   {
      LinkedListPtr_t Temp, Cur = _Root;
      while (Cur)
      {
         Temp = Cur->Next;
         delete Cur;
         Cur = Temp;
      }
      _Root = NULL;
   }
   bool AddLast()
   {
      LinkedListPtr_t Cur = _Root;
      while (Cur && Cur->Next)
         Cur = Cur->Next;
      if (Cur)
      {
         Cur->Next = new LinkedList_t;
         Cur->Next->Prev = Cur;
         return true;
      }
      return false;
   }
private:
   //Variables
   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

Search for specific node
Sorting
Deleting of specific node
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.

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