What is a Data Structure?

What a data structure is, and why the choice matters

A data structure is a way of arranging data in your computer’s memory. The arrangement decides which operations are fast and which are slow. Memory itself is one long strip of numbered cells. A data structure is a plan for laying your data across those cells so a particular task becomes cheap.

The same data can live in many shapes. A list of customer names can sit in an array, a linked list, a hash table, or a tree. Each shape answers a different question quickly. Picking the wrong shape can turn a fast program into a slow one, even when the code looks correct.

You measure these trade-offs with Big O notation. Big O describes how the time for an operation grows as the data grows. O(1) means the time stays constant no matter how much data you have. O(n) means the time grows in step with the number of items, n. O(log n) sits between them and grows very slowly. Read What is Big O Notation? for the full picture.

A real-world analogy

Think of three ways to store coats.

An array is like a wall of numbered lockers. If you know locker 7 holds your coat, you walk straight to it. You do not check lockers 1 through 6 first. Access by number is instant.

A linked list is like a treasure hunt. You start at the first clue, and each clue points to the next. To reach the tenth item, you follow nine clues in order. There is no shortcut to the middle. You only know where the next item lives once you read the current one.

A hash table is like a coat check. You hand over your coat and get a tag. Later you hand back the tag, and the attendant fetches your coat at once. The tag, your key, leads straight to the right hook without searching every coat in the room.

Arrays

An array stores items in a single block of memory, side by side. Each item has an index, a position number that starts at 0. Because the items are packed in order, the computer can jump to any index in one step. Indexed access is O(1), constant time.

Arrays shine when you know the position you want. They are weak when you need to insert or remove an item in the middle, because everything after that point has to shift across to make room or close a gap.

prices = [10, 25, 40, 55]   # an array of four numbers
print(prices[2])            # 40, found instantly by index

Linked lists

A linked list stores each item in a small package called a node. Every node holds a value and a pointer, the memory address of the next node. The nodes can sit anywhere in memory because each one knows where the next one lives.

To find an item, you walk the chain from the start until you reach it. Access or search is O(n), because in the worst case you visit every node. The pay-off comes at insertion and deletion. Once you are holding a node, you splice a new one in or unhook one by changing a couple of pointers. That step is O(1).

# a node points to the next node
node = {"value": 25, "next": some_other_node}

Use a linked list when you insert and delete often and rarely need to jump to a position by number.

Stacks and queues

A stack and a queue are linear structures with a strict rule about which item leaves next.

A stack is last in, first out, written LIFO. The last item you add is the first you remove, like a pile of plates. The two operations are push (add to the top) and pop (remove from the top). Both are O(1). Stacks track the “undo” history in an editor and the chain of function calls in a running program.

A queue is first in, first out, written FIFO. The first item you add is the first you remove, like a line at a shop. The operations are enqueue (add to the back) and dequeue (remove from the front). Both are O(1). Queues hold jobs waiting to run and tasks waiting for a worker.

Hash tables

A hash table is the structure behind fast lookup. It stores key and value pairs and finds any value by its key, not by a position. You meet it constantly: a dictionary in Python, a Map in JavaScript, and a HashMap in Java are all hash tables.

It works with a hash function, a small piece of code that turns a key into a number. That number points to a slot where the value lives. Because the function jumps straight to the slot, search, insert, and delete are O(1) on average. The “on average” matters. Sometimes two keys land in the same slot, a collision, and the table handles it. With many collisions the cost can degrade to O(n) in the worst case, but a good hash function keeps that rare.

Compare looking up a user by name in an array versus a hash table.

# Array: you scan every entry until you find the name. O(n).
users = [("ana", 30), ("ben", 41), ("cleo", 27)]
for name, age in users:
    if name == "cleo":
        print(age)          # 27, found after checking three entries

# Hash table: you jump straight to the key. O(1) on average.
users = {"ana": 30, "ben": 41, "cleo": 27}
print(users["cleo"])        # 27, found in one step

Reach for a hash table whenever you look things up by a name, an id, or any unique key.

Trees and binary search trees

A tree is a hierarchical structure. It starts at a single root node and branches downward, where each node has child nodes below it. Folders on your computer form a tree: one folder holds files and other folders, which hold more files, and so on.

A binary search tree, or BST, is a tree where each node has at most two children and keeps an ordering rule. Smaller values go left, larger values go right. That rule lets you search by halving the data at each step, like flipping to the middle of a sorted phone book and then a quarter, and so on.

When a BST stays balanced, meaning the branches are roughly even in depth, search, insert, and delete all run in O(log n). A red-black tree is one common kind of self-balancing BST. The warning sign is balance. If you insert already-sorted data into a plain BST, it can grow into a long thin chain, no better than a linked list, and degrade to O(n). Self-balancing trees exist to prevent exactly that.

A brief note on heaps and graphs

Two more structures show up often.

A heap is a tree that always keeps the smallest (or largest) value at the top. That makes it perfect for a priority queue, where you keep pulling out the most urgent item. Heaps power task schedulers and the core of several pathfinding algorithms.

A graph is a set of nodes connected by edges, with no required hierarchy. It models networks: friends on a social platform, roads between cities, links between web pages. Graphs are how you represent and search relationships rather than a strict sequence or tree.

How the right structure makes search and sorting fast

The structure you choose sets the ceiling on speed. Searching an unsorted array means checking each item, which is O(n). Put the same data in a hash table and a lookup drops to O(1) on average. Keep it in a balanced BST and a lookup is O(log n), while the data also stays sorted for free.

Sorting depends on structure too. A heap gives you heapsort, a clean O(n log n) method. Many fast algorithms work by first arranging data into a helpful structure, then reading it back. The lesson holds across the board: pick the structure that makes your most frequent operation cheap, and the rest of the program follows.

What’s next

• How Search Algorithms Work : see how linear and binary search use these structures to find data.
• How Sorting Algorithms Work : learn how ordering data unlocks faster search.
• What is a Database? : see how these structures persist data beyond a single program run.

Further reading

• Princeton Algorithms Cheatsheet : a concise reference table of structures and their operation costs.
• Introduction to Algorithms (CLRS) : the standard textbook covering every structure here in depth.
• What is an Algorithm? : the step-by-step recipes that run on top of these structures.
• What is Big O Notation? : how to read O(1), O(n), and O(log n) and compare speeds.
• How Search Algorithms Work : the methods that find a value inside these structures.
• How Sorting Algorithms Work : how to order data and why ordering speeds up search.
• What is a Database? : how structures like B-trees power durable, queryable storage.