Why data structures and algorithms matter

← Back to the section

Almost every program stores something and does something with it: items in a cart, messages in a chat, points on a map. One question comes up every single time — how to lay those data out so that working with them is convenient and fast. The answer decides whether looking up a record is instant or the program stalls for seconds, whether everything fits in memory, and how easy it is to add one more element. Data structures and algorithms are the answer to that question. This section is a route through them from scratch, from the array to the graph.

What a data structure and an algorithm are

A data structure is a way of organising data in memory (or on disk). An array, a linked list, a stack, a tree, a hash table — all of them are different ways to lay out the same data. Each way is good at something: one searches fast, another inserts fast, a third saves memory.

An algorithm is a sequence of steps that solves a task over the data. For most structures the basic tasks are the same:

• insert a new element;
• find the element you need;
• delete an element;
• walk all elements one by one;
• sort the elements into order.

The structure and the algorithm are tied together: the way you store data decides which operations are cheap and which are expensive. That is why they are studied side by side.

Three roles of data structures

Where is any of this useful? Roughly three large areas.

Storing real-world data. Data about people, goods, orders, transactions. The classic analogy is a card index: every card describes one entity (a person, a product), and the whole stack is the database. As soon as there are many cards, the familiar questions appear: how to find the right one quickly, how to add a new one, how to sort them alphabetically. Real databases are more complex than a card index, but the idea is the same.

A programmer's toolbox. Not every structure is visible to the user. Many exist for the program itself as a working tool: a stack to parse an expression or undo an action; a queue to process tasks in order; a priority queue to always take out the most urgent one. These are the helper structures under the hood.

Modelling. Some structures mirror the real world directly. A graph models routes between cities, connections in a social network, or dependencies between tasks. A queue models customers in a bank or cars at a gate. Here the structure is a map of the task itself.

The basic vocabulary

A few words that come up constantly; it is easier to agree on them right away.

• A record is a logical block describing one entity as a whole: one person, one product, one order. In a card index it is a single card; in code it is usually an object of a class.
• A field is a separate part of a record: the name, the address, the phone number. In an object it is one of its variables.
• A key is the field you search by. Say you look an employee up by surname — the surname is the key here. The same data may have several keys: today you search by surname, tomorrow by phone number.

This vocabulary lets you talk about operations uniformly: "find a record by key", "insert a record", "delete by key" — no matter which structure sits underneath.

An overview: which structure for what

The main idea of the whole section: there is no ideal structure — each one has its strong and its weak side. The choice is always a trade-off. Here is the map from a bird's-eye view; some terms may be unfamiliar right now — every one of them gets its own article.

There is no need to memorise the table — it becomes obvious as you read on.

How "fast" and "slow" are measured

The words "fast" and "slow" are about to become precise. The speed of an algorithm is measured not in seconds (those depend on the hardware) but in how the number of operations grows with the amount of data — this is called Big O notation. A linear scan through an array of a million elements takes up to a million steps; a binary search in an ordered array takes about twenty. Big O notation is exactly what describes that difference; we go through it in detail in the article on arrays and binary search.

How it is done in Java

The good news: almost everything in the table above is already written for you in Java — these structures live in the standard collections library (the Java Collections Framework). Writing your own linked list or your own tree in working code is rare. But choosing is a daily job, and the price of a mistake is exactly the same: pick the wrong structure and you get slow code where it could have been fast. That is why every article in this section has a block about the ready-made implementation: which class, what is inside it, and where it lets you down. Here is the whole map:

The difference shows up in ten lines: put the same records into an ArrayList and into a HashMap and look the last one up.

live example

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Lookup {
    public static void main(String[] args) {
        System.out.println(find(10));
        System.out.println(find(1000));
    }

    static String find(int size) {
        List<String> list = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 1; i <= size; i++) {
            list.add("key-" + i);
            map.put("key-" + i, i);
        }
        String target = "key-" + size;
        int compared = 0;
        for (String key : list) {
            compared++;
            if (key.equals(target)) break;
        }
        return size + " records: scanning the list took " + compared
                + " comparisons, HashMap returned " + map.get(target) + " right away";
    }
}

A hundred times more records — the list takes a hundred times longer, while the hash table does not care. That is O(N) against O(1).

The trap common to all of them. In Java the type of a variable and the actual structure are different things. Behind a declaration List<String> items there may be either an ArrayList or a LinkedList, and items.get(i) costs O(1) in one and O(N) in the other. The type says what you may do with the data; how much it costs is known only to the concrete class. So when reading someone else's code, look at the line with new, not at the declaration.

In short

• A data structure is a way of organising data; an algorithm is the steps of the operations over them (insert, search, delete, walk, sort).
• Structures serve three purposes: storing real-world data, acting as a programmer's tool, modelling tasks from the world.
• The basic vocabulary — record, field, key — lets you talk about operations uniformly.
• There is no ideal structure: each is fast at one thing and slow at another, and the choice is always a trade-off for the task at hand.
• "Fast" is measured with Big O notation — by how the number of operations grows with the amount of data.

What to read next

• Maths for Big O notation — powers and logarithms, in case school maths has faded.
• Arrays, binary search and Big O notation — the first structure of the section and the first measure of speed.
• Simple sorting: bubble, selection, insertion — three teaching algorithms that show where O(N²) comes from.
• Choosing a data structure — the summary of the section: the same table, but now with the reasons behind it.