What a data structure actually is

A way of arranging things, plus a promise about what that arrangement makes easy.

Imagine you own five hundred books and one long shelf. You have to put them on it somehow, and there is no arrangement that is simply correct. You could sort them alphabetically by author. You could group them by subject. You could arrange them by the colour of the spine, which looks wonderful. You could put them in the order you happened to buy them, which takes no effort at all.

Each of those choices is a bargain, and the bargain is always the same shape: some questions become easy to answer and others become hard.

• Sorted by author. Finding your copy of a book by Woolf takes a few seconds. Adding a new book by Austen means sliding hundreds of books along to make a gap.
• Grouped by colour. The shelf looks lovely and you can find the green one you half remember. Finding a specific title means scanning the whole shelf.
• In the order you bought them. Adding a book is free, because it goes on the end. Finding anything at all means starting at the left and looking at every spine.

Notice that no arrangement won. The one you should pick depends entirely on what you are going to do with the shelf. If you look things up constantly and buy a book once a month, sorting is clearly worth it. If you add books daily and rarely look anything up, sorting is a waste of your afternoons.

The same problem, inside a computer

A program has data: the things it is keeping track of. Names, prices, dates, messages, pixels, whatever the program is about. That data has to be arranged somehow inside the machine, and the same bargain applies. A data structure is a particular way of arranging data, together with a promise about which operations that arrangement makes cheap.

That framing is worth holding on to, because it stops you asking which structure is best. It is not a question with an answer. A hash table, which you will meet later, can find a record by name almost instantly but has no idea what order anything is in. A sorted list knows the order exactly but is slow to add to. Neither is better. They answer different questions, exactly like the shelves.