Choosing Between Vectors and Linked Lists

The default tells you where the burden of proof sits. A vector is the choice you keep unless something specific pushes you away from it. Before you choose a list, you must name a concrete reason.

Programming

Interactive lab

Try it: Linked List

How a singly linked list stores values in separate nodes joined by next pointers, and how inserting or deleting only rewires pointers.

How it works

HEAD points at the first node; each node holds a value and a pointer to the next node; the last node points to NULL.
To insert, create a node, store its value, point it at its successor, then point its predecessor (or HEAD) at it.
To delete, walk to the node and make its predecessor skip over it.
Searching means following next pointers from HEAD until the value or NULL is reached.

Default run (9 steps): HEAD → 10 → 20 → 30 → NULL. 3 of 10 nodes. Choose an operation. Example: append 40. … Done: HEAD → 10 → 20 → 30 → 40 → NULL.

Educational simulation

Loading the simulation…

Predicting Which Version Runs Faster

Imagine two versions of the same program. One stores its data in a linked list and the other stores it in a vector. The code that reads, searches, and sorts that data can be written in nearly identical form for both. The question this article answers is which container you should choose when either one would technically work.

What do you think happens?

If the data set is small, which version would you expect to run faster: the linked list version or the vector version?

The linked list version
The vector version
They always run at the same speed

Reveal answer

Answer:

The vector version can be faster, even when the data set is small.

The source calls this result surprising. It seems to point the other way on paper, and the explanation depends on how the hardware handles the data (machine architecture). Your intuition about list and vector costs can mislead you, so performance claims should be checked rather than assumed.

The rest of this article works through why the default is sensible, where it comes from, and what would justify departing from it. The goal is not to memorize a slogan but to be able to trace the reasoning yourself on a new problem.

Starting From the Need, Not the Structure

The starting point is a need, not a structure. If your program needs a sequence of elements, both a vector and a list can hold that sequence. The decision is therefore about which container to pick when either would technically work, and not about whether a sequence is needed at all.

Definition

The default rule: when all you need is a sequence of elements, use a vector unless you have a reason not to. The source describes this as a starting presumption, not a ban on lists.

Key point

The default tells you where the burden of proof sits. A vector is the choice you keep unless something specific pushes you away from it. Before you choose a list, you must name a concrete reason.

Notice what this reasoning does not depend on. It does not rely on a feeling that vectors are simpler or that lists are fancy. It moves from the need, to the default, to the operations involved, and only then looks for an exception.

Tracing a Quiz Score Decision

Consider a small program that stores a list of quiz scores for a class. The program needs to keep the scores as a sequence, count how many scores are above a threshold, find a particular score, sort the scores, and search the sorted result. The decision can be walked through one step at a time.

Worked example

Choosing a container for the quiz scores

A class program must keep quiz scores as a sequence, count scores above a threshold, find a particular score, sort the scores, and search the sorted result. Should the scores be stored in a vector or a linked list?

1
Identify the need
The program needs a sequence of elements. Both a vector and a list can hold that sequence, so the question is which one to pick.
2
Apply the default
Start from the presumption that a vector is the choice, unless a specific reason pushes you away from it.
3
Check the operations
Counting scores above a threshold and finding a particular score are traversal operations, illustrated in the source with count() and find(). Sorting and searching the sorted result are illustrated with sort() and binary_search(). The source says a vector performs better for both families.
4
Look for an exception
Nothing in the stated needs names a reason to prefer a list. The vector remains the choice, and the operations listed are the ones the source associates with vectors.
5
Verify before trusting
If someone claims a list would be faster here, treat that as a performance claim to check rather than assume.

Result

Store the quiz scores in a vector. The default holds because the program's operations are the ones the source says favor a vector, and no concrete reason for a list has been named.

Slots Versus Linked Nodes

The source does not walk through hardware details in this passage, so the diagram below shows only the general structural difference that the comparison rests on. A vector holds its elements in consecutive slots, and each element is reached by stepping to the next slot. A linked list holds nodes, and each node points to the next one, so reaching an element means following links from node to node.

How the elements of a vector sit in consecutive slots, while the nodes of a linked list are connected by links rather than by position.

Read the diagram as a question of access. Moving through a vector means stepping to the next slot. Moving through a list means following a link from one node to the next. The sample scores are invented for illustration and are not from the source.

Operations That Favor a Vector

The source identifies two families of operations where a vector performs better than a list. Use the comparison below to see which structure each family favors.

The two operation families the source associates with vectors: traversal, and sorting with searching.

Why a Small Vector Can Win

The most surprising claim in this section is that a small vector can perform better than a small list. The source describes this as something that seems unexpected unless you understand machine architecture. A result that looks like it should go the other way on paper depends on how the hardware handles the data.

The practical takeaway does not wait on the hardware details. When someone says a list will be faster for a small data set, the right response is to measure rather than accept the claim, and to recall that the source reports the opposite result for small vectors.

When to Set the Default Aside

The default is set aside only when you can name a concrete reason to choose a list. The flowchart below shows the order of questions: start from the need, apply the default, look for a specific exception, and verify any performance claim before acting on it.

Start from a need for a sequence, hold to the vector default, and move to a list only when a concrete reason is named and verified.

The source gives no specific list-favoring operations in this passage, so a reason to choose a list must come from your own program's needs and must be checked against actual performance. The default does not forbid lists; it only places the burden of proof on them.

Mistakes in Choosing a Container

Common mistake
Choosing a linked list because it sounds more sophisticated
Why it fails
The source says the default is based on the need and the operations, not on a feeling that lists are fancy.
Do this instead
Start from the default vector and name a concrete reason before choosing a list.
Common mistake
Assuming a list must be faster for a small data set
What it looks like
A program with a few quiz scores assumes the list version is quicker without measuring.
Why it fails
The source reports that a small vector can outperform a small list, and that intuition about these costs can mislead you.
Do this instead
Verify performance claims rather than assuming them.
Common mistake
Treating the default as a ban on lists
Why it fails
The source describes the default as a starting presumption, not a ban on lists.
Do this instead
Keep the list option open, but require a specific justification first.

Applying the Default to a New Scenario

MEDIUM

A program must store a sequence of sensor readings, repeatedly count how many readings exceed a limit, and sort the readings before searching them. Using the default rule, which container do you choose, and what would have to be true for you to set the default aside?

Hints

Start by stating the need: is it a sequence of elements?
Match the operations (count, sort, search) against the two families the source names.
Think about what concrete, verifiable reason would be needed before choosing a list.

Your attempt (not saved)

Key Takeaways

When you need only a sequence of elements, the default is a vector unless you have a reason not to use one.
The source associates vectors with traversal (find, count) and with sorting and searching (sort, binary_search).
A small vector can outperform a small list, a result that depends on machine architecture; check performance claims rather than assuming them.
To set the default aside, name a concrete reason for a list and verify it.

Related concepts

Vectors and Dynamic Arrays

More concepts starting with C