Collections in Dart — Lists, Sets, Maps, and Performance Trade-offs

Open the contacts app on your phone. You see a long list of contacts. How does Dart actually store all of that?

There are several built-in data types that can hold bulk data. Each one solves a slightly different problem, and choosing the right one shapes the performance of the whole program.

Let's start with the same set of phone numbers and see what each collection does with them.



List keeps the order we put things in. It also keeps the duplicate at [4] — Lists don't ask any questions. Set silently drops the duplicate, but loses the position index. Map attaches each number to a name, which is what we usually want for contacts — but now the structure is fundamentally different.

So how do we pick? The mental algorithm is small enough to memorise.



With the map in our head, let's go deep on each one.

A List is an ordered collection of objects. Each element has an index, starting at zero. We can store anything in a list, including duplicates.

void main() {
  List phoneNumbers = [
    '987654321',
    '123456789',
    '9876102345',
    '7876413232',
    '123456789',   // happily kept — Lists ask no questions
  ];
  print(phoneNumbers);
  print(phoneNumbers.length);   // 5
  print(phoneNumbers[2]);       // '9876102345'
}

Common operations on a list include:

phoneNumbers.add('555444333');         // append at end
phoneNumbers.insert(0, '111000222');    // insert at front
phoneNumbers.removeAt(1);               // remove by position
phoneNumbers.remove('123456789');       // remove first match by value
phoneNumbers.contains('987654321');     // true
phoneNumbers.indexOf('9876102345');     // 2
phoneNumbers.sort();                    // in-place sort

List flavours. Not all lists are equal. Dart gives us four shapes of list, each with its own rules.



How adding to a growable list actually works. When we write list.add(x), Dart appends to a backing array. But what happens when that array runs out of room?



Most calls to add are cheap — they just write to an empty slot. Once in a while, the backing array fills up and Dart has to allocate a new array twice the size and copy everything over. That copy is expensive, but it happens rarely enough that the average cost stays constant. This is what "amortized O(1)" means.

Lists happily store the same number twice. That's a feature for sequences (a chat log can repeat itself), but for a phonebook it's a bug. We want to drop the duplicate entry.

That's what a Set does. It keeps every distinct element exactly once.

void main() {
  var phoneNumbers = [
    '987654321', '123456789', '9876102345', '7876413232', '123456789',
  ];

  Set uniqueNumbers = {...phoneNumbers};   // spread into a Set
  print(uniqueNumbers);          // {987654321, 123456789, 9876102345, 7876413232}
  print(uniqueNumbers.length);   // 4 — the duplicate is gone
}

A surprise about Dart's default Set. When we write {...} or call Set(), we get a LinkedHashSet under the hood. The "linked" part means Dart secretly tracks insertion order, so iterating over the set produces elements in the order we put them in. Most other languages don't promise this; Dart does.

Set operations. The classic three from set theory — union, intersection, difference — are built into Dart's Set, and a Venn diagram is the fastest way to see what each one does.

var a = {1, 2, 3, 4};
var b = {3, 4, 5, 6};

print(a.union(b));         // {1, 2, 3, 4, 5, 6}
print(a.intersection(b));  // {3, 4}
print(a.difference(b));    // {1, 2}

The performance jewel — Set's contains is fast. Checking whether a List contains a value means scanning every element until we find it, which is O(n). Checking whether a Set contains a value uses hashing and runs in O(1) on average. For large collections, this is a thousand-times-faster kind of difference. We'll see exactly how Set pulls that off in the next topic, because Map uses the same trick.

A Set deduplicates phone numbers, but we've still lost the name. To go from "9876…" back to "Mom" we need the key→value relationship that a Map provides.

void main() {
  Map phoneNumbers = {
    'Ankit':   '987654321',
    'Mom':     '123456789',
    'Dad':     '9876102345',
    'Brother': '7876413232',
    'Sister':  '123456789',
  };
  print(phoneNumbers);
  print(phoneNumbers['Mom']);   // '123456789'
}

Notice that Sister and Mom can share the same number — values don't have to be unique, only keys do. That matches real life: two people can have the same phone, but they have different names.

The empty-literal gotcha. Dart's collection literal syntax has one trap that catches almost everyone the first time.



The bare {} looks like an empty set, but it's actually an empty Map. To get an empty Set, we need to give Dart a type hint or use the explicit constructor.

How Map (and Set) achieve O(1) lookup. When we write phoneNumbers['Mom'], Dart doesn't scan the whole map. It runs the key through a hash function, which gives it an integer. That integer, modulo the bucket count, tells Dart exactly which bucket to look in. Inside the bucket, it compares keys to find the match.



The whole point of hashing is to skip the linear scan. We compute the bucket index once, then look only inside that single bucket. Sets work the same way — they're basically Maps where we only care about the keys.

Three Map flavours. Just like List, Map comes in a few shapes that pick different trade-offs.



Common Map operations to know:

phoneNumbers['Cousin'] = '555000111';   // add or update
phoneNumbers.containsKey('Mom');         // true
phoneNumbers.containsValue('123456789'); // true (slower — O(n))
phoneNumbers.remove('Brother');
phoneNumbers.keys;       // Iterable of keys
phoneNumbers.values;     // Iterable of values
phoneNumbers.entries;    // Iterable of MapEntry(key, value)

Once we have a collection, the next thing we want to do is walk through it. Dart has several ways, ranging from the imperative for loop to functional one-liners.

The basic loops.

// Classic for-in
for (var number in phoneNumbers) {
  print(number);
}

// For a Map, iterate keys, values, or both
for (var name in phoneBook.keys) { ... }
for (var number in phoneBook.values) { ... }
for (var entry in phoneBook.entries) {
  print('${entry.key} → ${entry.value}');
}

