The Shape of Your Data Decides How Fast You Can Find It
A shopping list, a stack of plates, and a waiting line explain why programmers pick different containers.
Fireship · 100+ Computer Science Concepts ExplainedComputer memory is a jumble of data points. What matters is the container you put them in.
Probably the most useful container is the array, also called a list. It works like a shopping list, holding multiple data points in order. It also numbers each item starting at zero and counting up by one for each new entry. If you know you want the item at position 2, counting from zero, you can go straight to it.
You do not need numbers to make a list, though. In a linked list, each item points to the one after it. To find something, you follow the chain from link to link.
Sometimes the order you take things out matters more than finding one item. A stack works on a last in, first out rule. It is like stacking plates. You add to the top, and when you want the data, you lift the top one off. A queue does the opposite. It is first in, first out, like people waiting in line, where whoever arrived first leaves first.
Another workhorse is the hash, also called a map or a dictionary. It works like an array, except instead of numbered positions, you make up your own labels that point to each entry. A hash pairs each label with a value, useful when you want to look something up by name rather than by number.
When a straight line is not efficient, programmers branch out. Trees arrange points in layers so you can often move through them faster. Graphs go further, linking points in almost any pattern you need, where each point holds data and each link shows how two points relate.
Pick the shape that matches how you will put things in and take them out, and the computer has less searching to do.
Questions people ask
Why do array indexes start at zero?
It is a holdover from how memory addresses work. The index is really an offset from the start, so the first item is zero steps away, the second is one step away, and so on. Most major languages kept the convention.
When would a programmer use a stack versus a queue?
Use a stack when the most recent thing matters most, like undo in a text editor or backtracking in a web browser. Use a queue when fairness matters, like print jobs, customer support tickets, or messages waiting to be processed in order.
What does a key look like in a hash map?
A key is usually a name you choose, like a username, product code, or web address, paired with a value like a password, price, or page. The computer converts the key into a location in memory, so you can find the value without scanning the whole list.
Why can a tree be faster than a list?
A list must often be checked one item at a time from the start. A tree splits data into branches, so each choice eliminates a large group of items at once. That is why trees are common for searching, sorting, and storing things like file systems.