= Data structure
{wiki}
A <data structure> organizes stored information together with operations for accessing and changing it. Choosing a <data structure> means choosing which questions should be cheap to answer: an <array> supports access by numbered position, a <hash table> supports lookup by key, and a <priority queue> supports selecting an item by priority. The operations and their <time complexity> matter as much as the stored values.
Suppose three requests arrive as $(5,\mathrm{Ada}),(2,\mathrm{Bo}),(4,\mathrm{Cy})$, where the number is a priority and smaller numbers are more urgent. A <FIFO queue> removes Ada first because she arrived first. A minimum-oriented <priority queue> removes Bo first because $2$ is the least priority. An <array> can store the same three records in arrival order, but finding the least priority by scanning this representation takes three key inspections. A <binary heap> organizes these records so the least priority is immediately available. The information is the same; the representation changes the work needed to use it.
This is a useful design principle: preserve just enough organization for the operations the application needs. Maintaining a <sorted array> gives the whole order, but moving entries to insert a new key can be expensive. A <binary heap> keeps a weaker <heap order> that supports fast repeated selection without maintaining a <sorted array>. A good <data structure> makes an <algorithm>'s next step easy.
Back to article page
