Basic Unordered Linked Lists
So my last blog posts were about pointers. I gave a little historical context to the fact that I’m a self-taught pointer maniac. The past 6 years is the longest stretch I’ve gone without using a pointer. That is because I now program using C# instead of C/C++. Sometimes I miss pointers. They’re so powerful. What I don’t miss about pointers and what I love about C# is the memory management aspect of it all. That’s why I’m so methodical about assigning nulls and checking before allocating and de-allocating memory. There are other tests that should be performed as well, and I’m going to talk about it right now.
What happens if your application runs out of memory? It could happen. It does happen. The C/C++ malloc command has a flag for that, it’s called null. Yup, you guessed it, when you attempt to allocate a pointer and there is no memory available, the malloc command returns a null pointer. So always check to make sure the pointer is not null before using it. Here’s an example from the sample code used in my previous blog post:
#include <stdio.h>
#include <stdlib.h>
int main()
{
char * mypointer = NULL;
if (!mypointer)
{
mypointer = (char *)malloc(1);
if (!mypointer)
{
// perform some sort of error reporting here
return -1;
}
}
*mypointer='a';
if (mypointer)
{
free(mypointer);
mypointer=NULL;
}
}
I returned a “-1”, that’s just my return for an error code in this sample. Your method might not return anything, and you might have to exit out of the program entirely. Anyway, it’s on to linked lists.
What is a Linked List and Why Use them?
I used to program games as a hobby. Nothing serious, just a hobby. I liked to play Avalon board games, mostly World War II style strategy games and I made an attempt at writing a C++ war game with a similar board design. Here’s what Panzer Blitz looks like:
One of the things I noticed about the hex shaped board locations is that it is really just an array where the odd numbered columns are shifted half way up or down. Here’s what I’m talking about:
As you can see by the cell numbers the hex board on the left is the same as the shifted square board in the middle and the same as the 4×4 array on the right. I used an array to represent the map positions of each piece.
Now, it’s on to the playing pieces. One of the fun aspects of these types of games is that you can stack pieces. Here’s a sample picture I found using Google (I’m just trying to avoid dragging out the game and taking photos myself):
This is where pointers become fun. Yes, I said fun. But first, it’s time for a little diversion, let me explain what a linked list looks like in an abstract diagram form.
First, I’m going to use structures to store information about each playing piece. Each tank and soldier (I’m really trying to keep this simple) will have one structure allocated in memory and then I’m going to link them together into little stacks. Like this:
This is a list of three pieces, two tanks and a soldier. Inside each structure (not shown) is a variable that is the pointer to the next structure and the last structure points to null. The variable “P” here is the pointer to the first playing piece in the list. What I’m going to do here is setup a playing board that has an array of pointers. Each cell in the array is nothing more than a pointer, then I’ll initialize them all to null. When I place one or more pieces on the board, I just set one of the array cells to point to the top of the list or stack. Like this:
Now the basic game structures are setup. The rendering engine can run through the array and paint the associated background image (which can be stored in a separate array) and if the pointer in this array is not null, then render the top piece offset by the number of pieces in the stack so the height is different depending on the number of pieces.
When the user drags a stack of pieces, the pointer at the array cell containing the stack can be copied to the new grid location and the old pointer in the array can be set to null. This will have the effect of moving an entire stack of playing pieces without moving a bunch of data. Just re-adjusting the cell location of the pointer to the stack.
One of the rules of the game is that the top piece is attacked first. Once eliminated, then the next piece in the stack is under attack. If the top tank in the sample game board above becomes destroyed in game play, then the top tank can be assigned to a temporary pointer, then the game board array cell can point to that tank’s “next” pointer. Then the first tank can be de-allocated. Poof, it’s gone:
If the last tank at that grid position is destroyed, then the same exact algorithm can be performed to set the grid to that tank’s “next” pointer and de-allocate that tank. The “next” pointer just happens to be null, so that board position is now empty, and the rendering function will just render the background.
I’m going to wrap this discussion up for now, but next time I’m going to do some example code to demonstrate the basics of how this is all performed.