Let’s talk about data structures that have close analogies to things you already do or know! This post will not be educational or entertaining, I promise. Enjoy!

Linked Lists

What is it?

A linked list is a way of storing related information consecutively, such that you can only navigate forwards.

Where do I already use it?

Most people store the alphabet in their heads this way! You can easily recite the alphabet forwards (it’s even got a catchy tune), but few people can fluently recite the alphabet backwards. That’s exactly what a linked list is like: going forward is easy, going backwards is hard.

Variations

If you can cite the alphabet backwards, you probably remember it analogously to what we call a doubly-linked list. It’s easy to go forwards and backwards (quick, what letter comes before v?) but it’s much more difficult to tell me what the nth letter is without counting (quick, what is the 17th letter?)

There’s a fairly uncommon but cool data structure called a “skip list,” too. This is basically a linked list, but where you don’t always want to navigate through every element to move forward because it’s a lot of elements. So you have your linked list, but then you also have a linked list that skips bunches of the list. The only example that’s coming to mind for me here is learning to speedrun a video game: You have a linked list of what you’d call the “route,” e.g. the order in which you go from place to place doing stuff. Then, at each place you go, there’s a bunch of smaller steps to do said stuff. So here you have the base linked list which is very detailed and tedious (e.g. walk 3 squares left, slash your sword then move down, etc etc) but you have a list on top of that that’s much coarser, and you can sort of go up and down between the two. So you’d think of it like: go to dungeon 1 (skip list), collect item 2 (skip list), (now drop down to the more detailed linked list) then move down two squares before wiggling away from some enemy. If this explanation makes no sense, don’t worry! I told you this wouldn’t be educational or entertaining, didn’t I?

Array

What is it?

An array is a lot like a linked list in these abstract, analogy-driven terms: it’s easy to navigate forward. It’s also easy to navigate backwards (like a doubly-linked list). However, it’s also very easy to access the nth element.

Where do I already use it?

Probably in how you think of months! You can tell me the months in order, and you could go backwards (it might be a bit stilted but you wouldn’t have any real trouble), but you can also probably tell me offhand exactly what the 5th month is.

You probably also think of days of the week this way, with some possible complications (e.g. is the first day of the week sunday or monday?). Although that’s hard to really say; 7 elements is tiny.

Map/Dictionary/Hash

These are all terms that usually refer to the same thing. Sometimes they hint at underlying implementations, which are far too educational for this blog.

What is it?

It’s a lot like what it sounds like: a mapping from something to something else. A mapping allows very fast access to any value based on its key. It’s not very good at going backwards, though!

Where do I already use it?

Probably something similar is happening all over your brain! But I can’t convince myself any of that is sufficiently map-like, because cognition is basically a black box.

Some more concrete examples: if I ask you to tell me what the word “alopecoid” means, you can go look it up in a dictionary easily*. But if I ask you to tell me a word that means “like a fox,” that’s a lot harder! Maybe you come up with “vulpine,” and I say, oh, no, that’s not the one I was thinking of, can you give me another? There’s no way get to a word based on its definition besides reading the whole dictionary, so you’re out of luck.

Tree

What is it?

A tree is a way of storing hierarchical data; that is, there is some “root” to the tree that has some number of “children,” each of which can have its own children (or not), etc. It’s useful for lots of stuff: it can make various searching procedures faster, it’s (generally) quite fast for inserting new values while maintaining sortedness, it’s the only sensible way of representing certain kinds of data at all.

Where do I already use it?

Company hierarchies work like this! There’s some big boss CEO at the top, who has some number of direct reports, and they have direct reports, etc. Presumably you know at least a substantial portion of the tree that includes you: you should know your boss, and probably their boss, and on up. You should also know all your direct reports, should you have any. But who cares about the hierarchy in departments you’re not in? I sure don’t!

Another example is family trees. Given a sufficiently correct family tree, you can go up and down and left and right to define relationships! For example, instead of your “boss” being above you, it would be your parents. Your children are your… well, children (one of those references is to human children, of course; either will do). If you go up a level and over a level, you get an aunt or an uncle**; if you go up a level, right a level, up another level (but not to the same place you’d get to going up two from the start!) and then down some more, you’ll end up with a 9th step-cousin π times removed (I think).

Graph

What is it?

A graph is a lot like a tree, except the connections between elements don’t have to go straight up and down***. They can go anywhere! Anything can be connected to anything else!!

Where do I already use it?

This is how Facebook works! I’m friends with a bunch of people, and they’re friends with a bunch of people, and some of those people are friends with me, etc, etc. Just lots and lots of people and lots of connections between them.

For an example that might make it more clear why graphs are interesting, consider playing the “Six degrees of separation” game, where you try to figure out how you’re connected to <cool celebrity X>. You start at yourself, and then you figure out the next connection: maybe your mom knew someone who grew up in X’s hometown. Then from there, you find out that this person knew X’s childhood barber. Now you’ve gotten there in just four jumps: you -> your mom -> person from X’s hometown -> X’s childhood barber -> X! This is a useful (if somewhat silly) way to use a graph.

Variations

Some graphs are what we call “Directed Acyclic Graphs,” or DAGs. These are an important subset of all graphs, with some restrictions on the connections between elements: the connections have a direction (such as parent-child or boss-employee) and there are no cycles (that is, if we have people A, B, and C, and we have that A is B’s boss, and B is C’s boss, we know for sure that C can’t be A’s boss, because that would form the cycle A->B->C->A).

Do you play video games (or maybe pen and paper RPGs)? If so, the “skill tree” you may have encountered in that setting are named pretty appropriately! There’s a “base skill” (or more than one, in which case you can think of the true root of the tree being a skill you have from the beginning), and after you’ve obtained that maybe you get a couple options for new skills. But sometimes you need more than one prerequisite — these skill “trees” should really be called skill DAGs! In this example, the direction is a “prerequisite” relationship, and there can’t be any cycles. If there were a cycle in a skill DAG, all the skills in that cycle would be unlearnable, since they all depend on each other (directly or indirectly).

Maybe you went to college? College degree requirements can be thought of as a DAG. Taking topology requires completing calc 3 and also algebra, which don’t depend on each other!

Lots of things are graphs. You can think of roads as connections on a graph, and intersections as the elements. Graphs show up everywhere! Some graphs can be directed and cyclic (think of a city neighbourhood with a lot of one way streets). Some graphs can be undirected and acyclic (I presume, I can’t actually think of a real-life example at the moment).

Bloom Filter

What is it?

A way to check whether we’ve already seen a certain element, without using much storage space (memory) to keep track. But there’s a twist… sometimes it lies! It might tell us we’ve seen something that we have not (but never the opposite).

Where do I already use it?

Hahahahaha, just kidding, you don’t.

---

* “Easily” is a substantial overstatement here! For years it wasn’t defined in any online dictionary I could find, and missing from many text ones. Even now, check out the Merriam Webster page for it, namely:

Wait, there’s more! This word doesn’t usually appear in our free dictionary, but we’ve shared just a bit of the information that appears in our premium Unabridged Dictionary. There’s more definition detail there.

** Is there a gender-neutral term for “sibling of parent?”

*** I sort of pretended that “right” and “left” are givens in trees, since they’re often represented directly in family trees. In general, that’s not the case, and navigating to a sibling is a process of going up to the shared parent and then back down to the sibling; they generally aren’t stored, in a computer, with a direct sibling connection. This does differentiate them from graphs importantly.