Copy LinkCopied!Data Structure

We generally call "data structure" the different ways to organize data in code. There are two aspects to data structures:

1. How the data is stored in the computer's memory. When scripting games in Godot, this part is handled by the engine itself.
2. How the data is partitioned in our code to make it easier to access.

In high-level languages like GDScript, you have little control over how the data is stored in memory, so it is not something you can influence. However, how you partition your data can dramatically impact performance and ease of access.

Copy LinkCopied!Data structures work like real-life partitioning and organization

Data structures are similar to how you would organize a library, a deck of cards, or a bunch of papers in the real world.

Suppose I gave you an unordered deck of 52 cards and asked you to find cards I name. If I asked you for the ten of spades, in the worst case, you'd have to look at all 52 cards to find it.

How could you make this task easier? You could divide the deck into four stacks based on the card suits (diamonds, clubs, hearts, or spades). Then when I say, "Give me the queen of hearts", you'd look at the stack of hearts, and you'd only have to look at 13 cards at most!

Splitting the stack into four divides the maximum lookup time by 4. If you ordered the cards or split them further, you could find the queen of hearts even faster.

That's the idea behind data structures: You partition your data to make it easier to find, add, or remove elements.

Here's another example: Imagine that you have a bunch of student files. You might naturally order them by the first letter of their family name. That would make finding a student whose name starts with a specific letter really quick.

However, if I asked you to give me the files of all the students who are 14 or older, that would still take a long time. If I asked you for this often, it would be a good idea to sort students by age, so you can find them quickly.

At the library, books are ordered by author, title, or subject to make it easier to find them. This example and the previous two are similar to how we structure data in code.

Copy LinkCopied!Why we care about data structures

We think about data structures to achieve different tasks efficiently:

1. Retrieving data
2. Adding data
3. Removing data
4. Sorting data

No data structure is equally good at all four of those tasks. If a data structure excels at one, it will be less efficient at some others. So, the choice of data structure depends on what you need to do with your data.

In Godot, the two building blocks for authoring more complex data structures are arrays and dictionaries:

• Arrays are the fastest at retrieving elements by index, appending and removing data at the end of the list, or looping through all elements.
• Dictionaries can be more efficient at inserting new elements anywhere in the data structure, and they are generally faster at looking up elements by key.