Collections Internals

By the end of this lesson you will be able to explain what actually happens inside a List, Set, and Map when you call their methods — not just what the methods do, but why some are fast and some are slow, how hashing turns a key into a memory slot, why iteration order differs between collection types, and how lazy Iterable chains like .where().map() really run.

Full API reference — this lesson is about how collections work inside (growth, hashing, laziness, equality). Every single method and constructor has its own lesson with a runnable example, its cost and its exceptions:

D22 · Mutable vs Immutable — const, final, unmodifiable views and copies, shallow vs deep copy
D25 · Iterable methods — where, map, expand, take, fold, reduce, first/last/single, generators…
D26 · List methods — add, insert, remove*, sort, sublist, setRange, fillRange, shuffle…
D27 · Set & Map methods — union/intersection, putIfAbsent, update, entries, HashMap/LinkedHashMap/SplayTreeMap…
D28 · Queue & LinkedList — ListQueue ring buffer, DoubleLinkedQueue, LinkedList, collection views

1. List internals: backing array, growth, shifting

Picture a List as a row of numbered lockers bolted together in one straight line — a contiguous block of memory. Because the lockers are numbered and sit right next to each other, jumping straight to locker #7 takes exactly one step, no matter how many lockers there are. But if you want to shove a NEW locker in at the very front, every single locker after it has to shuffle down one position first. That shuffling is the whole story behind why some List operations are fast and some are slow.

Dart's List comes in two flavors:

Fixed-length — created with List.filled(n, value) (its growable parameter defaults to false!) or List.generate(n, (i) => ..., growable: false). (The old unnamed List<int>(n) constructor was removed years ago — it no longer compiles in Dart 3.) Its backing array is allocated once, at exactly that size, forever. Calling .add() on it throws an UnsupportedError — there is nowhere for the new element to go.
Growable — created with a list literal [1, 2, 3] or <int>[]. Its backing array can be swapped out for a bigger one behind the scenes as you add more elements.

The same rules as runnable Dart (the // => lines are the exact output):

Now the doubling rule as code: capacity is our model of the backing array (Dart does not expose the real one), copies counts the elements moved by growth.

The exact growth strategy (how much bigger the new backing array is, and exactly when it grows) is an implementation detail of the Dart SDK, not something the language specification promises you — it could change between SDK versions. What is a reliable, teachable idea (shared by dynamic arrays in nearly every language, including Dart's) is: the backing array keeps some spare room, copies everything into a bigger array only occasionally, and the result is that add() is amortized O(1) — average the cost of many adds together, and each one is roughly constant time, even though a few individual calls do an O(n) copy.

The maths behind "amortized": the copies are 2 + 4 + 8 + … < 2n in total, i.e. fewer than 2 extra copies per add. In code:

Reading a slot is one address computation, base + i × slotSize, which is why list[i] is O(1) at any length:

Now the operations that are slow no matter what: inserting or removing anywhere except the end.

The shifting, written out as code that counts the element moves (a model of what the runtime does inside insert and removeAt):

A common beginner mistake: calling list.insert(0, x) or list.removeAt(0) in a loop and being surprised the program is slow on a big list. Each call is O(n) because of the shifting — do that n times and you've built an accidental O(n²) algorithm. If you need to repeatedly add/remove from the FRONT, reach for a Queue (covered in section 4) instead — it does the same job in O(1). Use ListQueue (or a head index), never list.removeAt(0), as a queue:

Index access list[i] is O(1) — direct jump, no shifting. add()/removeLast() at the END are O(1) (amortized for add). insert()/removeAt() anywhere else are O(n) because every following element must shift.

Input size → what is feasible: a few thousand front-inserts on a list of n ≤ 10⁴ is fine (n²/2 = 5·10⁷ moves); n = 10⁵ front-removals would be 5·10⁹ moves — far past the ~10⁸ steps/s budget, so use ListQueue. Appending n = 10⁷ items with add() is fine (< 2n copies).

2. Core List API: sort, sublist, indexOf, contains

Think of sort() as handing a librarian your own rulebook for "which volume goes first" (the comparator) — she reshuffles the shelf, but she never tells you the exact order she picked up and put down each volume, only that the FINAL shelf obeys your rule.

The comparator contract, a descending sort, and a tiebreaker for stability, as code:

Dart's core library documentation does not guarantee that List.sort() is a stable sort — meaning if two elements compare as "equal" under your comparator, their relative order after sorting is not promised to match their original order. If you need stability (e.g. sorting rows by score but wanting ties to keep their original relative order), make the comparator itself break ties by a secondary key, such as original index:

list.sort((a, b) { final c = a.score.compareTo(b.score); return c != 0 ? c : a.originalIndex.compareTo(b.originalIndex); });

Three more everyday List operations, all straightforward once you know their cost:

"O(n)" made visible: count how many elements a scan looks at.

sublist copies a range into a brand-new list (end index exclusive). indexOf and contains on a plain List are both O(n) — there's no shortcut, every element might need checking. (Compare this to a Set's contains, coming up next — that one is O(1) average, because of hashing.)

Input size → what is feasible: sort is O(n log n): n = 10⁶ ≈ 2·10⁷ comparisons — fine. indexOf/contains are O(n): called inside a loop over n = 10⁵ items that is 10¹⁰ steps — switch to a Set/Map.

3. Hashing from zero

Imagine a huge coat-check room with only 8 numbered hooks, but hundreds of possible coats. You can't give every unique coat its own hook — so instead you use a rule: "take the coat-owner's name, add up the letters, and hang it on hook (sum % 8)." That rule is a hash function: it turns something arbitrary (a name, a string, any key) into a small number you can use as a direct index — turning a slow "search every hook" lookup into a fast "jump straight to the hook" lookup.

A real HashMap/HashSet works the same way. For teaching, we'll build our OWN tiny, hand-checkable hash function (Dart's real String.hashCode algorithm is more complex and not part of the public language spec — you should never depend on its exact values):

