Data structures, at working level

What is a data structure, and why does the choice matter?

A data structure is the shape you keep several things in together. So far that sounds simple, and its simplicity is exactly why its importance goes unnoticed: most beginners assume that choosing between these shapes is a matter of taste, because any of them can hold the same data.

Any of them really can. A hundred names can go in a list, in a dictionary, or in a set. The difference is somewhere else: each shape answers one question cheaply and every other question expensively.

So here is the rule to take away from this lesson. When deciding what shape to keep data in, do not look at the data; look at the question you are going to ask of it later. "Which is the third member" is one question, "what is the value of this key" is another, and "is this thing in here at all" is a third. Three questions, three shapes.

And so that you expect the right thing: the wrong choice usually does not break the program. The program works, your code simply has to do a lot of work to ask a simple question, and that extra work shows up when the data grows or when something is added to it. The last section of this lesson is a real example of exactly that.

The list: when order is itself information

A list is several things one after another, with their order preserved. That preserved order is the only thing separating a list from the rest, and it matters more than it looks.

prices = [12000, 8000, 15000]

prices.append(9000)
print(prices[0])
print(len(prices))

Every member has a number called an index, and the numbers start at zero rather than one. So prices[0] is the first price. Starting at zero has a historical reason and is the same in nearly every modern language, and it is also why it is the source of the off-by-one error you met in the conditions and loops lesson.

A list is right when the order carries meaning: the steps of a task, search results in rank order, the messages of a conversation. In all of those, swapping two members changes the meaning, and that is the signal that a list is the correct choice.

And one property that looks like an advantage at first and becomes a cost later: a member's index is not fixed. Remove the first member and every later member moves up a place and takes a new index. Which is to say "member number three" tells you nothing about that member; it only says where it stands in the list right now. If you have stored that number somewhere to use later, you have just built a bug that has not happened yet.

The dictionary: when a key replaces a number

A dictionary is pairs of a key and a value. Instead of finding something by its number, you find it by its name. Different languages give it different names, but the idea is the same.

user = {"name": "sara", "city": "shiraz"}

print(user["city"])
user["city"] = "tabriz"

Here is the important difference that usually gets skipped: when you write user["city"], the program does not search through the dictionary. It goes straight to the right place. Had you kept the same data in a list of pairs, finding the city would mean reading the whole list from the start until you reached the pair whose key is the city.

On three members that difference is invisible. On three thousand members, and especially when that search sits inside a loop, it is exactly what makes a page slow. Most of the slow code we have seen on client sites is of precisely this kind: a linear search inside a loop, where one key would have been enough.

A second property that matters just as much: a key does not change. Unlike a list index, which shifts as things are added and removed, the key stays the key. If you need to come back to one particular member later, this is the only property you actually need, and the last section of this lesson shows how seriously that plays out in practice.

The set: when all you want to know is whether it is there

A set is several unique things with no defined order. It does two jobs very well and every other job not at all: it removes duplicates, and it answers quickly whether something is inside it.

tags = {"seo", "speed", "seo"}

print(len(tags))
print("seo" in tags)

The third line prints two, not three, because the duplicate was dropped at the moment it went in. That behaviour is what makes a set useful and it is also what silently shrinks your data if you are not paying attention; if the repetitions mean something to you, a set is the wrong shape.

Now a real world example, from this site's own code. PHP has no data type called a set at all. So when we need one, we build it out of an array whose keys are the things we want to track and whose values do not matter in the slightest:

$used = array();

// ... inside a loop that builds an id for each heading:
while ( isset( $used[ $id ] ) ) {
    $id = $base . '-' . $n++;
}
$used[ $id ] = true;

Look at that true: it is never read anywhere in the program. What is really being stored is the key itself, meaning "this id has already been used". That is precisely the definition of a set, built out of the tool that happened to be available. And the reason a list is no good here is the reason from the previous section: isset goes straight to the key, while hunting for an id in a list of ids means reading the whole list, inside a loop that runs once per heading.

Which one goes where?

The three shapes above, plus one whose name has not come up yet, the tuple, cover almost everything you need in a first year. A tuple is a list with one difference: it cannot be changed after it is built. It suits things that inherently should not change, such as a pair of latitude and longitude.

The last column is the most important column of this table and the rest only explain it. If you are unsure which to choose, write the sentence you are going to ask of this data later and see which row it lands in.

And a position that does not sit well with the usual tutorials: in everyday web work the dictionary comes up more often than the list and is used less often than it should be. Beginners pour everything into lists because the list is the first thing they learned, and then loop through them to find one member. Change that single habit and a good share of the slow code you would write later never gets written at all.

A real decision: why the release ledger for these lessons is not a list

The very learning section you are reading publishes its lessons one at a time on a schedule: three a day, taking turns across sixteen tracks. The order of those turns is not stored; it is recomputed from the lessons themselves each time.

And right there is a real problem. When a track that had been empty gets filled, its new lessons land in the middle of the queue and the position of every lesson after them moves up by one. Now suppose the ledger recording what has been published were a list of positions, or even just a number saying the first five are out. A lesson published yesterday would, after today's reshuffle, no longer be among the first five; it would fall off the list and its page would 404 for a visitor.

So the ledger is a dictionary. Its key is the lesson's own address and its value is the moment it first went out. On the day this lesson was checked it held five keys, the first of which was this:

'seo/how-search-engines-work' => 1788539040

Now, however much the queue changes, this key stays where it is, because the key was never a position in the queue; it was the lesson's own name. The whole story in one sentence: a list answers what is in position three, and a dictionary answers when this particular lesson went out. Only the second question still means anything once the queue is rebuilt.

This is what the first section of this lesson said, only this time on a real page: the wrong choice would not have broken the program. The program would have worked, and one morning a few published pages would simply have vanished without a sound.