What is a data structure? Arrays, lists, trees and hash tables

A data structure is a way of arranging data in a computer's memory so that the things you need to do with it, such as finding an item, adding one or keeping them in order, are fast. The same million names can sit in a plain list, a sorted list, a tree or a hash table; each arrangement makes some jobs quick and others slow, and choosing well can make a program thousands of times faster.

In short

• A data structure is an arrangement of data plus the rules for working with it: how to find, add and remove items.
• No structure is best at everything; each trades speed at one job for slowness at another, or for extra memory.
• Picking one means asking which operations a program does most often, then choosing the structure that makes those cheap.

What does a data structure actually do?

It decides where each piece of data goes, so that you know where to look later. The US National Institute of Standards and Technology's Dictionary of Algorithms and Data Structures defines one as "an organization of information, usually in memory, for better algorithm efficiency". The key word is efficiency. Data structures and algorithms come as a pair: the arrangement of the data decides which methods are possible, and how many steps each one takes.

A kitchen is a fair picture. Plates stacked in a cupboard are easy to take from the top and awkward to take from the bottom. Spices in alphabetical order are quick to find and slow to add, because a new jar means shifting the others along. Spices thrown in a drawer are quick to add and slow to find. None of these is wrong; each suits a different habit. Computers face the same trade-offs, with millions of items and no patience.

What are the main data structures?

Most programs are built from a handful. The column for finding an item uses Big O notation, which says how the work grows as the number of items, n, grows: O(1) means the same work however many items there are, O(log n) grows very slowly, and O(n) means checking up to every item.

Structure	Everyday picture	Find an item	Add an item	Good for
Array	A row of numbered lockers	O(1) by position; O(n) by value, or O(log n) if sorted	Fast at the end, slow in the middle	Data read in order or by position
Linked list	A treasure hunt, each clue pointing to the next	O(n)	O(1) once you're at the spot	Frequent inserts and removals
Stack	A stack of plates: last in, first out	Only the top	O(1)	Undo, tracking function calls
Queue	A line at a shop: first in, first out	Only the front	O(1)	Jobs waiting their turn
Hash table	A coat check: the ticket number says which hook	O(1) on average	O(1) on average	Looking things up by name or key
Balanced tree	A game of higher-or-lower	O(log n)	O(log n)	Data kept in sorted order
Graph	A subway map: stops joined by lines	Depends on the question	O(1) per link	Maps, networks, who-knows-whom

Two of these deserve a closer look. A hash table runs each key, such as a name, through a hash function that turns it into a number, and uses that number to pick a slot. To find the name later, it computes the same number and goes straight to the slot, instead of searching. A tree splits data at each step: everything smaller to the left, everything larger to the right. Trees are built from smaller trees of the same shape, which is why code that walks them is usually written with recursion.

How much difference does the choice make?

Take a phone with 1,000,000 contacts, and look up one name in three structures.

1. An unsorted list. The only method is to check names one by one. On average the right one is halfway in, so about 500,000 comparisons; if it's missing, 1,000,000.
2. A sorted array. Now binary search works: look at the middle name, see whether the one you want comes before or after it, throw away the other half, and repeat. Each step halves the remaining names, so 1,000,000 becomes 500,000, then 250,000, and so on. Since 2 multiplied by itself 20 times is 1,048,576, about 20 comparisons always settle it.
3. A hash table. Compute the name's hash, go to that slot, and check the one or two names stored there. About 1 or 2 comparisons, and still about 1 or 2 with 100 million contacts.

The gap between 500,000 steps and 20 steps comes entirely from how the data is arranged, not from a faster computer. Measured in Python on an Apple M3 Max laptop in November 2026, finding the middle name of a million by scanning the list took about 3 milliseconds; binary search on the sorted list took about 0.14 microseconds; the hash table, Python's built-in dictionary, took under 0.03 microseconds. That is roughly 100,000 times faster than the scan, for one line of code changed. Do a million lookups and the scan takes most of an hour; the dictionary, a fraction of a second.

The numbers depend on the machine; the ratios barely do. Python's own wiki lists the expected costs of these operations on its built-in types, and they match the counts above: checking whether an item is in a list is O(n), in a dictionary O(1) on average.

Then why not use a hash table for everything?

Because it gives up things other structures keep. A hash table scatters keys on purpose, so it has no order: it can't list contacts alphabetically, or answer "every name between Smith and Smyth", without sorting everything first. It uses extra memory for empty slots. And its speed is an average: if many keys land in the same slot, lookups slow down, which careful designs make rare.

A sorted tree answers the range question in O(log n) steps and keeps everything in order, at the cost of being somewhat slower for single lookups. This is why real systems often keep the same data in two structures at once. A database stores rows in a table and adds an index, usually a tree, on the columns people search by, paying with extra storage and slower writes to make reads fast. Search engines do the same on a vast scale: the index described in how search engines work is, at heart, a giant lookup structure from each word to the pages that contain it.

What do people get wrong about data structures?

The common mix-up is between what a structure promises and how it is built. A stack is a promise, last in first out, and it can be built on top of an array or a linked list. Computer scientists call the promise an abstract data type and the way it's built an implementation. Python's "list" is, underneath, an array that grows as needed, not a linked list, despite the name; its "dictionary" is a hash table.

The other mistake is to think this matters only to specialists. Every app makes these choices, usually through the ready-made structures its language provides, as the Python tutorial on data structures shows for lists, sets and dictionaries. A program that feels slow with 10,000 items and freezes with a million is very often using a list where it needed a dictionary. Even a blockchain is a data structure first: a list of blocks in which each one holds a fingerprint of the one before.

Check yourself

• Without looking back, explain why binary search needs only about 20 steps for a million sorted names.
• What does a hash table give up in exchange for its fast lookups?
• What is the difference between a stack as a promise and a stack as it is built?

Sources

• Data structure — Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology
• Hash table — Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology
• Time complexity of Python's built-in types — Python Wiki
• Data structures, in the Python tutorial — Python Software Foundation
• Data structure — Wikipedia