When a program is slow, the math usually isn't the problem. The time goes to lookups, digging through data that was stored with no thought for how it would be found. A data structure is really just a storage format, a way of organizing data so you can store it, find it, and update it quickly, and every structure gives something up to make the operations you care about fast. Match the structure to the operation and a search finishes in milliseconds, but get it wrong and the same search takes minutes.
The order matters, because every structure on this page exists to fix something the one before it couldn't do. Start at the top and work down, and each structure arrives right as the one before it breaks.
Arrays give you instant access by index, but inserting at the front means shifting everything over. Linked lists fix the insertion and give up the indexing to do it. Neither one can find a value without scanning, so hashmaps close that gap, and queues put these pieces to work whenever order of arrival matters.
Reading element 50,000 takes exactly as long as reading element 0, because position is computed, not searched.
Insert at the front without shifting a single element. The catch is that reaching anything means walking the chain.
Pull one value out of a million in a single step. The key itself tells you where to look.
How printers and web servers decide what to handle next. Whatever has waited longest goes first.
Everything above stores data in a line, and lines break down once data starts to nest or interconnect. Trees handle the nesting, heaps reshape a tree so the most urgent item is always on top, and graphs drop the parent-child rules entirely so anything can connect to anything. Matrices take arrays into two dimensions for data that lives on a grid.
Folders inside folders, replies under replies. When data nests, a flat list stops working and a tree takes over.
Almost nothing in a heap is sorted, yet the smallest item is always on top. The sloppiness is what makes it fast.
Road maps and social networks are the same structure underneath: things, and the connections between them.
An image, a maze, a chessboard. Anything laid out in rows and columns is already a matrix.
Every structure in this tier exists because a general one hits a wall on a specific question. Hashmaps can't find keys by prefix, so tries store words letter by letter and prefixes come free. Rechecking connectivity after every merge would mean traversing a graph over and over, which is the work union-find skips. And segment trees answer range questions a plain array would have to rescan from scratch each time.
Find every word starting with "ca" without scanning the whole dictionary. This is the tree autocomplete is built on.
It answers one question fast: after a million merges, are these two items in the same group?
Sum any slice of an array in about 20 steps, even while the values underneath keep changing.