Какие знаешь структуры данных?

Структуры данных в Android разработке

Знание структур данных критически важно для написания эффективного кода. Давайте разберём основные структуры которые используются в Android.

Линейные структуры

Array - фиксированный размер, O(1) доступ по индексу

val numbers = intArrayOf(1, 2, 3, 4, 5)
println(numbers[2])  // O(1)

ArrayList - динамический массив

val list = mutableListOf<String>()
list.add("item")  // O(1) в конце
list.add(0, "first")  // O(n) в начале

LinkedList - двусвязный список

val linkedList = LinkedList<Int>()
linkedList.addFirst(1)  // O(1)
linkedList.addLast(2)   // O(1)
linkedList[0]  // O(n) доступ по индексу

Структуры поиска

HashMap - key-value хранилище O(1)

val map = mutableMapOf<String, Int>()
map["age"] = 25
println(map["age"])  // O(1)

TreeMap - сортированный map O(log n)

val sorted = sortedMapOf<String, Int>()
sorted["z"] = 1
sorted["a"] = 2
// Итерация в отсортированном порядке

HashSet - уникальные элементы O(1)

val set = mutableSetOf<String>()
set.add("item")
if ("item" in set) {
    println("Found")
}

TreeSet - сортированный set O(log n)

val sorted = sortedSetOf<Int>()
sorted.addAll(listOf(3, 1, 2))
// Итерирует в отсортированном порядке

Очереди

Queue - FIFO (First In First Out)

val queue: Queue<Int> = LinkedList()
queue.offer(1)    // Добавить
queue.offer(2)
println(queue.poll())  // 1 (первый добавленный)

Deque - двусторонняя очередь

val deque: Deque<Int> = ArrayDeque()
deque.addFirst(1)
deque.addLast(2)
deque.removeFirst()   // O(1)
deque.removeLast()    // O(1)

PriorityQueue - приоритетная очередь O(log n)

val pq = PriorityQueue<Int>()
pq.offer(3)
pq.offer(1)
pq.offer(2)
println(pq.poll())  // 1 (наименьший приоритет)

Стеки

Stack - LIFO (Last In First Out)

val stack = Stack<String>()
stack.push("first")
stack.push("second")
println(stack.pop())  // "second"

Деревья

Binary Search Tree - O(log n) поиск в среднем

class Node(val value: Int) {
    var left: Node? = null
    var right: Node? = null
}

fun search(node: Node?, target: Int): Node? {
    return when {
        node == null -> null
        node.value == target -> node
        target < node.value -> search(node.left, target)
        else -> search(node.right, target)
    }
}

Balanced Trees (AVL, Red-Black) - O(log n) гарантировано

// TreeMap и TreeSet используют красно-чёрные деревья
val map = sortedMapOf<String, String>()

Графы

Adjacency List - для поиска в ширину

val graph = mapOf(
    "A" to listOf("B", "C"),
    "B" to listOf("D"),
    "C" to listOf("D")
)

fun bfs(start: String) {
    val queue = LinkedList<String>()
    val visited = mutableSetOf<String>()
    queue.offer(start)
    visited.add(start)
    
    while (queue.isNotEmpty()) {
        val node = queue.poll()
        println(node)
        
        for (neighbor in graph[node] ?: emptyList()) {
            if (neighbor !in visited) {
                queue.offer(neighbor)
                visited.add(neighbor)
            }
        }
    }
}

Adjacency Matrix - для плотных графов

val graph = arrayOf(
    intArrayOf(0, 1, 1),  // A -> B, A -> C
    intArrayOf(0, 0, 1),  // B -> C
    intArrayOf(0, 0, 0)   // C
)

Android специфичные

SparseArray - вместо HashMap<Int, T>

val sparse = SparseArray<String>()
sparse.put(1, "one")
sparse.put(2, "two")
println(sparse[1])  // "one"

LongSparseArray - для key типа Long

val longSparse = LongSparseArray<String>()
longSparse.put(1L, "one")

ArrayMap - более эффективный HashMap для малых размеров

val map = ArrayMap<String, String>()
map["key"] = "value"

Сложность операций

Когда что использовать в Android

Fragment данные:

// Используй ArrayList для большинства случаев
val items = mutableListOf<Item>()
recyclerAdapter.submitList(items)

Кэширование:

// HashMap для быстрого доступа
val cache = mutableMapOf<String, UserData>()

Уникальные значения:

val selectedIds = mutableSetOf<Int>()
if (id in selectedIds) {
    // O(1) проверка
}

Приоритеты:

// PriorityQueue для очередей задач
val taskQueue = PriorityQueue<Task> { t1, t2 ->
    t1.priority.compareTo(t2.priority)
}

Выводы

1. ArrayList - выбор по умолчанию для коллекций
2. HashMap - для быстрого key-value поиска
3. HashSet - для уникальных элементов
4. SparseArray - вместо HashMap в Android для int ключей
5. Знай сложность - O(1), O(log n), O(n) операций
6. Выбирай по требованиям - скорость vs память vs простота
7. Профилируй - не гадай, измеряй производительность

Правильный выбор структуры данных может дать 10x улучшение производительности.