Using a linked list in your game

This article presumes that you already have some JavaScript experience. It should not be treated as help to leaning JavaScript, but rather as help to improve the knowledge you already have. You need to know at the very least about arrays and objects to properly benefit from this article. In this article, I will continue on way past what which you need to know to merely use the linked list. Feel free to stop reading once you feel you understand how to use a linked list, or continue reading if you want to learn the juicy features and tricks.

What exactly is a linked list?

Linked lists are useful data structures that can be used in a large amount of clever ways. We use linked lists to store objects in a way that is very similar, yet slightly different, to arrays. A linked list in use could look something like this:

Start Linked List
"this is entry one"
"this is entry two"
"this is entry three"
"this is entry four"
"this is entry five"
"this is entry six"
"this is entry seven"
End Linked List

In this imaginary example (the linked list doesn't actually look like that) I have filled a linked list with strings. The great thing about JavaScript is that just about everything are objects. Be it strings, numbers, functions, arrays or your own custom objects. You can practically store anything in place of those strings.

But wait a minute, this looks an awful lot like an array. Why should you bother using a linked list instead of an array? Linked lists and arrays, although very similar, have a key difference in how they are built up that could really affect your JavaScript performance. Let's duplicate our previous example with an array instead.

myArray[0] = "this is entry one"
myArray[1] = "this is entry two"
myArray[2] = "this is entry three"
myArray[3] = "this is entry four"
myArray[4] = "this is entry five"
myArray[5] = "this is entry six"
myArray[6] = "this is entry seven"

The most apparent diffrence here is that in an array, each of our objects are assigned a number (although it can be a little confusing since we start counting at 0 instead of 1). For example, "this is entry five" is assigned to array position 4. A linked list does not do this, not even behind the scenes. What's the practical difference? If we wanted, we could fish out information out of the array based on these numbers. We could code "alert(myArray[4])" and JavaScript would instantly throw "this is entry five" in our face. A linked list cannot do this.

But wait a minute, why would we want to use a linked list if it can't do the same things as an array can do? There is actually an advantage to not having your objects indexed by numbers in this way. I'll explain why.

Imagine that we wanted to delete one of these objects. If we wanted to delete the content of myArray[3], the array would end up looking something like this:

myArray[0] = "this is entry one";
myArray[1] = "this is entry two";
myArray[2] = "this is entry three";
myArray[3] = null;
myArray[4] = "this is entry five";
myArray[5] = "this is entry six";
myArray[6] = "this is entry seven";

However, if we did the same thing to our linked list, it would look something like this:

Start Linked List
"this is entry one"
"this is entry two"
"this is entry three"
"this is entry five"
"this is entry six"
"this is entry seven"
End Linked List

Can you spot the difference complared to the linked list earlier? The "this is entry four" is gone! And the difference is, unlike the array, there is no hole left in our collection. This can be incredible useful in certain situations.

So, does this mean that unless you need to access your objects directly like we demonstrated above you should always use the linked list rather than the array? Absolutely not! Although the linked list avoids certain problems that the arrays has, it's still a data structure we have programmed ourselves in JavaScript. The array is a native data structure to the JavaScript language, and will always be faster no matter how well we code our linked list. The exception is if we encounter a very specific problem mentioned below.

So, what's some good examples of when we might want a linked list? The linked list is particulary useful when you have a large number of objects that gets deleted at random. One example could be the the monsters in a JavaScript game. As the player slays the monsters, we need to delete them out of our list.

If we attack with one thousand killer bees who are saved inside an array, and the player stomps on four of them, then our array will have four holes. The two options that the programmer can do in this case is either to merely skip over these holes as the loop comes to them:

for(var i=0;i<monsters.length-1;i++) { //regular unoptimized for loop
  if(monsters[i] != null) { //if monsters[i] has not been deleted
    updateMonster(monster[i]); //run our update function for this monster
  }
}

But if we do this, as the game progresses, there will be more and more holes in the array. What a nightmare it would be if there was only 43 monsters alive in the game, but the size of the monster array was 500 objects big, resulting in 467 holes!

The other alternative is to clean up these holes manually so they won't appear in our updateMonster loop. It could be done something like this:

function killMonster(n) { //n here is the array position of the monster
  monsters[n] = null; //delete the monster
  for(var i=n;i<monsters.length-2;i++) { //start the loop at the deleted monster
    monsters[i] = monsters[i+1] //push all monsters after the deleted one a step up
  }
  monsters.length = monsters.length-1; //we make the array one slot smaller
}

Here, after deleting a monster, we clean up the array by reordering the monsters positions so there won't be any hole, and readjust the array size to account for there being one less monster. Doing it this way will work pretty much solve the issue no matter what the situation, but it's a very bad solution. If we have one thousand monsters, we could be forced to push 999 monsters up one array position should the first one die. Hardly an optimal solution. Imagine if you make a very action packed game with tons of small enemies that constantly spawn and die. This cleaning up effort will definitely take a big chunk of your performance, doing hundreds of loop iterations per enemy kill.

The linked list elegantly avoids these problems. It can be easily visualized as a chain. If we remove one chain link from the chain so that it is disconnected, then all you need to do is attach the chain links on each side of the hole, and behold, the chain is whole once again without much effort. This is pretty much exactly how the linked list works.

Realize that the attaching of the two chain links does cost some performance, but it doesn't grow as the size of the chain grows. It doesn't matter if you have ten monsters or ten billion monsters. The operation is exactly the same, unlike the array where the operation grows alongside with the array size.

The key lesson here is that the linked list offers no new features you can't do with an array. It just does some things in a very special way that could save you performance in specific situations. As you grow experienced with using linked lists, you'll instantly recognize which problems are best solved with an array, and which are best solved with a linked list.

Okay, enough theory. Let's find out how a linked list is actually used. How the heck are you supposed to use a linked list if you can't access it by a number like that?

A linked list can be accessed in the following ways: We can always fetch the top and bottom objects, in this case, the "this is entry one" and "this is entry seven". And we can also fetch the objects above and under an object we have already fetched. Meaning, if you are currently working with "this is entry three", then you can access "this is entry two" and "this is entry four". Having these rules in mind, it shouldn't be hard to imagine how you could make a loop that goes though all the entries.

However, you don't really need to think too hard about this part if you plan on using my linked list library. I have already constructed a loop for you, so you can start using a linked list instantly. Here is an example that should get you going:

myList = new LinkedList();
myList.add('This is the first entry');
myList.add('This is the second entry');
myList.add('This is the third entry');

var i,loop=myList.foreach();while(i=loop.next()) {
  document.write(i);
}

Pardon me about the ugly loop line. I did my best to make the loop as pretty as possible, while still making it as fast as possible. You really don't need to understand how it works. All you need to do is replace the "myList" part with the variable containing your list, and replace "i" with whatever you want your object to be put into for your usage.

It works exactly like a normal loop in that you can use the break or continue statements, and you can stack as many loops as you want (you'll have to use different variable names for "i" and "loop" for each stacked loop though). The loop in this example will simply write out everything inside the linked list. It's fairly simple once you can look past the strange loop syntrax.

So, let's go on to the next thing, deleting things inside a list. Deleting things in an array was easy. In a linked list, it's slightly more tricky, but nothing hard once you grasp it. You can easily delete any object inside your linked list like this:

myList.removebyobject('This is the second entry');

There is one thing you should be aware of though. This method of deleting is barely faster than the way you delete and clean up things inside an array. To truly unlock the speed behind the linked list, you have to understand what a link is. However, you now know the basics behind the linked list, You can stop reading here and just start using the linked list. It's very easy to replace the slow things you do now with faster alternatives once you understand more.

When working with a linked list, you can access objects like demonstrated above, but you can also access the links themselves. Links are what keeps a linked list together. Each link holds one object. So in our example at the top where we have seven entries, there are seven links hidden behind the scenes, one for each entry. They also keep track of which links are above and bellow them. Don't worry, I'll show with examples.

So, in reality, a linked list looks a bit more like this:

Start Linked List
link: "this is entry one"
link: "this is entry two"
link: "this is entry three"
link: "this is entry four"
link: "this is entry five"
link: "this is entry six"
link: "this is entry seven"
End Linked List

Now, as I mentioned above, you can always access the first and the last link in a list. You can easily do this as follows:

myList.first

if you want to access the object ('this is entry one') of the first link, you access a property named "value":

myList.first.value

so, pretty straightforward, you can do this:

alert(MyList.first.value)

This is pretty much identical to typing alert(myArray[0]). But as I mentioned earlier, all links know the next and previous links. You access these with the "next" and "previous" properties of a link, like this:

alert(MyList.first.next.value); //alerts "this is entry two"
alert(MyList.first.next.next.value); //alerts "this is entry three"
alert(MyList.last.previous.previous.next.previous.previous); //alerts "this is entry four"

If you think this looks bothersome and complicated, then fear not, because you'll never use the "next" and "previous" properties in this strange way. Just understand that you use the properties to navigate the linked list.

So, why would you need to work with the links like this rather than the objects? Well for starters, it's a lot faster, and it gives you a lot more flexibility and power.

myList.removebyobject('This is the second entry'); //this is very slow
myList.removebylink(MyList.first.next); //this is very fast

Let's use these things we have learned in an actual practical example. Let's say we are making a TODO list.

myList = new LinkedList();
myList.add('Clean up office');
myList.add('Go to the store');
myList.add('Pay bills');
myList.add('Find lost keys');
myList.add('Make dinner');

Now, let's make a custom loop that does our TODO list.

while(myList.first) { //as long as the first link contains something
  doTask(myList.first.value); //we do the the task that's first in the list
  myList.removebylink(myList.first); //remove the first link, second link automatically replaces it
}

Great huh? Not only is this code easy to read and understand (provided that you know how a linked list works), but it offers another great feature! Let's say that there is a possibility we might find our lost keys while doing our other tasks. We can add this:

while(myList.first) {
  doTask(myList.first.value);
  myList.removebylink(myList.first);
  if(keysfound == true) {
    myList.removebyobject('Find lost keys');
  }
}

In this oversimplified example (it won't work at all if you copy it), should we find our keys at any point while doing our other tasks, then the "Find lost keys" job will be removed from the list. And since we aren't using an array, there will be no hole in it's place. Instead, "Pay bills" will be directly followed by "Maker dinner". Linked lists are great because we can remove and add entries to it at will without any problems.

This can be very useful in games. For example, instead of a regular everyday TODO list, you could make a TODO list AI for your monster, with entries like "get powerup" and "attack player". Should the powerup be taken by the player before the monster can get it, or should the player die before the monster can attack him, it won't be a problem since you can easily remove these objectives from the list without problems, or add them should the monster suddenly encounter a situation that requires a new task on the TODO list, such as "open door".

Linked lists are very useful in the right situation, and very flexible. Please see the reference for a full list of all the properties and methods of the linked list.