What Is a Data Structure?

Where you put things changes everything

Imagine two kitchens. In the first, every spice sits in a labeled rack in alphabetical order. In the second, all the spices are dumped in one big drawer. Both *contain* the same spices — but reaching for cumin takes a glance in one kitchen and a frustrating dig in the other. The spices are your data. The rack-versus-drawer choice is your [[data-structure|data structure]]: the way you arrange information so you can work with it.

This is the partner idea to the last guide. An algorithm is the steps; a data structure is the *shape the data sits in* while those steps run. And the shape matters enormously: a phone book sorted by name lets you find a person in seconds, but if you only have their *number* and want the name, that same sorted-by-name book is almost useless. There is no single best structure — only the right one for the questions you'll ask most.

The promise vs. the machinery (ADT vs. implementation)

There's a useful split hiding here. On one side is the *promise*: "you can add an item, remove an item, and ask how many there are." That list of operations and what they mean — with no word about how it's built inside — is called an [[abstract-data-type|abstract data type]] (ADT). On the other side is the *machinery*: the actual nuts and bolts in memory that deliver the promise. That's the implementation.

Think of a vending machine. The promise is simple: press a code, money in, snack out. *How* it does that — spirals, sensors, a tiny motor — is hidden behind the glass, and you don't care, as long as the snack arrives. An ADT is the front of the machine; the implementation is everything behind the glass. The same promise (a "list of things") can be delivered by very different machinery (an array, or a chain of linked boxes), each with its own costs.

Three you'll meet first: array, list, map

You don't need them all today — just a preview, so the names feel familiar later. The [[dsa-array|array]] is a row of slots numbered 0, 1, 2, …; jump straight to slot 5 and the value is *right there*, instantly. The list is a chain of items, easy to grow and rearrange but you walk it one link at a time. The map (also called a dictionary) stores *key → value* pairs, like a word linked to its definition, so you look things up by name instead of by position.

array:   [ A | B | C | D | E ]      jump to index 3 -> D  (instant)
           0   1   2   3   4

list:    A -> B -> C -> D -> E      walk from A to reach D (4 steps)

map:     "cat" -> 9                 look up by the key "cat", not a number
         "dog" -> 4
         "fox" -> 7

Same five values, three shapes. The array reaches any slot at once; the list must be walked; the map finds things by name. Different shapes make different jobs easy.

Each of these gets its own guide later. For now, the one thing to carry forward is the lesson, not the details: the structure you choose decides which operations are cheap and which are costly. Choosing well is half of writing fast programs — and to *measure* cheap versus costly, we need the language of the next guide.