• # Introduction to Pointers, Structures and Linked-Lists Part 9

General and Gameplay Programming

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


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;
{
public:
// Constructors
{
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;
}
{
if (_Next)
{
_Next->_Prev = NULL;
delete _Next;
}
if (_Prev)
{
_Prev->_Next = NULL;
delete _Prev;
}
}
{
_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:
{
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;
}
};


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
{
Data_t Data;


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
{
Data_t Data;
public:

{ }
{
while (Cur)
{
Temp = Cur->Next;
delete Cur;
Cur = Temp;
}
_Root = NULL;
}
{
while (Cur && Cur->Next)
Cur = Cur->Next;
if (Cur)
{
Cur->Next->Prev = Cur;
return true;
}
return false;
}
private:
//Variables
};


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

Report Article

## User Feedback

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

## Create an account

Register a new account

There are no reviews to display.

• ### Latest Published Articles

• #### Game Engine Containers - handle_map

Jeff Kiah This article explores the creation of a data container for game programming. This container is meant to take the place of C++ standard library containers such as std::map and std::unordered_map, with an alternative that stores data contiguously in memory.
• 34708 views
• #### Casual Connect 2018 Coverage

Beth Feldman GameDev.net's coverage of Casual Connect 2018 from Anaheim, CA.
• 268 views
• #### Postmortem: I Am Overburdened, Recaps and Numbers

Spidi provides a fully detailed breakdown of the development and business results of the release of "I Am Overburdened".