What are the differences between List, Set, and Map?

The key to choosing is to think about how you'll access the data, not how you'll store it. List is an ordered sequence (access by index), Set is a bag of unique values (fast membership checks), and Map is a key→value dictionary (fast lookup by key).

* The default Linked* implementations do preserve insertion order — they're just not sorted.

---

Code in action

// List — ordered, allows duplicates
final scores = <int>[90, 85, 90, 70];
scores.add(100);                    // [90, 85, 90, 70, 100]
scores[0];                          // 90 — index access, O(1)
scores.where((s) => s >= 90);       // (90, 90, 100)

// Set — unique values, fast membership
final tags = <String>{'flutter', 'dart', 'flutter'};  // {'flutter', 'dart'}
tags.add('mobile');                 // {'flutter', 'dart', 'mobile'}
tags.contains('dart');              // true — O(1), not O(n)!

// Quick dedupe trick
final unique = [1, 2, 2, 3, 3].toSet().toList();      // [1, 2, 3]

// Set algebra
final a = {1, 2, 3}, b = {2, 3, 4};
a.union(b);                         // {1, 2, 3, 4}
a.intersection(b);                  // {2, 3}
a.difference(b);                    // {1}

// Map — key→value lookup
final ages = <String, int>{'Alice': 30, 'Bob': 25};
ages['Charlie'] = 35;               // add/update
ages['Alice'];                      // 30
ages['Zoe'];                        // null — missing key returns null
ages['Zoe'] ?? 0;                   // 0 — safe default
ages.putIfAbsent('Dave', () => 40); // only adds if missing

for (final entry in ages.entries) {
  print('${entry.key}: ${entry.value}');
}

---

Performance — the cheat sheet

* Amortised. Occasional O(n) when the underlying array resizes.

The big takeaway: contains on a List is O(n). If you're checking membership in a loop, convert to a Set first.

---

When to use which

---

Common mistakes to avoid

// ❌ Using List.contains in a hot loop
final blocked = ['a', 'b', 'c', /* ...10k items */];
for (final user in users) {
  if (blocked.contains(user.id)) {  // O(n) every iteration → O(n²) total
    ...
  }
}

// ✅ Convert once, then check
final blockedSet = blocked.toSet();
for (final user in users) {
  if (blockedSet.contains(user.id)) { ... }   // O(1) per check
}

// ❌ Treating Map access like it can't be null
int age = ages['Alice'];            // ❌ ages['Alice'] is int?, not int

// ✅ Handle the missing key
final age = ages['Alice'] ?? 0;

// ❌ Mutating a const collection
const tags = {'a', 'b'};
// tags.add('c');                   // 💥 Unsupported — const sets are immutable

// ❌ Using mutable objects as Map/Set keys
final key = [1, 2];
final m = {key: 'hi'};
key.add(3);                         // hash changed → can't find it anymore

// ✅ Use immutable keys (String, int, or a value-class with proper ==/hashCode)

---

Interview follow-ups

1. Why is Set.contains O(1) but List.contains O(n)? Sets are backed by a hash table — Dart hashes the value and jumps straight to the bucket. Lists have no such index, so contains walks the array element by element.

2. What determines whether two objects are "the same" in a Set or Map key? Dart uses == and hashCode. Override both (or use class extends Equatable / Dart 3 records) when you want value-based equality instead of identity.

3. What's the difference between {} and <String>{}? {} is an empty Map, not an empty Set — a classic gotcha. Use <String>{} (or <String, int>{} for a Map) to be explicit. With a non-empty literal Dart can infer it: {1, 2} is a Set<int>.

4. When would you use SplayTreeMap over Map? When you need keys sorted (e.g., leaderboards, time-series buckets) or fast "next/previous key" queries. The trade-off is O(log n) operations instead of O(1).