Try your own key below — the table already contains cat, ax, dog, and by. Try typing act (an anagram of cat — same letters, same sum, so it lands in the exact same bucket and COLLIDES) or ox (lands in an empty bucket, no collision):

The same table as runnable code: every bucket is a small list (a chain), a collision just makes one chain longer.

A collision does NOT mean data is lost. When two different keys hash to the same bucket, the table keeps a small list at that bucket (called a chain) holding every key that landed there, and checks each one with == to find the right entry. More collisions make lookups slower (closer to O(n) in the worst case, where everything collides into one bucket) — this is exactly why a good hash function should spread keys out as evenly as possible.

A hash table doesn't stay one fixed size forever. As more keys are added, the load factor (how full it is: size ÷ capacity) rises. Once it crosses a threshold (a common choice is 0.75), the table grows and rehashes — every existing key gets a brand-new bucket index computed against the new, bigger capacity:

Rehashing is exactly why a key's bucket position is not something you can rely on staying fixed — and it's O(n) work (touching every entry) whenever it happens. But because it only happens occasionally (capacity keeps doubling), the AVERAGE cost of put()/get() stays O(1) — the same amortized-cost idea as growable List.add() from section 1.

This leads to Dart's == / hashCode contract: if two objects are equal (a == b is true), they must return the same hashCode — otherwise a hash-based collection can never find them. Dart does NOT check this for you — if your == and hashCode disagree, or you mutate a key after inserting it, nothing warns you and lookups quietly fail. Keeping both promises is entirely on you:

Never mutate any field that == or hashCode depends on, once an object is being used as a Map key or Set element. The collection computed the bucket ONCE, at insertion time, and has no way to know the object changed underneath it. The entry doesn't disappear — it just becomes unreachable by lookup, which is often worse than a crash because it fails silently.

When are two objects "equal"?

Hash collections use == and hashCode, so you must know which types compare by value and which only by identity (the very same object). List, Set and Map use identity; String, numbers, records and your own classes with ==/hashCode overridden compare by value:

A hash function turns a key into a bucket index. Collisions are handled by chaining. Load factor triggers a resize + full rehash, which is why bucket positions aren't permanent. If a == b then a.hashCode == b.hashCode must hold — and that hashCode must never change while the object is a live key.

Input size → what is feasible: n = 10⁶ keys in a hash map ≈ 10⁶ steps (O(1) average each). If every key collided into one chain the same work would be n² / 2 = 5·10¹¹ steps — a good hashCode is the difference between feasible and impossible.

4. Set, Map, Queue variants & complexity

