Jeremy Visser

A word of warning: don’t read this post. You’ll regret it. It’s basically a convoluted regurgitation of my brain with regards to using linked lists in C. Here be dragons.

In C, creating variables, and storing values in them is quite easy. You just declare them as such:

int i;

And then perform whatever operations you want with them:

i = 2;
i = i * 2;
printf("%d", i); /* 4 */

There is also a cool thing called struct, which lets you create a big variable that contains lots of sub-variables. It works a bit like this:

typedef struct tagGameObject {
	int x;
	int y;
} GameObject;

Then, you can create ‘instances’ of it like this: (note the scare quotes, because C isn’t really object-oriented)

GameObject rocket;
GameObject monster;

rocket.x = 20;
rocket.y = 25;

monster.x = 300;
monster.y = 250;

printf("rocket is at (%d,%d)", rocket.x, rocket.y); // rocket is at (20,25)
printf("monster is at (%d,%d)", monster.x, monster.y); // monster is at (300,250)

Now, let’s just say I wanted to have 3 monsters. I could create three of them like this:

GameObject monster_1;
GameObject monster_2;
GameObject monster_3;

monster_1.x = 100; /* ...etc. */

However, that’s a bit tedious. What if I wanted 20 monsters? Surely I don’t declare each one individually. Nope — you can use arrays for that, which are pretty easy.

GameObject monsters[20];

monsters[0].x = 100;
monsters[1].x = 110;
monsters[2].x = 120; /* ...etc. */

But that has a problem. I’m stuck with 20 monsters all at the same time. Even if you are not using all monsters in the array, the memory is always allocated for each one. Sometimes that is what you want. Sometimes it is not. What if you wanted to be able to create and delete monsters at wish, and it didn’t matter how many you had at any one time?

Enter linked lists.

Linked lists are a way for you to have an arbitrary number of structs allocated and de-allocated at will, with the ability to (fairly) efficiently iterate through and access them all.

The key element of linked lists is a pointer inside the struct which points to another struct of the same type. Typically this is called something meaningful like next. An example:

typedef struct tagGameObject {
	int x;
	int y;
	struct tagGameObject* next = NULL; /* used for linked lists */
} GameObject;

But now we see that we’ve moved beyond arbitrarily declaring variables like before (monster_1, monster_2, or arrays like monster[20]). We need to allocate them on-the-fly. Luckily, C has a function to do just that: malloc().

So let’s allocate ourselves a new GameObject for posterity. The only parameter malloc needs is the amount of memory to allocate for our needs. And how much space will we need? Enough space to fit a GameObject in memory. And how do we know how big a GameObject is? The sizeof() function. Like so:

malloc(sizeof(GameObject));

Okay, um. So what did that do? Well, it created a GameObject somewhere out in the ether (i.e. somewhere in memory, but we don’t know where). To try and illustrate, let’s see what happened before:

So that’s just like normal. A simple program with two integers, declared as you’d expect: int some_variable; and int another_variable; Notice the arrows connecting the two variables to the program code — every time you type ‘some_variable‘ or ‘another_variable‘ in the code, it knows where to find the value in memory. So, after that false start (apologies, everyone — I’d make a terrible story writer), let’s run malloc() (for real, I promise) using the code we wrote before:

So see that ‘GameObject’ sitting out there? Yep. It has no arrows pointing to it. Which means that we have some GameObject out there, dynamically allocated (yay!), but no way to access it! So we need a pointer. By day, pointers point to locations in memory (and by night, they fight crime when dereferenced). We declare a pointer with a * symbol, and use it like this:

GameObject* m = malloc(sizeof(GameObject));

So the function malloc() gives us the pointer we need to find out where in the ether our GameObject is. To illustrate this, see the new arrow in this picture:

The new arrow is the pointer, which tells us where in memory it is.

So, to summarise my point so far, pointers by themselves aren’t all that useful. To make them useful, we need to make them point at real locations in memory, where we have allocated some object for us to work with. The reason we do this is because with linked lists, we don’t want to know how many monsters or rockets or bullets or pots of petunias we are going to need. And because of that, we can’t hardcode them into the application. So we use pointers.