// forEach takes a function
phoneNumbers.forEach((n) => print(n));

The functional toolkit. Most real iteration code reaches for map, where, and fold instead of explicit loops. They're shorter, clearer, and chainable.

var numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

// map — transform each element
var doubled = numbers.map((n) => n * 2);
// (2, 4, 6, 8, 10, 12, 14, 16, 18, 20)

// where — filter
var evens = numbers.where((n) => n.isEven);
// (2, 4, 6, 8, 10)

// fold — collapse to a single value
var sum = numbers.fold(0, (acc, n) => acc + n);
// 55

// chain them
var sumOfDoubledEvens = numbers
  .where((n) => n.isEven)
  .map((n) => n * 2)
  .fold(0, (acc, n) => acc + n);
// 60

The Iterable hierarchy. List, Set, and the keys/values of a Map are all Iterable. So is the result of where or map. This is why we can chain operations across different collection types — they all speak the same iteration protocol.

The lazy evaluation gotcha. Here's the surprise that bites people. where and map return lazy Iterables. Nothing actually happens until we iterate. And every time we iterate, the work runs again.

var numbers = [1, 2, 3, 4, 5];
var bigOnes = numbers.where((n) {
  print('checking $n');
  return n > 3;
});

// Nothing has been printed yet!

print(bigOnes.first);   // prints "checking 1" through "checking 4", then 4
print(bigOnes.length);  // prints "checking 1" through "checking 5" AGAIN — re-runs the filter

For a lazy iterable used many times, the filter runs every time. The fix is to materialise with .toList() or .toSet() when we'll use the result more than once:

var bigOnes = numbers.where((n) => n > 3).toList();
// now bigOnes is a real List, work happens once

Reach for lazy iterables when chaining transformations (the laziness avoids building intermediate lists). Reach for .toList() when storing or reusing the result.

Now that we know what each collection can do, the real question is when to pick which. The answer almost always comes down to the access pattern.



The big lessons from the table:

• If we'll ever call contains on a big collection, use a Set. The List version is O(n) — a thousand-element scan for every check.
• If we want to look up by name, ID, or any other "key," use a Map. Don't simulate it with a List of records.
• If we need positional access (the third item, the last item, the items in order), use a List.
• Inserting at the start of a List is O(n) — every other element has to shift. If we're doing this a lot, our data structure is probably wrong.

The TypedData escape hatch for numeric data. Everything in this table is the cost for general-purpose collections that store any kind of object. For large numeric arrays, we have a different option — the typed lists from Episode 3 (Uint8List, Int32List, Float64List) store unboxed values contiguously and skip the per-element pointer overhead. For image, audio, or sensor data, that's the right choice. The boxing story we covered in Episodes 3 and 4.5 applies in full here: a List<int> of byte-range values can use roughly 8 times the memory of the equivalent Uint8List. When numbers are the data, TypedData wins.

Dart has a few syntax features that make working with collections genuinely enjoyable. They blur the line between defining a collection and computing one.

The spread operator. Three dots flatten a collection into another collection literal.

void main() {
  List<int> list1 = [1, 2, 3];
  List<int> list2 = [4, 5, 6];

  // Combine two lists
  var combined = [...list1, ...list2];   // [1, 2, 3, 4, 5, 6]

  // Copy and extend
  var extended = [...list1, 7, 8, 9];    // [1, 2, 3, 7, 8, 9]

  // Works for Set and Map literals too
  var uniqueNumbers = {...phoneList};
  var merged = {...mapA, ...mapB};
}

Spread also has a null-aware version ...? that's a no-op when the source is null — handy when building collections from optional inputs.

Collection-if. Inline conditionals inside collection literals. The first time we see this, it feels like magic.

bool isLoggedIn = true;
bool hasNotifications = false;

var menuItems = [
  'Home',
  'About',
  if (isLoggedIn) 'Profile',
  if (isLoggedIn) 'Settings',
  if (hasNotifications) 'Inbox',
  'Logout',
];
// ['Home', 'About', 'Profile', 'Settings', 'Logout']

Compare that to the imperative alternative — three separate if blocks each calling add — and the collection-if version is harder to get wrong.

Collection-for. The same idea, but with a loop.

var numbers = [1, 2, 3, 4, 5];

var doubled = [for (var n in numbers) n * 2];
// [2, 4, 6, 8, 10]

var phoneTags = [
  for (var entry in phoneBook.entries)
    '${entry.key}: ${entry.value}',
];

// Combine collection-if and collection-for
var bigNumbers = [
  for (var n in numbers) if (n > 2) n * 10,
];
// [30, 40, 50]

Const collections. When a collection's contents are known at compile time and never change, prefix it with const. Dart will allocate it exactly once and reuse the same canonical instance — much like the canonical booleans from Episode 2 and string literals from Episode 5.

const validRoles = {'admin', 'editor', 'viewer'};
const httpCodes = {200: 'OK', 404: 'Not Found', 500: 'Error'};

Unmodifiable views. Wrap a collection to expose it without letting callers mutate it. Great for public API surfaces where we want to share data but keep ownership.

final _internalList = [1, 2, 3];
List<int> get items => List.unmodifiable(_internalList);

var view = items;
view.add(4);   // throws — UnsupportedError

That completes the data-foundation arc of this series. Booleans for transistor states. Integers and doubles for counting and measuring. Strings for text. Collections for the bulk data of every real program. Maps especially are the workhorse of app development — we'll see them everywhere when we move on to Flutter, from widget configuration to API responses to state management. Now we have the right mental model for picking the right one.