List: специфичные операции

List - самый популярный из всех типов коллекций в Kotlin. Он предоставляет мощный набор операций благодаря наличию доступа к элементам по индексу.

Получение элементов по индексу

Списки поддерживают все стандартные операции для получения элементов: elementAt(), first(), last() и другие, перечисленные в разделе Выбор одного элемента. Списки характерны тем, что предоставляют доступ к элементам по индексу, поэтому именно по индексу проще всего получить необходимый элемент. Это осуществляется с помощью функции get(), которая принимает индекс в качестве аргумента. Также можно использовать сокращённый синтаксис - [index].

Если размер списка меньше указанного индекса, то будет выброшено исключение. Есть ещё две функции, которые помогут этого избежать:

• getOrElse() - позволяет вам предоставить функцию для вычисления значения по умолчанию. Если по указанному индексу элемент не был найден, то будет возвращён результат вычисления этой функции.
• getOrNull() - возвращает null в качестве значения по умолчанию.

fun main() {
    val numbers = listOf(1, 2, 3, 4)
    println(numbers.get(0)) // 1
    println(numbers[0]) // 1
    //numbers.get(5) // exception!
    println(numbers.getOrNull(5)) // null
    println(numbers.getOrElse(5, {it})) // 5
}

Получение части списка

Помимо обычных операций для Выборки элементов, списки предоставляют функцию subList(), которая возвращает представление указанного диапазона элементов в виде списка. Таким образом, если элемент исходной коллекции будет изменён, то он также изменится и в списке, созданном с помощью функции subList(), и наоборот.

fun main() {
    val numbers = (0..13).toList()
    println(numbers.subList(3, 6)) // [3, 4, 5]
}

Поиск позиции элемента

Линейный поиск

В любом списке вы можете найти позицию элемента с помощью функций indexOf() и lastIndexOf(). Они возвращают первую и последнюю позицию элемента, равного заданному аргументу. Если таких элементов нет, то обе функции возвращают -1.

fun main() {
    val numbers = listOf(1, 2, 3, 4, 2, 5)
    println(numbers.indexOf(2)) // 1
    println(numbers.lastIndexOf(2)) // 4
}

Также существуют две функции, которые принимают предикат и ищут соответствующие ему элементы:

• indexOfFirst() - возвращает индекс первого элемента, соответствующего заданному предикату или -1, если таких элементов нет.
• indexOfLast() - возвращает индекс последнего элемента, соответствующего заданному предикату или -1, если таких элементов нет.

fun main() {
    val numbers = mutableListOf(1, 2, 3, 4)
    println(numbers.indexOfFirst { it > 2}) // 2
    println(numbers.indexOfLast { it % 2 == 1}) // 2
}

Бинарный поиск в отсортированном списке

Ещё один способ поиска элементов в списке – бинарный поиск. Он работает значительно быстрее остальных встроенных функций поиска, но для его использования требуется, чтобы список был отсортирован по возрастанию в соответствии с определённым порядком: естественным или любым другим, указанным в параметре функции. В противном случае результат не будет определён.

Чтобы найти элемент в отсортированном списке, вызовите функцию binarySearch(), передав ей искомое значение в качестве аргумента. Если такой элемент существует, функция вернёт его индекс; в противном случае она вернёт (-insertionPoint - 1), где insertionPoint - это индекс, в который этот элемент должен быть вставлен, чтобы список оставался отсортированным. Если существует более одного элемента с указанным значением, функция может вернуть любой из их индексов.

Вы также можете указать диапазон индексов для поиска: в этом случае функция выполняет поиск только между двумя предоставленными индексами.

fun main() {
    val numbers = mutableListOf("one", "two", "three", "four")
    numbers.sort()
    println(numbers) // [four, one, three, two]
    println(numbers.binarySearch("two")) // 3
    println(numbers.binarySearch("z")) // -5
    println(numbers.binarySearch("two", 0, 2)) // -3
}

Бинарный поиск с Comparator

Если элементы списка не являются Comparable, вы должны предоставить Comparator, который будет использован в бинарном поиске. Список должен быть отсортирован по возрастанию в соответствии с этим Comparator. Давайте посмотрим на пример:

data class Product(val name: String, val price: Double)

fun main() {
    val productList = listOf(
        Product("WebStorm", 49.0),
        Product("AppCode", 99.0),
        Product("DotTrace", 129.0),
        Product("ReSharper", 149.0))

    println(
      productList
        .binarySearch(Product("AppCode", 99.0), compareBy<Product> { it.price }
        .thenBy { it.name }
      )
    ) // 1
}

В данном примере есть:

• список из экземпляров класса Product, которые не являются Comparable.
• Comparator, который определяет порядок: продукт p1 предшествует продукту p2, если цена p1 меньше, чем цена p2. Итак, имея список, отсортированный по возрастанию в соответствии с этим порядком, мы используем binarySearch(), чтобы найти индекс указанного Product.

