Операции с массивами: доступ, поиск, вставка, удаление и сортировка

Массив хранит упорядоченную последовательность элементов и позволяет обращаться к ним по индексу. С массивами выполняют создание, чтение, изменение, обход, поиск, вставку,…

Массив хранит упорядоченную последовательность элементов и позволяет обращаться к ним по индексу. С массивами выполняют создание, чтение, изменение, обход, поиск, вставку, удаление, сортировку, копирование и агрегирование.

Перед выбором операции нужно понять, какая структура используется:

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

JavaScript Array, Python list и Java ArrayList — динамические последовательности. Java int[] и Go [N]int имеют фиксированную длину. Go []int — срез: его длина меняется через append, но он может ссылаться на общий базовый массив.

Создание массива

Массив создают пустым, с заданным размером или сразу с начальными значениями. В Go и Java синтаксис фиксированной и динамической структуры различается.

const numbers = [10, 20, 30];

const numbers: number[] = [10, 20, 30];

package main
func main() {
  fixed := [3]int{10, 20, 30}
  numbers := []int{10, 20, 30}

  _, _ = fixed, numbers
}

import java.util.ArrayList;
import java.util.List;

public class Example {
  public static void main(String[] args) {
    int[] fixed = {10, 20, 30};
    List<Integer> numbers = new ArrayList<>(List.of(10, 20, 30));
  }
}

numbers = [10, 20, 30]

Доступ по индексу

Элемент массива получают по его индексу. Во многих языках индексация начинается с нуля.

const first = numbers[0];

const first = numbers[0];

package main
func main() {
  numbers := []int{10, 20, 30}
  first := numbers[0]

  _ = first
}

public class Example {
  public static void main(String[] args) {
    int[] numbers = {10, 20, 30};
    int first = numbers[0];
  }
}

first = numbers[0]

Доступ по индексу обычно выполняется за O(1): адрес элемента вычисляется по началу массива, индексу и размеру элемента. Выход за границы обрабатывается по-разному: Java, Go и Python сообщат об ошибке, а JavaScript при чтении отсутствующего индекса вернет undefined. Проверку границ нельзя пропускать только потому, что синтаксис разрешает обращение.

Изменение элемента

Если массив изменяемый, элемент можно заменить.

numbers[1] = 25;

numbers[1] = 25;

package main
func main() {
  numbers := []int{10, 20, 30}
  numbers[1] = 25
}

public class Example {
  public static void main(String[] args) {
    int[] numbers = {10, 20, 30};
    numbers[1] = 25;
  }
}

numbers[1] = 25

const в JavaScript запрещает присвоить переменной другой массив, но не делает элементы неизменяемыми. Для неизменяемого обновления создают копию.

Обход массива

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

for (const number of numbers) {
  console.log(number);
}

for (const number of numbers) {
  console.log(number);
}

package main
import "fmt"
func main() {
  numbers := []int{10, 25, 30}

  for _, number := range numbers {
    fmt.Println(number)
  }
}

public class Example {
  public static void main(String[] args) {
    int[] numbers = {10, 25, 30};

    for (int number : numbers) {
      System.out.println(number);
    }
  }
}

for number in numbers:
  print(number)

Обход всего массива имеет сложность O(n).

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

Поиск может быть линейным или более эффективным, если массив отсортирован.

Линейный поиск просматривает элементы по порядку.

const index = numbers.findIndex((number) => number === 25);

const index = numbers.findIndex((number) => number === 25);

package main
func main() {
  numbers := []int{10, 25, 30}
  index := -1

  for currentIndex, number := range numbers {
    if number == 25 {
      index = currentIndex
      break
    }
  }

  _ = index
}

public class Example {
  public static void main(String[] args) {
    int[] numbers = {10, 25, 30};
    int index = -1;

    for (int currentIndex = 0; currentIndex < numbers.length; currentIndex++) {
      if (numbers[currentIndex] == 25) {
        index = currentIndex;
        break;
      }
    }
  }
}

index = next((index for index, number in enumerate(numbers) if number == 25), -1)

В худшем случае линейный поиск работает за O(n).

Если данные отсортированы и структура поддерживает доступ по индексу, можно применять двоичный поиск: сравнивать искомое значение со средним элементом и каждый раз отбрасывать половину диапазона. Поиск занимает O(log n), но предварительная сортировка обычно стоит O(n log n), а вставка нового элемента в отсортированный массив по-прежнему требует сдвига за O(n).

Для частых проверок «есть ли значение» без обращения по индексу лучше рассмотреть множество или хеш-таблицу.

Вставка

У фиксированного массива операции вставки нет: нужно создать новый массив большего размера и скопировать элементы. Динамическая структура умеет увеличиваться сама.

В динамический массив можно добавить элемент в конец.

numbers.push(40);

numbers.push(40);

package main
func main() {
  numbers := []int{10, 20, 30}
  numbers = append(numbers, 40)

  numbers = append(numbers, 0)
  copy(numbers[2:], numbers[1:])
  numbers[1] = 15
}

import java.util.ArrayList;
import java.util.List;

public class Example {
  public static void main(String[] args) {
    List<Integer> numbers = new ArrayList<>(List.of(10, 20, 30));
    numbers.add(40);
    numbers.add(1, 15);
  }
}

numbers.append(40)
numbers.insert(1, 15)

Добавление в конец динамического массива обычно имеет амортизированную сложность O(1). Иногда вместимость заканчивается, структура выделяет больший участок памяти и копирует туда все элементы — одна такая операция стоит O(n), но происходит не при каждом добавлении.