So let’s make our pointer point to something useful. Just for a recap, I’ve declared our pointer again, then I’ll actually allocate some memory for it and point the pointer to that location of memory.

GameObject* monster = NULL;

/* ...then some time later, back at the ranch: */

monster = (GameObject*) malloc(sizeof(GameObject));
/* now our 'monster' pointer points to some real memory */
monster->x = 100; /* ...and we can set stuff like so */
monster->y = 150;

I have to use monster->x instead of monster.x because it is a pointer (for various technical reasons that I don’t understand apart from the fact that you need to ‘dereference’ it). And yes, I could have also done the declaration of the pointer with malloc() in one line, but honestly — who cares? I’m already coding in C — I’m feeling sadistic enough as it is.

So, yeah, I seem to be getting a little side-tracked. So what’s with this ‘next‘ pointer I mentioned too many paragraphs ago? Well, we use next to ‘point’ to another monster/rocket/bullet/petunia that we have allocated. And that object we are pointing to can in turn point to another object. Let’s see how this works.

/* create our first monster */
GameObject* monster = (GameObject*) malloc(sizeof(GameObject));

/* and another monster */
monster->next = (GameObject*) malloc(sizeof(GameObject));

/* and yet another monster */
monster->next->next = (GameObject*) malloc(sizeof(GameObject));

Now the only variable we have in the code pointing to any of the monsters is the first one (‘monster‘), which we declared on the first line. Now, the last ‘next‘ in our linked list will always be NULL (as we specified NULL as the default when we defined the GameObject struct). This is very important for if we want to iterate through all the monsters. Some code that can iterate through our linked list is as follows:

GameObject* m = monster;
while (m) { /* i.e. while m is not NULL */
	printf("We've got a monster that is at (%d,%d).", m->x, m->y);
	/* maybe we'd draw the monster onto the screen at this point in a real game*/
	m = m->next;
}

So as you can see, we’re starting with setting our variable ‘m‘ to point to the initial monster, reading its data (in this case, its variables x and y), and then going to the next monster in the series (m = m->next). Because ‘while (m)‘ will only loop if m is not NULL, if we are at the last monster in the linked list (in which case, m->next will be NULL), the loop will stop, and we’re done iterating. No arrays; no for loops; no nonsense++.

Let me try and illustrate this once again with my über Inkscape skillz:

So yeah. We basically follow the yellow brick road of pointers through the ether.

No talk on linked lists would be complete with some monkey mojo to add a new item to the list. Here’s a function to do just that (along with a way to call it):

GameObject* add_object(GameObject** first)
{
	GameObject* new_object = (GameObject*) malloc(sizeof(GameObject));
	new_object->next = *first;

	*first = new_object;

	return new_object;
}

GameObject* monster = NULL;

/* add three monsters to our linked list */
add_object(&monster);
add_object(&monster);
add_object(&monster);

Quite simple, really. All that function does is create a new object, set its ‘next‘ value to the current first item, then set itself as the first item. And yes, I know — copy-and-paste coding is horrible. Sigh…the things I do for clarity.

Deleting an object from a linked list is slightly more involved (and won’t strain myself trying to explain it, so I’ll just post it here for reference), but not too bad. Here’s how it goes:

void del_object(GameObject** first, GameObject* object_to_del)
{
	GameObject* o;

	if (!first)
		return;

	if (object_to_del == *first) {
		*first = object_to_del->next;
	} else {
		o = *first;
		while (o->next && o->next != object_to_del) {
			o = o->next;
		}
		/* Okay, found it. object_to_del == o->next */
		if (o->next)
			o->next = o->next->next;
	}

	free(object_to_del);
}

GameObject* monster = NULL;

/* add three monsters to our linked list */
add_object(&monster);
add_object(&monster);
add_object(&monster);

/* let's delete the second one */
del_object(&monster, monster->next);

So basically, we iterate through all the objects until we find the one we want to get rid of, and remove it from being ‘next’, and free the memory for the object. Makes sense if you don’t try and understand my crappy code.

Well, I hope you enjoyed this explanation of linked lists, straight from the horse’s mouth. What I’ve written here is exactly how I understand linked lists in my head (after struggling to understand various other articles on the topic), so if one other person benefits from this article, it will totally make my day.