Data Structure in Dart – Advanced data structures

1. Why Advanced Data Structures?

Basic structures (arrays, stacks, trees, graphs) are building blocks.
Advanced data structures solve problems like:

• Fast connectivity checks
• Efficient prefix search
• Range queries
• Caching
• Large-scale indexing

These appear in:

• Databases (B-Trees)
• Search engines (Trie)
• Networks (Union-Find)
• Mobile apps (LRU Cache)

---

2. Disjoint Set (Union–Find)

Concept

Used to track connected components.

Supports:

• find(x) → which group does x belong to?
• union(x, y) → merge groups

Used in:

• Kruskal’s MST
• Network connectivity
• Friend groups

---

Dart Implementation

class UnionFind {
  final List<int> parent;
  final List<int> rank;  UnionFind(int size)
      : parent = List.generate(size, (i) => i),
        rank = List.filled(size, 0);  int find(int x) {
    if (parent[x] != x) {
      parent[x] = find(parent[x]); // Path compression
    }
    return parent[x];
  }  void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);    if (rootX == rootY) return;    if (rank[rootX] < rank[rootY]) {
      parent[rootX] = rootY;
    } else if (rank[rootX] > rank[rootY]) {
      parent[rootY] = rootX;
    } else {
      parent[rootY] = rootX;
      rank[rootX]++;
    }
  }
}

⏱️ Time complexity: almost O(1) (inverse Ackermann)

---

3. Trie (Prefix Tree)

Concept

Optimized tree for string searching.

      root
      |
      c
      |
      a
      |
      t*

Used in:

• Autocomplete
• Spell check
• Search engines

---

Trie Node in Dart

class TrieNode {
  Map<String, TrieNode> children = {};
  bool isEnd = false;
}class Trie {
  final TrieNode root = TrieNode();  void insert(String word) {
    TrieNode node = root;
    for (var char in word.split('')) {
      node.children.putIfAbsent(char, () => TrieNode());
      node = node.children[char]!;
    }
    node.isEnd = true;
  }  bool search(String word) {
    TrieNode node = root;
    for (var char in word.split('')) {
      if (!node.children.containsKey(char)) return false;
      node = node.children[char]!;
    }
    return node.isEnd;
  }  bool startsWith(String prefix) {
    TrieNode node = root;
    for (var char in prefix.split('')) {
      if (!node.children.containsKey(char)) return false;
      node = node.children[char]!;
    }
    return true;
  }
}

---

Flutter Use Case – Autocomplete

• Each keystroke → prefix search
• Extremely fast
• Used in search bars

---

4. LRU Cache (Least Recently Used)

Concept

Keeps most recently used items.
Evicts least recently used item when full.

Used in:

• Image cache
• API cache
• Database query cache

---

LRU Cache Implementation (HashMap + Doubly Linked List)

import 'dart:collection';class LRUCache<K, V> {
  final int capacity;
  final LinkedHashMap<K, V> _cache = LinkedHashMap();  LRUCache(this.capacity);  V? get(K key) {
    if (!_cache.containsKey(key)) return null;
    V value = _cache.remove(key)!;
    _cache[key] = value; // move to end
    return value;
  }  void put(K key, V value) {
    if (_cache.containsKey(key)) {
      _cache.remove(key);
    } else if (_cache.length == capacity) {
      _cache.remove(_cache.keys.first);
    }
    _cache[key] = value;
  }
}

---

Flutter Example

• Cache API responses
• Prevent unnecessary network calls
• Improve UI performance

---

5. Segment Tree

Concept

Used for range queries:

• Sum
• Min
• Max

Array: [1, 3, 5, 7, 9, 11]
Segment Tree stores range sums

---

Dart Example (Range Sum)

class SegmentTree {
  late List<int> tree;
  int n;  SegmentTree(List<int> nums) : n = nums.length {
    tree = List.filled(4 * n, 0);
    build(nums, 0, 0, n - 1);
  }  void build(List<int> nums, int node, int start, int end) {
    if (start == end) {
      tree[node] = nums[start];
    } else {
      int mid = (start + end) ~/ 2;
      build(nums, node * 2 + 1, start, mid);
      build(nums, node * 2 + 2, mid + 1, end);
      tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2];
    }
  }  int query(int l, int r) {
    return _query(0, 0, n - 1, l, r);
  }  int _query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return tree[node];    int mid = (start + end) ~/ 2;
    return _query(node * 2 + 1, start, mid, l, r) +
        _query(node * 2 + 2, mid + 1, end, l, r);
  }
}

---

6. Fenwick Tree (Binary Indexed Tree)

Concept

Optimized for:

• Prefix sums
• Frequency counts

Faster & simpler than Segment Tree.

---

Dart Example

class FenwickTree {
  final List<int> tree;  FenwickTree(int size) : tree = List.filled(size + 1, 0);  void update(int index, int delta) {
    while (index < tree.length) {
      tree[index] += delta;
      index += index & (-index);
    }
  }  int query(int index) {
    int sum = 0;
    while (index > 0) {
      sum += tree[index];
      index -= index & (-index);
    }
    return sum;
  }
}

---

7. Bloom Filter

Concept

Probabilistic data structure:

• Fast membership test
• Allows false positives
• No false negatives

Used in:

• Databases
• Caching
• Web crawlers

(Not commonly implemented in Flutter, but good to know.)

---

8. Comparison Table

Structure	Best Use Case
Union-Find	Connectivity
Trie	Prefix search
LRU Cache	Caching
Segment Tree	Range queries
Fenwick Tree	Prefix sums
Bloom Filter	Membership test

---

9. Summary

• Advanced structures solve scalability problems
• Often combine multiple basic structures
• Critical for system design interviews
• Appear in real production systems