Every Built-in Method: List
After this lesson you will know what a Dart List looks like inside memory, why add is cheap but insert(0, x) is not, and you will have seen every single public member of List (constructors, getters, setters, operators, methods, static helpers and the Iterable members it inherits) with its cost, the exceptions it can throw, whether it changes the list or returns something new, and a runnable example whose exact output was checked against the real Dart SDK.
Source of truth: the Dart SDK 3.11 sources (core/list.dart, core/iterable.dart, collection/iterable.dart, and the VM implementation _internal/vm/lib/growable_array.dart). All complexities and growth numbers below describe the native VM / AOT implementation; on the web (dart2js) a List is a JavaScript array and the growth details differ. Every printed result in this lesson was produced by running the code with Dart 3.11 and is asserted in verify/d26.dart.
1. What a List really is (memory picture)
Picture a row of numbered lockers in a school corridor: locker 0, locker 1, locker 2 ... Each locker holds one thing. At the corridor entrance a clipboard says "lockers in use: 3" and points to the row. The row itself is the array (a fixed block of equally sized slots side by side in memory). The clipboard is the List object. The number on the clipboard is the length; the number of lockers that physically exist is the capacity. If you want a 4th item but all lockers are taken, you cannot extend the corridor: you must build a bigger corridor, move everything over, and throw the old one away.
Some words, defined once. The heap is a big shared storage room where objects live. A reference is an arrow (really a memory address) from a variable to an object. An index is a slot number starting at 0. A growable list can change length; a fixed-length list cannot.
Watch the three objects involved when you build and grow a list: the variable xs on the stack (a small scratch area for local variables), the _GrowableList object (two fields: length and _data), and the array _data points to.
Here is a small working model of what add does, simplified from the real _GrowableList in growable_array.dart (Dart 3.11). The real one is: if length == _capacity call _growToNextCapacity(), then _setLength(len + 1) and store. The model keeps the same steps: if full, grow; then store.
The real rule is int _nextCapacity(int old) => (old * 2) | 3; (also in the model, section 2). (c * 2) | 3 means "double it, then force the lowest two bits to 1", so the capacity goes 0 → 3 → 7 → 15 → 31 → 63. The array that is actually allocated is capacity | 1 slots (always odd, which the garbage collector gets for free because of memory alignment). Capacity is not observable from Dart code, only from reading the SDK, so treat these numbers as an implementation detail of Dart 3.11, not a promise.
Reading and writing one slot never walks the list: the address of slot i is base + i × slot size, which is one multiplication and one memory access: O(1) (constant time, independent of the list size). Try the edge case: an index outside 0 .. length-1 is rejected by a bounds check before any memory is touched.
List<List<int>> the slots hold arrows to other lists, not copies.2. Growth and "amortised O(1)"
A single add that finds the array full costs O(n) (it copies n references). So why do people say add is O(1)? Because growing multiplies the capacity (about ×2) instead of adding a fixed amount. After a copy of n elements there are n free slots, so the next ~n adds are free. Spread the copying cost over all the adds and it is a small constant per add: that is called amortised O(1) (an average over a long run, not a promise for every single call). Run it, then change n.
The capacity rule in Dart, and a counter that reproduces the animation (this models the rule from the source; it does not read a real list's capacity):
| adds so far (n) | capacity after | total copies so far | copies ≤ 2n? |
|---|---|---|---|
| 3 | 3 | 0 | yes |
| 4 | 7 | 3 | yes |
| 8 | 15 | 10 | yes |
| 16 | 31 | 25 | yes |
| 1000 | 1023 | 1012 | yes (1012 ≤ 2000) |
insert(0, x) and removeAt(0) are not amortised O(1): every call shifts the whole tail, so n calls cost about n²/2 moves. If you need a queue, use ListQueue (a ring buffer, lesson D28), not removeAt(0) on a List.The "about n²/2" claim as code: the i-th front insert shifts the i elements already stored, so the total is 0 + 1 + ... + (n-1), which equals n(n-1)/2:
Input size → what is feasible: n = 106 adds on a growable list take a few milliseconds of copying overall; n = 106 calls of insert(0, x) would be ~5·1011 element moves (minutes), so redesign instead of micro-tuning.
3. Every member, grouped by purpose
Each card shows: the signature, what it means in plain words, a badge telling you what happens to the list, the cost and why, the exceptions, and a runnable example with its exact output.
| Badge | Meaning |
|---|---|
| mutates | changes this list object (length, order or contents) |
| returns new | builds a new object (list, set, string); the original is untouched |
| lazy view | returns a cheap wrapper that reads the original when iterated; nothing is copied now, later changes to the list show through |
| read-only | reads or reports; changes nothing, allocates nothing important |
| creates | a constructor: makes a brand-new list |
List itself (6 constructors, 3 static helpers, 34 instance members), 29 inherited from Iterable, 6 from the Iterable extensions (indexed, firstOrNull, lastOrNull, singleOrNull, elementAtOrNull, nonNulls) and 3 from Object (hashCode, runtimeType, noSuchMethod). Deprecated: none of these is marked @Deprecated in Dart 3.11. The old unnamed constructor List(n) no longer exists: List<int>(3) is a compile error ("doesn't have an unnamed constructor"); use List.filled instead. The extension members are declared in dart:collection but dart:core re-exports them, so they work with no import (checked with Dart 3.11.5).Players use a mini-language so you can type your own experiments: the first part is the list ([3,1,2], or fixed[...], unmod[...], nullable[...], of[...]), then operations separated by ;, for example [3,1,2] ; add 4 ; insert 0 9 ; removeWhere even. Values are whole numbers from -999 to 999, at most 12 values and 12 operations. A predicate is even, odd, >N, <N or =N. Lists in arguments use brackets: addAll [1,2].
Index of every member (click a name to jump to its card)
3.1 Create: constructors and literals
How a list is created decides two things: fixed-length or growable, and how big its array is. [] literals and the constructors with growable: true (the default for of, from, generate) can grow; of, filled and generate allocate n | 1 slots (an iterable whose length is unknown up front is added element by element instead, so its capacity ends on a doubling step); List.filled and List.empty default to fixed. Input size → feasible: building a list of n = 107 ints costs ~107 writes (tens of milliseconds); that is fine, but List.filled with a mutable object shares one object, which is a bug rather than a cost.
3.2 Read and inspect
Reading never changes the list. Index reads are O(1); sublist copies; getRange and reversed are views. Remember: == on lists is identity. Input size → feasible: any n up to memory limits for index reads; sublist of k elements costs k, so slicing a 106 list inside a 106 loop (1012 steps) is too slow, use index ranges or getRange.
3.3 Search
A plain list has no hash table or sorted order to exploit, so every search is a linear scan: O(n). They differ only in where they start, what counts as a match and when they stop. Input size → feasible: one scan of n = 106 is ~1 ms; calling contains n times on n = 105 elements is 1010 steps (too slow): put the elements in a Set or sort and binary-search.
3.4 Add
Adding at the end is amortised O(1). Adding anywhere else must slide the tail to the right first: O(n − index). Input size → feasible: n = 106 adds fine; n = 105 insert(0, x) calls = ~5·109 moves (several seconds): build in reverse or use a ListQueue.
3.5 Change in place (the length stays the same, except length = and replaceRange)
These overwrite slots that already exist. Writing one slot is O(1); the range versions are O(k) for k slots. Input size → feasible: overwriting k = 106 slots takes about a millisecond.
3.6 Remove
Removing from the end is O(1). Removing elsewhere closes the gap by sliding the tail left: O(n − index). Removing many elements one by one with remove is O(n²); removeWhere does it in a single O(n) pass. Input size → feasible: n = 105 single remove calls in a loop = ~1010 steps (too slow); one removeWhere over n = 106 = ~106 steps.
length setter (used by every removal): after shrinking to newLength, Dart allocates a smaller array only if 2 × newLength < oldLength − newLength (the SDK comment says it picks the variant with fewer writes). Otherwise it keeps the big array and writes null into the freed slots, so capacity stays. The player captions show which branch ran. As code:3.7 Reorder and re-view
sort and shuffle rearrange this list in place; reversed and asMap give views and leave the list alone. Input size → feasible: sort of n = 106 takes ~106·20 = 2·107 comparisons (fast); a hand-written O(n²) sort at n = 105 is 1010 steps (too slow).
The shuffle players need a "random" source you control, so the code panels use a tiny scripted Random whose nextInt returns your numbers (reduced to fit). With a real Random(seed) the same algorithm runs, only the picks differ:
3.8 Transform, iterate and convert (inherited from Iterable)
Most of these come from Iterable. The ones that return an Iterable (map, where, take ...) are lazy: they remember a recipe and do the work only when you loop or call toList(), and they redo it on every new loop. Watch a chain pull one element at a time. (Lesson D25 covers Iterable in depth.) Input size → feasible: a chain over n = 106 elements is ~106 steps per pass; iterating the same lazy chain 1000 times repeats that 1000 times, so call toList() once if you reuse it.
fold and reduce squash the whole list into one value:
Iterable.generate, Iterable.empty, Iterable.withIterator, Iterable.castFrom, Iterable.iterableToShortString and Iterable.iterableToFullString belong to Iterable (lesson D25). Typed lists such as Uint8List and Int32List implement the same List API on a compact fixed-length byte buffer (lesson D16). UnmodifiableListView and ListBase are in lesson D28.4. Mutable vs immutable lists
"Mutable" means the object can change after it is made. Whether you can change a list depends on how it was made, and which members throw:
| How it was made | Change an elementxs[i] = v, sort, shuffle, fillRange, setRange | Change the lengthadd, remove*, insert*, clear, length = | Copy semantics |
|---|---|---|---|
[1, 2], List.of, toList(), List.generate | allowed | allowed (growable) | new independent list (shallow) |
List.filled(n, x) (default), toList(growable: false), List.empty() | allowed | UnsupportedError: fixed-length | new independent list |
List.unmodifiable(src) | UnsupportedError | UnsupportedError | a frozen copy: later changes to src do not show |
const [1, 2] | UnsupportedError | UnsupportedError | one shared canonical object: identical(const [1,2], const [1,2]) is true |
UnmodifiableListView(src) (D28) | UnsupportedError | UnsupportedError | a read-only view: changes to src do show through |
Three traps follow from "variables hold references": aliasing (two names, one list), shallow copy (the outer list is copied but the inner lists are shared) and changing a list while looping over it. Step through each.
final keyword only stops you from pointing the variable at another list. final xs = [1]; xs.add(2); is legal. Only const (or List.unmodifiable) makes the object unchangeable. The for-in check only compares the length: a loop body that removes one element and adds one element does not throw, it silently reads shifted data.toList(), List.of, [...xs] and sublist(0) are all shallow.5. Choosing the right collection
The best structure is the one whose cheap operations match what your program does most. Complexities are for n elements on the native VM.
| Operation | List | ListQueue (D28) | LinkedList (D28) | Set (default LinkedHashSet, D27) |
|---|---|---|---|---|
read by index [i] | O(1) | O(1) | no index (O(n) walk) | no index |
| add at end | O(1) amortised | O(1) amortised | O(1) | O(1) expected |
| add / remove at front | O(n) (tail shifts) | O(1) amortised (ring buffer) | O(1) | n/a |
| insert / remove in the middle | O(n) | O(n) | O(1) if you hold the entry | remove O(1) expected |
contains / indexOf | O(n) | O(n) | O(n) | O(1) expected |
| keeps duplicates | yes | yes | yes | no (unique) |
| order guarantee | by index | by position | by position | insertion order |
| memory per element | 1 slot (8 bytes on 64-bit; 4 with pointer compression) + spare capacity | 1 slot + spare | a node object per element | hash table entry |
Rule of thumb: default to List. Switch to Set when you keep asking "is it in there?", to ListQueue when you remove from the front, and to a typed list (Uint8List, Float64List, D16) when you hold millions of numbers. Input size → feasible: a List handles 107 ints (80 MB of slots) comfortably; ten million contains calls on it would not.
Quiz
Interview questions
Cheat sheet: every member
Generated from the same member data as the cards above: every member with its cost and whether it mutates or returns something new.