Okay, let’s begin with what I mean by the term “Data Structure”. Data Structures is a data organization, management, and storage format that lets users or developers access and/ or modify data more efficiently. These structures are a collection of data values with relationships. And among those, some functions and operations can be applied to said structures or data.
The most commonly used data structures are listed:
- Array
- Hash Table
- Linked Lists
- Stack
- Queue
Please note before we go on, I will not be explaining the allocation and memory applications of each data structure; that will be another lecture.
The aforementioned data structures are used almost every time a developer writes a program. And some of these most of us may not even know we use. This may be due to it only being used by the compiler or interpreter or written into a library that we installed. Without these simple structures, you cannot write the complex programs that we see in everyday life.
Now, I am going to start with what an Array is. An array is a collection of items that are stored in memory locations. This data structure aims to store values or data of the same type in a set memory location.
Here is a code example:
local MyArray = {1,2,3,4,5}
Here we see a local variable called “MyArray”. This array is set to store objects of the class int. We can also do this using strings, vectors, or even user data. But it’s also worth noting that there are certain uses where arrays are not as useful as we may believe. This is because arrays allocate memory based on the number of items and the size of the array. This means the more we add, the more memory it takes up. And the more the array holds, the slower it is to find something.
This leads me to the next data structure most of us have used in everyday development. The hash table, aka dictionary, every language out there calls it something different. Ruby is called a Hash; in Java, it’s called a set, and the list goes on. But the point of this is to bypass the problem that arrays have. This problem is that we can’t simply find a value without iterating the whole array. This means that it can slow down our code.
Here is a code example:
local MyArray = {"Apple", "Pear", "Peach", "Grape"}
local MyHash = {
Apple = 1;
Pear = 2;
Peach = 3;
Grape = 4;}
Here we can see an array and a hash table. If we were to want to get an Apple from the Array, we would have to use loop the table. Roblox gave us a table library to do this for us, but internally it’s doing the same as this code provided:
for Index, Value in next, MyTable do
if Value == "Apple" then
return Index
end
end
This can slow down code greatly if you have a large number of entries in the array. If we were to look at a hash table, we could see that we can instantly pull the data.
MyHash.Apple
Now we have nice and neat code that is much more efficient than the alternative. However, what if you wanted to have something that acts like an array but connects more like a dictionary. That’s where linked lists come into play. This data structure has a head node that links to an end node; this repeats for every object in the structure. I wrote up a Lua version if you are interested in looking, as I cannot simply provide an example without coding the whole structure.
Now that we have talked about the holder-type data structures, we can talk about the more advanced concepts given with the final 2 I will be talking about.
The Stack is a beneficial data structure that many developers overlook. The Stack is a structure that runs operations in a certain order. This order is abbreviated using LIFO(Last In First Out). This means the last item that we put in will be the first item out. Think of it like stacking plates; the plate on top will come out first even though it was the last one put down. This is very useful for keeping track of code compilation and is used almost every time you run a Lua script. That’s why you hear the term stack when talking about functions and variables when you learned Lua.
Now we can move on to the queue. This is a fundamental data structure that is used in almost everything. When you download something from a website, your browser adds the file to a download queue. This same concept applies when you’re searching for things on the web. The way that this structure works is relatively simple. It can be compared to the way a line works. When your standing in line at the grocery store, the first person there goes first, the last person there goes last. This can be abbreviated with the term FIFO(First In First Out). This can be used to keep track of player requests. It can also be applied when you want cross-server communications and need to limit the amount of network traffic. Really the possibilities are endless. I linked an example of this below:
Data structures are very complex but simple at the same time. We use them every time we write code, even if we don’t realize it. But they are crucial to the development of Roblox games as a whole. There are also many more data structures, such as Binary trees. However, I cannot fit those into this short explanation as those are advanced topics unless you have solid foundational knowledge on these topics.
I hope you learned something!
Sam