Операции со списками

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

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

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

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

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

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

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

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

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

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

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

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

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

fun main() {
//sampleStart
    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 }))
//sampleEnd
}

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

import kotlin.math.sign
//sampleStart
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) })
}
//sampleEnd

Добавление

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

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

Обновление

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

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

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

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

Удаление

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

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

Сортировка

В разделе Порядок элементов в коллекциях мы описываем операции, которые извлекают элементы коллекции в определённом порядке. Для изменяемых списков стандартная библиотека предлагает аналогичные расширяющие функции, которые выполняют те же операции упорядочения «на месте». Когда вы применяете такую операцию к экземпляру списка, она изменяет порядок элементов в этом конкретном экземпляре.

Функции сортировки «на месте» имеют названия, похожие на названия функций, которые применяются к неизменяемым спискам, но без суффикса ed/d:

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

• shuffle() вместо shuffled().

• reverse() вместо reversed().

asReversed(), вызванная на изменяемом списке, возвращает другой изменяемый список, представляющий собой обращённый вид исходного списка. Изменения в этом представлении отражаются в исходном списке. Следующий пример показывает функции сортировки для изменяемых списков:

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

    numbers.sort()
    println("Sort into ascending: $numbers")
    numbers.sortDescending()
    println("Sort into descending: $numbers")

    numbers.sortBy { it.length }
    println("Sort into ascending by length: $numbers")
    numbers.sortByDescending { it.last() }
    println("Sort into descending by the last letter: $numbers")
    
    numbers.sortWith(compareBy<String> { it.length }.thenBy { it })
    println("Sort by Comparator: $numbers")

    numbers.shuffle()
    println("Shuffle: $numbers")

    numbers.reverse()
    println("Reverse: $numbers")
//sampleEnd
}