Linked Lists – Adding and Deleting

Getting Started

In my last blog post I showed how I setup a basic board game with an array of linked lists. Now I’m going to show you some straight C code to add a unit to the board. I used a standard WIN32 console application, just to get past the complex interface code. My purpose is to show the linked list part.

First, we’ll need a structure:

struct Unit
{
 int Offense;
 int Defense;
 (Unit *) Next;
};

This structure will store the variables that represent the unit offense and defense numbers. The “Next” variable is a pointer to the next unit node in the linked list.

The game board

The game board is nothing more than a 4×4 array of Unit structure pointers that I declared globally:

Unit * PlayingBoard[4][4];

The problem with this array is that each cell has an unknown value in it. So we’ll need a function to make sure all cells contain a NULL value to begin with. I called that function “InitializeBoard()”:

void InitializeBoard()
{
    for (int i=0;i<4;i++)
    {
        for (int j=0;j<4;j++)
        {
            PlayingBoard[i][j] = NULL;
        }
    }
}

Add a Unit

Now, we’ll need a way to add a unit to the board. I want to set this up so the whole “pointer” arrangement is hidden from the game designer. I just want to use pointers inside the lowest level functions. This will prevent someone else from having to do all the allocation and de-allocation when they can just call the low-level functions that create pieces and delete pieces. So I’m going to use the malloc command in this function to get enough memory to use as my structure. To make sure I have the exact amount of memory that I need, I used the “sizeof” command with the structure name.

void AddUnit(int pUnitType,int pX,int pY)
{
    int liOffense = 1; // default to soldier
    int liDefense = 1;

    if (pUnitType == 1) // tank
    {
        liOffense = 3;
        liDefense = 5;
    }

    if (pX < 4 && pX > -1 && pY < 4 && pY > -1)
    {
        Unit * p = (Unit *)malloc(sizeof Unit);
        if (p)
        {
            p->Next = PlayingBoard[pX][pY];
            PlayingBoard[pX][pY] = p;
        }
    }
}

Notice how I checked to make sure that the x and y coordinates that were passed in as parameters are within the range of the board. Don’t assume anything! I also made sure that the malloc command returned a valid pointer. If not, then the playing piece will not be added to the board. There should be a warning message recorded someplace so that it can be checked after testing the game to see if any memory problems had occurred during the game. If this type of memory problem occurs, then the playing piece won’t show up, but the game will continue to work without crashing.

Delete a Unit

Now, it’s time to delete a unit:

void DeleteUnit(int pX, int pY)
{
    if (pX < 4 && pX > -1 && pY < 4 && pY > -1)
    {
        if (PlayingBoard[pX][pY])
        {
            Unit * p = PlayingBoard[pX][pY];
            PlayingBoard[pX][pY] = p->Next;
            free(p);
        }
    }
}

Again, I checked to make sure that the x and y parameters are inside the actual board. Then I check to make sure that the element at that grid location is not NULL. Don’t forget this step, because there might not be a unit at the location that the function wants to delete. Now for the tricky part. First we have to assign the top unit (the one linked to the board) to a temporary pointer, that I called “p”. Then we can assign the board position to the “Next” pointer of that Unit. This will cause the stack to shift up one. If “Next” is equal to NULL, then that will just get assigned to the board and no unit is sitting on that board position. If there is another unit attached to next, then it will get assigned to the board.

The last line will free the temporary pointer to the Unit we’re trying to actually get rid of. This returns the memory back to the operating system.

Tying it Together

Now, we need to actually write a program that uses all the above pieces. You’ll need to add a stdlib.h header declaration at the top. That is where the malloc and free commands reside. You’ll also need to add any function declarations at the top of your file to make sure they can be called:

#include <stdlib.h>

// function declarations
void InitializeBoard();
void AddUnit(int pUnitType, int pX,int pY);
void DeleteUnit(int pX, int pY);

Then, make sure you call the InitializeBoard() function first. After this, you can call AddUnit and DeleteUnit for any square on the board.

To download the complete CPP file click here: linked list source code file.

What’s Next?

If you typed in the code above (or copied and pasted), you’ll notice that this is not really a “game” yet. What it would take to make this into something useful is a few more low-level functions. One function that will be necessary is a complete board clear. You’ll have to do a while loop on a board cell and call Delete unit until a NULL is detected. Then do that for every cell. You could change the DeleteUnit function to return a true/false depending on if the “Next” unit was NULL or not. That could signify if there are any additional units at that cell. Then just created a function that calls DeleteUnit until false for each cell.

Other functions needed are a function to render the units on the screen. This, of course, depends on what you want to be displayed. If you just want to work on the game engine first and ignore the graphical front end, you can just setup a dumb and dirty text-based interface to use symbols to represent each unit on the playing board. Or you can go for the cool graphics first and get it to look right before you start working on the game AI.

You’ll need functions to read and write the offense and defense numbers. Since the top unit is the only unit fighting at a time, then only the top defense and offense matter. Remember the goal is to keep all the pointer code inside the lowest level units. Make these units perform the minimum task they need to perform, then do the complicated stuff by calling these functions.

I hope this blog post helps you to learn pointers better.


Leave a Reply