ENES

Data structure

A way of organizing data in memory so the operations you need are fast.

Four ways to organize the same data: an array of numbered boxes, a stack of plates, a queue of people and a tree of branches

A data structure is a particular way of arranging data inside a program so it can be used efficiently. The same list of customers can be kept as a simple numbered row, sorted, grouped by city or linked in a chain, and each arrangement makes some operations fast and others slow. Choosing the right one is half of writing a good algorithm.

A few classics show up everywhere. An array is a row of numbered slots: jumping to slot 500 is instant, but inserting in the middle means shifting everything after it. A hash table (called a dictionary or map in many languages) finds a value by its key almost instantly, like looking up a phone number by name. A stack works like a pile of plates, last in first out, and is how programs remember which function called which. A queue is first in first out, like a line at the bank, and is used for jobs waiting their turn. Trees and graphs connect items to each other, for folders inside folders, database indexes or a map of roads.

You rarely build these from scratch: every modern language ships with good versions of them. What matters is knowing which to pick. Searching for a name in an unsorted list of a million entries means checking them one by one; putting the same names in a hash table makes each lookup take about the same time no matter how big it grows.

Keep in mind

Go deeper

Related terms

More in Software