Tech Article #1: Data structures

Once in a while I will post entries that are more technical in nature. This is the first of them. You should read it anyways, as you'll see the benefit for users at the end.

Last night I was reading about data structures. The folks over at XNA Game Studio have written a four-part article on these, and it made for some excellent reading. Well, I haven't read Part IV yet, but the first three were very cool.

Data structures have to do with storing, retrieving, analysing, and modifying data. In my case, these structures will hold things such as all the aircraft that are in the air, their position, altitude, flightplans (I am considering having overhead traffic at both high and low altitude), etc., as well as anything else that gets bunched up in collections of the same kind.

There are different types of data structures and, like aything else in life, each has its pros and cons. The existing data structures in C# and XNA, and their brief descriptions, are:

- Arrays: A size-defined sequence of data types. Imagine a specific-sized box. Now add, say, 17 of them side by side, glued together. That would be a 17-item array. It is very fast to add and retrieve information, but if you have to change its size by suddenly adding another item in the middle, things get slow. Good for a collection of a static number of items (i.e. number of taxiways in an airport. Those don't change very often).
- Lists: Similar to arrays, except the number of "boxes" is not defined, so they are a little more flexible. Better to hold a collection of items whose total number is unknown or changing over time (i.e. number of arriving flights)
- Collections: Very similar to Lists, except these are good for inheritance (for object-oriented programming, inheriting is making a copy of an object that you can then customize for your own needs)
- Linked Lists: These are very interesting. They are like an array, except instead of being boxes that are glued side-to-side, these are boxes that know where the previous and next are. They could be half a world apart, but if you looked at one box, it would have the address of its predecessor and its successor. The cool thing about this is if you have to add a new itemin the middle of the existing items, you just put it in and change the addresses of predecessors/successors accordingly. The bad part is if you are looking for the last box, your code has to run through every box, starting with the first one, before it can find the last.
- Stacks: Exactly as their name says, these are stacks where you add an object and it goes on top of the stack. When you retrieve an object, they come out in LIFO order. LIFO is Last In First Out. Think of a narrow dead end street being used to park cars. You can only remove the car that was parked first after all the previous ones behind it have been removed. How does this help TowerSIm? Not sure yet, I'm not planning on having vallet parking :).
- Queues: Same as Stacks, but FIFO. You guessed it, First In First Out (i.e. a list of aircraft that have requested clearance).
- Dictionaries: Part IV which I still haven't read.
- Trees: Part IV which I still haven't read.

Pretty cool right? Well, for me it is :). Understanding these will ensure that I use the proper ones for different things, and will give you, the user, the highest possible frame rate.