A guest list kept in the order people RSVP'd is a LinkedHashSet. A guest list kept alphabetically no matter the RSVP order is a SplayTreeSet. A guest list where you genuinely don't care about (and can't rely on) any particular order at all — just fast "is this person on the list?" checks — is a plain HashSet.

Dart's default {} / {1, 2, 3} literals are NOT a bare, order-agnostic hash table — they default to the insertion-ordered variants:

Default Set literal → LinkedHashSet. Iterates in the exact order elements were first inserted.
Default Map literal → LinkedHashMap. Iterates keys in the exact order they were first inserted (re-assigning an existing key's value does NOT move its position).

From dart:collection you can explicitly choose a different ordering guarantee:

HashSet / HashMap — no ordering guarantee at all (may look "random", and the order can change between SDK versions, so never rely on it). Slightly less memory/bookkeeping overhead than the Linked* variants, since they don't need to track insertion order.
SplayTreeSet / SplayTreeMap — always iterate in sorted order (by a comparator you provide, or natural order by default). Backed by a splay tree (a self-adjusting binary search tree), so operations cost O(log n) amortized rather than O(1) average.
LinkedHashSet / LinkedHashMap — the same implementation the default literals already give you, explicit for when you want to be clear about it in code review.

In code: the type tests, insertion order, what re-assigning a key does, and the sorted/ordered variants.

Queue (from dart:collection, implemented as ListQueue by default) is the fix for the O(n) front-insert/remove problem from section 1:

ListQueue is implemented as a circular buffer internally (a fixed-size backing array where the "start" and "end" pointers can wrap around), which is what lets BOTH ends support O(1) add/remove — something a plain List can only do at one end. A ring buffer in 25 lines (head index + wrap-around + doubling) so you can see why nothing ever shifts:

The classic use of a queue — a breadth-first search work list — written with ListQueue:

The complexity table below, measured: count == calls for a List.contains miss against a hash Set:

Operation	List	LinkedHashSet / LinkedHashMap	HashSet / HashMap	SplayTreeSet / SplayTreeMap	Queue (ListQueue)
Index / key lookup	O(1) by index	O(1) average	O(1) average	O(log n)	O(1) at either end, O(n) middle
Add at end / insert	O(1) amortized (end), O(n) elsewhere	O(1) average	O(1) average	O(log n)	O(1) either end
Remove	O(1) end, O(n) elsewhere	O(1) average	O(1) average	O(log n)	O(1) either end
contains	O(n)	O(1) average	O(1) average	O(log n)	O(n)
Iteration order	insertion / index order	insertion order	unspecified	sorted	front-to-back

Default {} literals are insertion-ordered (Linked*). Reach for plain HashSet/HashMap only when you truly never rely on iteration order. Reach for SplayTree* when you need sorted iteration. Reach for Queue whenever you need fast operations at BOTH ends.

Input size → what is feasible: up to ~10⁷ Set/Map/Queue operations fit in a second. SplayTree* costs ≈ log₂ n ≈ 20 comparisons per operation at n = 10⁶ — pay it only when you need sorted order or firstKeyAfter/lastKeyBefore queries.

5. Iterables: lazy vs. eager

.where() and .map() are like writing instructions on a recipe card — "filter for odd numbers, then square them" — without actually cooking anything yet. Nothing happens until someone actually walks into the kitchen and starts cooking (calls .toList(), loops with for..in, or calls .fold()/.reduce()). That's what lazy means: the description is built first, the work happens later, on demand.

The same program as runnable Dart:

A subtle bug this causes: if you call .where(...) or .map(...) and never iterate the result (never call .toList(), never loop over it, etc.), your callback function never runs at all — not even once. Beginners sometimes expect side effects (like a print inside the callback) to happen immediately, and are confused when nothing prints.

Laziness isn't just a curiosity — it lets an operation like .take() stop early, without ever touching the rest of the source:

This is also why chaining .where().map().where() on a huge (or even infinite, via a generator) sequence and then calling .take(5) is efficient: each element is pulled through the ENTIRE chain one at a time, and the chain can stop as soon as enough results exist — it never allocates an intermediate list for each stage the way calling .toList() after every single step would.

Terminal operations that force evaluation (turn laziness into a real, concrete result):

reduce() throws a StateError if the Iterable is empty — there is no first element to use as the starting accumulator. fold() never has this problem because YOU supply the seed value explicitly, so it works fine (returning just the seed) even on an empty Iterable.

Because a lazy chain is only a description, every pass re-runs every callback, and the chain is a view of its source (a later change to the source shows up), whereas toList() is a snapshot:

Laziness also makes infinite sequences possible: a sync* generator produces the next value only when asked.

map/where/take/expand build a lazy pipeline description; nothing runs until a terminal operation (toList, for..in, fold, reduce, forEach...) actually iterates it, one element at a time through the whole chain. reduce throws on empty; fold does not, because it takes an explicit seed.

Input size → what is feasible: a lazy chain over n = 10⁶ items costs one pass (10⁶ callback calls) per terminal operation; iterating it k times costs k·n, so for k > 1 call toList() once. take(m) on a huge or infinite source costs only about m / (fraction that passes the filters) callbacks.

6. Collection literals: if, for, spread, unmodifiable

A collection-if is like packing a suitcase where one item only goes in "if it's going to rain" — you decide as you pack, not afterward. A collection-for is like packing one of each color from a rack, without writing out each color by hand. A spread ... is like dumping the entire contents of a smaller bag straight into the suitcase, in place.

The same literal as runnable Dart, plus the Set and Map forms of collection-if/for/spread:

Plain ...expr (spread) expects an actual collection. With sound null safety, spreading a nullable value such as List<int>? does not even compile; forcing it with ...expr! compiles but throws a TypeError at run time when the value is null. If the collection might be null, use the null-aware spread ...?expr instead, which quietly contributes nothing when it's null.

List.unmodifiable(...) takes a snapshot of a collection's CURRENT contents and locks it — any later attempt to mutate that snapshot throws. A const list literal is unmodifiable for the same reason, permanently, from the moment it's compiled:

Collection-if/for build the list AS it's written, evaluated once, in source order. Spread ... inlines another collection's elements; ...? is the null-safe version. List.unmodifiable and const collections both throw UnsupportedError on any mutation attempt.

Input size → what is feasible: building [...a, ...b] copies |a| + |b| elements, O(n) once; doing it inside a loop of n iterations is O(n²) (n = 10⁵ → 5·10⁹ copies) — use add/addAll on one list instead. The full List.unmodifiable/view/copy rules are in D22.

7. Choosing the right collection

Choosing a collection is like choosing a container at a hardware store: a numbered drawer cabinet (List) for things you access by position, a "have I already got one of these?" checklist (Set) for uniqueness, a labeled-bin filing system (Map) for looking things up by a name/ID, and a ticket queue at a counter (Queue) for strict first-come-first-served or both-ends processing.

You need to...	Reach for	Why
Access elements by numeric position, keep duplicates, care about order	`List`	Contiguous backing array → O(1) index access
Guarantee no duplicates, fast "have I seen this?" checks	`Set` (default `LinkedHashSet`)	Hashing → O(1) average `contains`/`add`, keeps insertion order
Look values up by a key/name instead of a position	`Map` (default `LinkedHashMap`)	Hashing on the key → O(1) average get/put
Iterate in sorted order at all times	`SplayTreeSet`/`SplayTreeMap`	Splay tree (self-adjusting BST) keeps keys ordered; O(log n) amortized ops
Truly don't care about any iteration order, want the leanest hash table	`HashSet`/`HashMap`	No insertion-order bookkeeping overhead
Add/remove from BOTH ends fast (e.g. a sliding window, a work queue)	`Queue` (`ListQueue`)	Circular buffer → O(1) at either end
Transform/filter a source without building intermediate lists, or possibly stop early	`Iterable` chain (`.where().map()`...)	Lazy evaluation, one pass, can short-circuit with `.take()`

Ask "how will I access this data?" first — by position (List), by uniqueness/membership (Set), by key (Map), or strictly from the ends (Queue) — and the right collection usually falls out immediately.

Input size → what is feasible: n ≤ 10³: anything works, pick the most readable. n = 10⁵–10⁶ with repeated membership/lookup: Set/Map, never List.contains (n² = 10¹⁰–10¹²). Repeated front removal: ListQueue. Sorted iteration or range queries: SplayTree*. Every method of each collection: see the Full API box at the top.

Quiz

Interview questions

Cheat sheet

Concept	Fact
List backing storage	Contiguous array; fixed-length (`List.filled(n,v)`, growable defaults false) throws `UnsupportedError` on `add()`
Growable List add()	Amortized O(1): occasional O(n) copy into a bigger backing array, otherwise O(1)
insert()/removeAt() not at the end	O(n) — every following element shifts
Index access, add/removeLast at end	O(1)
sort(comparator)	NOT guaranteed stable — add a tiebreaker in the comparator if you need stability
sublist(start, end)	End EXCLUSIVE, returns a new list, O(k) copy
indexOf / contains on List	O(n) — linear scan
Hash function	Turns a key into a bucket index (`hash % capacity`); collisions chained per bucket
Load factor & resize	size ÷ capacity crossing a threshold (commonly 0.75) triggers a full rehash into a bigger table — O(n) occasionally, O(1) amortized
== / hashCode contract	`a == b` ⟹ `a.hashCode == b.hashCode`; never mutate a field a live key's == /hashCode depends on
Default {} / {a,b} literals	`LinkedHashSet` / `LinkedHashMap` — insertion order
HashSet / HashMap	dart:collection; no ordering guarantee
SplayTreeSet / SplayTreeMap	dart:collection; always sorted iteration, O(log n) amortized ops
Queue (ListQueue)	dart:collection; O(1) add/remove at BOTH ends (circular buffer)
Iterable laziness	`map`/`where`/`take`/`expand` only run when a terminal op (`toList`, loop, `fold`, `reduce`...) iterates
reduce vs fold	`reduce` seeds from the first element, throws `StateError` on empty; `fold` takes an explicit seed, safe on empty
Collection-if / collection-for	Build the literal in source order, evaluated once at construction
Spread ... / ...?	Inlines another collection's elements; `...?` skips a `null` collection safely
List.unmodifiable / const	Snapshot/compile-time list, any mutation throws `UnsupportedError`