Расскажите о таких структурах данных, как List, Set, Map?android-13

1. List

Особенности:

  • Упорядоченная коллекция элементов
  • Допускает дубликаты
  • Доступ по индексу
  • Может быть изменяемым (Mutable) и неизменяемым

Основные реализации в Kotlin/Java:

// ArrayList - основан на массиве, быстрый доступ по индексу O(1)
val arrayList = ArrayList<String>()
arrayList.add("Android")
arrayList.add("Kotlin")

// LinkedList - основан на связанных узлах, быстрые вставки/удаления O(1)
val linkedList = LinkedList<String>()
linkedList.add("Android")
linkedList.addFirst("Kotlin") // Добавление в начало

Применение в Android:

  • Отображение элементов в RecyclerView
  • Хранение последовательностей данных
  • Передача упорядоченных параметров

2. Set

Особенности:

  • Неупорядоченная коллекция (кроме LinkedHashSet)
  • Не содержит дубликатов
  • Оптимизирован для проверки принадлежности (contains)

Основные реализации:

// HashSet - хранение в хэш-таблице, O(1) для операций
val hashSet = HashSet<String>()
hashSet.add("Android")
hashSet.add("Kotlin")

// TreeSet - сортированное множество, O(log n) операций
val treeSet = TreeSet<String>()
treeSet.add("Android")
treeSet.add("Kotlin") // Автоматическая сортировка

// LinkedHashSet - сохраняет порядок вставки
val linkedHashSet = LinkedHashSet<String>()
linkedHashSet.add("Android")
linkedHashSet.add("Kotlin")

Применение в Android:

  • Удаление дубликатов из коллекции
  • Проверка уникальности элементов
  • Хранение тегов или категорий

3. Map

Особенности:

  • Пары ключ-значение
  • Ключи уникальны
  • Оптимизирован для поиска по ключу

Основные реализации:

// HashMap - хэш-таблица, O(1) для операций
val hashMap = HashMap<String, Int>()
hashMap["Android"] = 1
hashMap["Kotlin"] = 2

// TreeMap - сортированная по ключам, O(log n)
val treeMap = TreeMap<String, Int>()
treeMap["Android"] = 1
treeMap["Kotlin"] = 2 // Автоматическая сортировка по ключам

// LinkedHashMap - сохраняет порядок вставки
val linkedHashMap = LinkedHashMap<String, Int>()
linkedHashMap["Android"] = 1
linkedHashMap["Kotlin"] = 2

Применение в Android:

  • Кэширование данных
  • Хранение конфигураций
  • Передача данных между компонентами (Bundle)
  • SharedPreferences реализован как Map

Сравнение производительности

Операция | ArrayList | LinkedList | HashSet | TreeSet | HashMap | TreeMap --- | --- | --- | --- | --- | --- | --- Добавление | O(1)* | O(1) | O(1) | O(log n) | O(1) | O(log n) Поиск | O(1) | O(n) | O(1) | O(log n) | O(1) | O(log n) Удаление | O(n) | O(1) | O(1) | O(log n) | O(1) | O(log n)

*O(n) при необходимости расширения массива

Kotlin-специфика

// Неизменяемые коллекции
val immutableList = listOf("Android", "Kotlin")
val immutableSet = setOf("Android", "Kotlin")
val immutableMap = mapOf("Android" to 1, "Kotlin" to 2)

// Изменяемые коллекции
val mutableList = mutableListOf("Android", "Kotlin")
val mutableSet = mutableSetOf("Android", "Kotlin")
val mutableMap = mutableMapOf("Android" to 1, "Kotlin" to 2)

Рекомендации для Android

  1. Выбор структуры:

    • Нужен порядок и индексы → List
    • Нужна уникальность → Set
    • Нужны пары ключ-значение → Map

  2. Потокобезопасность:

    • Для многопоточности используйте ConcurrentHashMap, CopyOnWriteArrayList

  3. Производительность:

    • Для частых вставок/удалений в середине → LinkedList
    • Для частых поисков → HashSet/HashMap

  4. Память:

    • SparseArray (для примитивных ключей) экономит память по сравнению с HashMap

Резюмируем

  1. List - для упорядоченных данных с возможными дубликатами
  2. Set - для уникальных элементов с быстрой проверкой принадлежности
  3. Map - для хранения пар ключ-значение с быстрым поиском по ключу
  4. В Android предпочитайте неизменяемые коллекции там, где возможно
  5. Выбор конкретной реализации зависит от:
    • Требований к порядку элементов
    • Необходимых операций и их частоты
    • Потокобезопасности
    • Использования памяти
  6. Kotlin предоставляет удобные функции-расширения для всех типов коллекций

Вопросы

Собеседования