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 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.

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. But if you divided 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 have to look at 13 cards at most, dividing 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'd 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'd be a good idea to write down an index of 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:

• Retrieving data.
• Adding data.
• Removing data.
• 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.