Обхід, черги та сортування

Безпечний обхід і зміна

Цикл for (item in collection) використовує ітератор. withIndex() додає індекс і значення, а indices потрібний, коли позиція використовується для запису. Не варто багаторазово звертатися до list[index], якщо конкретна реалізація списку не обіцяє ефективний випадковий доступ.

Структурна зміна колекції під час звичайного обходу може спричинити ConcurrentModificationException. Назва не означає, що обов’язково працювали два потоки: достатньо неправильного видалення в одному циклі. Це діагностика помилки, а не механізм синхронізації.

fun main() {
    val numbers = mutableListOf(1, 2, 3, 4)
    val iterator = numbers.iterator()
    while (iterator.hasNext()) {
        if (iterator.next() % 2 == 0) iterator.remove()
    }
    println(numbers)
}

MutableIterator.remove() видаляє елемент, щойно повернений next(), і узгоджує стан цього ітератора. Не викликайте remove двічі після одного next. Інший безпечний підхід – сформувати нову колекцію відфільтрованих елементів; його вивчаємо в темі 11.

ArrayDeque як стек і черга

Двостороння черга ArrayDeque<T> підтримує вставлення і вилучення з обох кінців. Для FIFO додають у кінець і забирають із початку; для LIFO додають і забирають із того самого кінця. Назви операцій явно показують дисципліну обслуговування.

fun main() {
    val queue = ArrayDeque<String>()
    queue.addLast("A")
    queue.addLast("B")
    println(queue.removeFirst())
    println(queue.removeFirstOrNull())
    println(queue.removeFirstOrNull())
    val stack = ArrayDeque<Int>()
    stack.addLast(10)
    stack.addLast(20)
    println(stack.removeLast())
}

Операції з суфіксом OrNull зручні для порожньої структури. Якщо колекція допускає nullable-елементи, знову виникає неоднозначність між відсутністю й збереженим null; її розв’язують контрактом. Для черги пріоритетів JVM надає java.util.PriorityQueue. Її poll повертає мінімальний за компаратором елемент, але звичайний ітератор не обіцяє відсортованого порядку всіх елементів.

Сортування та вибір реалізації

sorted() створює новий список природного порядку; sortedDescending() змінює напрям. Для змінюваного списку sort() змінює поточний об’єкт. Comparable задає природний порядок класу, а Comparator – окреме правило. Вираз compareBy<Person> { it.name } створює компаратор за ключем; докладне складання правил буде в наступній темі.

Структура	Типова вартість	Коли доречна
ArrayList	Індекс O(1), пошук O(n)	Позиційний список
HashSet / HashMap	Очікувано O(1)	Належність, ключі
TreeMap / відсортована множина	O(log n)	Упорядковані ключі
ArrayDeque	Кінці амортизовано O(1)	Черга або стек
PriorityQueue	Вставлення/вилучення O(log n)	Мінімум за пріоритетом

Оцінки залежать від операції, реалізації та властивостей ключів. Вставлення в середину ArrayList потребує зміщення елементів, тому має O(n), хоча доступ за індексом сталий. Додавання в кінець амортизовано стале: інколи внутрішній масив збільшується з копіюванням. Хеш-таблиця має очікувану, а не безумовну гарантію O(1).

При взаємодії з Java Kotlin може бачити платформні типи. Java-код здатний повернути null або змінити колекцію, яку Kotlin-код сприймає через інтерфейс читання. На межі бібліотеки перевіряйте контракт null і власності. Приведення до MutableList не є безпечним універсальним способом «розблокувати» будь-який список.