Вставка в начало или середину требует сдвинуть элементы справа и работает за O(n).

Удаление

Удаление из конца обычно проще, чем удаление из середины.

numbers.pop();
numbers.splice(1, 1);

numbers.pop();
numbers.splice(1, 1);

package main
func main() {
  numbers := []int{10, 20, 30, 40}

  last := numbers[len(numbers)-1]
  numbers = numbers[:len(numbers)-1]

  index := 1
  copy(numbers[index:], numbers[index+1:])
  numbers = numbers[:len(numbers)-1]

  _ = last
}

import java.util.ArrayList;
import java.util.List;

public class Example {
  public static void main(String[] args) {
    List<Integer> numbers = new ArrayList<>(List.of(10, 20, 30));
    numbers.remove(numbers.size() - 1);
    numbers.remove(0);
  }
}

numbers.pop()
del numbers[1]

После удаления из середины элементы справа сдвигаются влево, поэтому операция имеет сложность O(n). В Go при удалении элементов-ссылок из долгоживущего среза иногда дополнительно обнуляют освободившуюся ячейку базового массива, чтобы сборщик мусора мог освободить объект.

Сортировка

Сортировка упорядочивает элементы по заданному правилу.

numbers.sort((a, b) => a - b);

numbers.sort((a, b) => a - b);

package main
import "sort"
func main() {
  numbers := []int{30, 10, 20}
  sort.Ints(numbers)
}

public class Example {
  public static void main(String[] args) {
    int[] numbers = {30, 10, 20};
    java.util.Arrays.sort(numbers);
  }
}

numbers.sort()

В учебных курсах часто изучают сортировку пузырьком, выбором и вставками, а в практических библиотеках используются более эффективные алгоритмы.

Методы выше сортируют исходную структуру на месте. В JavaScript компаратор (a, b) => a - b обязателен для чисел: без него sort() по умолчанию сравнивает строковые представления, и число 10 может оказаться перед 2.

Копирование и объединение

Массивы можно копировать, объединять, получать подмассивы.

const copy = [...numbers];
const merged = [...numbers, 50, 60];
const part = numbers.slice(0, 2);

const copy = [...numbers];
const merged = [...numbers, 50, 60];
const part = numbers.slice(0, 2);

package main
func main() {
  numbers := []int{10, 20, 30}
  copied := append([]int(nil), numbers...)
  merged := append(append([]int(nil), numbers...), 50, 60)
  part := numbers[0:2]

  _, _, _ = copied, merged, part
}

public class Example {
  public static void main(String[] args) {
    int[] numbers = {10, 20, 30};
    int[] copied = java.util.Arrays.copyOf(numbers, numbers.length);
    int[] merged = java.util.stream.IntStream.concat(
      java.util.Arrays.stream(numbers),
      java.util.stream.IntStream.of(50, 60)
    ).toArray();
    int[] part = java.util.Arrays.copyOfRange(numbers, 0, 2);
  }
}

copy = numbers.copy()
merged = numbers + [50, 60]
part = numbers[0:2]

Эти копии являются поверхностными: новый контейнер создается, но вложенные изменяемые объекты могут остаться общими. В Go выражение numbers[0:2] вообще создает новый срез того же базового массива; изменение элемента part может изменить numbers. Для независимой копии используют append([]int(nil), numbers...) или copy.

Преобразование и фильтрация

Динамические последовательности часто преобразуют без ручного управления индексами:

const numbers: number[] = [10, 20, 30, 40];
const doubled = numbers.map((number) => number * 2);
const greaterThanTwenty = numbers.filter((number) => number > 20);

console.log(doubled); // [20, 40, 60, 80]
console.log(greaterThanTwenty); // [30, 40]

В Python для этого используют списковые включения, в Java — Stream API, а в Go обычно пишут явный цикл с заранее выделенным результирующим срезом. Обход всех элементов требует O(n).

Агрегирование

Часто нужно найти сумму, максимум, минимум, среднее значение.

const sum = numbers.reduce((total, number) => total + number, 0);

const sum = numbers.reduce((total, number) => total + number, 0);

package main
func main() {
  numbers := []int{10, 20, 30}
  sum := 0

  for _, number := range numbers {
    sum += number
  }

  _ = sum
}

public class Example {
  public static void main(String[] args) {
    int[] numbers = {10, 20, 30};
    int sum = java.util.Arrays.stream(numbers).sum();
  }
}

total = sum(numbers)

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

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

Типичные ошибки при работе с массивами

• выход за допустимый диапазон индексов;
• смешение индекса и значения, например удаление не того элемента в перегруженном методе Java;
• изменение массива во время обхода без учета сдвига индексов;
• ожидание, что срез или поверхностная копия полностью независимы от исходных данных;
• использование линейного поиска в большом массиве при каждой итерации;
• числовая сортировка JavaScript без компаратора;
• вставка в фиксированный массив как в динамический список;
• удержание слишком большого базового массива маленьким срезом.

Вывод

Основные операции с массивами — создание, доступ, изменение, обход, поиск, вставка, удаление, сортировка, копирование, преобразование и вычисление агрегатов. Массив особенно удобен для быстрого доступа по индексу. При вставке, удалении и изменении размера нужно учитывать, является ли структура фиксированным массивом, динамическим массивом или срезом, а также понимать стоимость перемещения элементов.