Как происходит удаление или добавление элементов в массив и список?

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

В списках (например, в ArrayList в Java или list в Python) удаление/добавление элементов может быть более эффективным.

• Для списков на основе динамических массивов (например, ArrayList):

  • Добавление в конец: обычно быстро (амортизированная O(1)). Если массив заполнен, происходит пересоздание и копирование (O(n)).
  • Добавление в середину/начало: требует сдвига всех последующих элементов (O(n)).
  • Удаление по индексу: требует сдвига всех последующих элементов (O(n)).
  • Удаление по значению: требует поиска элемента (O(n)) и сдвига последующих (O(n)).

• Для списков на основе связных структур (например, LinkedList в Java или связанный список в Python):

  • Добавление/удаление в начале/конце: очень быстро (O(1)), так как требуется только изменить ссылки.
  • Добавление/удаление в середине: требует поиска позиции (O(n)), затем изменение ссылок (O(1)).

В целом, удаление/добавление в массивах всегда O(n), тогда как в списках зависит от конкретной реализации и позиции операции.

Пример на Python:

# Массив (имитация с использованием list)
arr = [1, 2, 3]
# Добавление элемента (создается новый list)
new_arr_add = arr[:1] + [99] + arr[1:]
# Удаление элемента (создается новый list)
new_arr_remove = arr[:1] + arr[2:]


# Список (list в Python является динамическим массивом)
my_list = [1, 2, 3, 4, 5]

# Добавление в конец (обычно эффективно)
my_list.append(6)
#print(my_list) # [1, 2, 3, 4, 5, 6]

# Добавление в середину (дорого)
my_list.insert(2, 99)
#print(my_list) # [1, 2, 99, 3, 4, 5, 6]

# Удаление по индексу (дорого)
my_list.pop(3) # Удалит 3 (бывший 4)
#print(my_list) # [1, 2, 99, 4, 5, 6]

# Удаление по значению (дорого)
my_list.remove(99)
#print(my_list) # [1, 2, 4, 5, 6]

Пример на Java (для сравнения int[] и ArrayList):

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

class Example {
    public static void main(String[] args) {
        // Массив
        int[] arr = {1, 2, 3};
        // Добавление элемента (требует создания нового массива)
        int[] newArrAdd = new int[arr.length + 1];
        System.arraycopy(arr, 0, newArrAdd, 0, 1);
        newArrAdd[1] = 99;
        System.arraycopy(arr, 1, newArrAdd, 2, arr.length - 1);
        //System.out.println(Arrays.toString(newArrAdd)); // [1, 99, 2, 3]

        // Удаление элемента (требует создания нового массива)
        int[] newArrRemove = new int[arr.length - 1];
        System.arraycopy(arr, 0, newArrRemove, 0, 1);
        System.arraycopy(arr, 2, newArrRemove, 1, arr.length - 2);
        //System.out.println(Arrays.toString(newArrRemove)); // [1, 3]


        // Список (ArrayList)
        List<Integer> myArrayList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));

        // Добавление в конец (обычно эффективно)
        myArrayList.add(6);
        //System.out.println(myArrayList); // [1, 2, 3, 4, 5, 6]

        // Добавление в середину (дорого)
        myArrayList.add(2, 99);
        //System.out.println(myArrayList); // [1, 2, 99, 3, 4, 5, 6]

        // Удаление по индексу (дорого)
        myArrayList.remove(3); // Удалит 3 (бывший 4)
        //System.out.println(myArrayList); // [1, 2, 99, 4, 5, 6]

        // Удаление по значению (дорого)
        myArrayList.remove(Integer.valueOf(99)); // Удалит 99
        //System.out.println(myArrayList); // [1, 2, 4, 5, 6]
    }
}