Пользовательские компараторы также удобны, когда для сортировки списка используется порядок, отличный от естественного, например, без учета регистра для элементов String.

fun main() {
    val colors = listOf("Blue", "green", "ORANGE", "Red", "yellow")
    println(colors.binarySearch("RED", String.CASE_INSENSITIVE_ORDER)) // 3
}

Бинарный поиск с функцией сравнения

Бинарный поиск с функцией сравнения (comparison) позволяет находить элементы без предоставления явных значений для поиска. Вместо этого он принимает элементы функции сравнения, преобразованные в Int, и ищет элемент, для которого функция возвращает ноль. Список должен быть отсортирован по возрастанию в соответствии с порядком, предоставленным функцией; другими словами, возвращаемые функцией значения должны расти от одного элемента списка к следующему.

import kotlin.math.sign

data class Product(val name: String, val price: Double)

fun priceComparison(product: Product, price: Double) = sign(product.price - price).toInt()

fun main() {
    val productList = listOf(
        Product("WebStorm", 49.0),
        Product("AppCode", 99.0),
        Product("DotTrace", 129.0),
        Product("ReSharper", 149.0))

    println(productList.binarySearch { priceComparison(it, 99.0) }) // 1
}

Бинарный поиск как с компаратором, так и с функцией сравнения может выполняться для диапазонов списков.

Операции записи

В дополнение к изменяющим коллекцию операциям, которые описаны в разделе Операции записи коллекций, изменяемые списки поддерживают операции записи, характерные только для списков. Эти операции используют индекс для доступа к элементам, что расширяет возможности для изменения списка.

Добавление элементов

Чтобы добавить элементы в определённую позицию в списке, используйте add() и addAll(), которым в качестве аргумента передайте позицию для вставки элемента. Все элементы, которые идут после указанной позиции, будут смещены вправо.

fun main() {
    val numbers = mutableListOf("one", "five", "six")
    numbers.add(1, "two")
    numbers.addAll(2, listOf("three", "four"))
    println(numbers) // [one, two, three, four, five, six]
}

Обновление элементов

Списки также предоставляют функцию для замены элемента в заданной позиции - set(), у которой есть операторная форма []. set() не меняет индексы других элементов.

fun main() {
    val numbers = mutableListOf("one", "five", "three")
    numbers[1] =  "two"
    println(numbers) // [one, two, three]
}

Функция fill() просто заменяет все элементы коллекции на указанное значение.

fun main() {
    val numbers = mutableListOf(1, 2, 3, 4)
    numbers.fill(3)
    println(numbers) // [3, 3, 3, 3]
}

Удаление элементов

Чтобы удалить элемент из определённой позиции списка, используйте функцию removeAt(), передав ей в качестве аргумента эту позицию. Все индексы элементов, которые идут после удаляемого, будут уменьшены на единицу.

fun main() {
    val numbers = mutableListOf(1, 2, 3, 4, 3)    
    numbers.removeAt(1)
    println(numbers) // [1, 3, 4, 3]
}

Сортировка

В разделе Сортировка коллекций описаны операции, которые возвращают элементы коллекции в определённом порядке. Для изменяемых списков в стандартной библиотеке есть аналогичные функции-расширения, выполняющие сортировку, но вместо возврата нового отсортированного списка они изменяют порядок элементов в исходном списке.

Подобные функции сортировки названы похожими именами, но без суффикса ed/d:

• sort* вместо sorted* в именах всех функций сортировки: sort(), sortDescending(), sortBy() и так далее.
• shuffle() вместо shuffled().
• reverse() вместо reversed().

Функция asReversed(), вызываемая к изменяемому списку, возвращает другой изменяемый список, который является перевёрнутым представлением исходного списка. Вместе с изменением этого представления вы изменяете и исходный список.

В следующем примере показаны функции сортировки для изменяемых списков:

fun main() {
    val numbers = mutableListOf("one", "two", "three", "four")

    numbers.sort()
    println("Sort into ascending: $numbers") // Sort into ascending: [four, one, three, two]
    numbers.sortDescending()
    println("Sort into descending: $numbers") // Sort into descending: [two, three, one, four]

    numbers.sortBy { it.length }
    println("Sort into ascending by length: $numbers") // Sort into ascending by length: [two, one, four, three]
    numbers.sortByDescending { it.last() }
    println("Sort into descending by the last letter: $numbers") // Sort into descending by the last letter: [four, two, one, three]

    numbers.sortWith(compareBy<String> { it.length }.thenBy { it })
    println("Sort by Comparator: $numbers") // Sort by Comparator: [one, two, four, three]

    numbers.shuffle()
    println("Shuffle: $numbers") // Shuffle: [one, two, three, four]

    numbers.reverse()
    println("Reverse: $numbers") // Reverse: [four, three, two, one]
}