Введение

Сегодня мы исследуем разницу между List и LinkedList, а также такой важный термин, как амортизированное время. Но перед тем, как глубоко погрузиться в эту тему, давайте кратко вспомним три базовые структуры данных: статический/динамический массив и список.

Статический массив

Статический массив — это массив, размер которого определяется при его создании и который не может быть изменен в процессе выполнения программы. Это означает, что количество элементов в статическом массиве фиксировано, и если вам потребуется хранить больше элементов, чем было выделено изначально, вам придется создавать новый массив большего размера и копировать в него элементы из старого массива. Если вы знаете точно, сколько у вас элементов, и их число ТОЧНО не будет меняться, то можете смело его использовать, ведь очень быстрый поиск, а следовательно поменять значения тоже…

НО

У вас миллион элементов. И вдруг вам нужно добавить еще один, что произойдет?

  1. поиск в памяти на миллион+1 ячеек
  2. ее выделение
  3. перенос всего миллиона значений в новую память
  4. наконец добавление нашего нового элемента

Как же нам облегчить жизнь?…

Динамический массив

Модификация статического, вместо того чтобы при добавлении нового значения мы выделяли на N+1 памяти больше, мы создаем на N*M, иначе, задаем правило.

что произойдет в том же случае что мы описали выше? Тоже самое, только памяти выделится на(допустим M = 2) миллион больше, таким образом при частых добавлениях элементов у нас есть зарезервированная для этого память. С удалением та же история, при определенном пороге выделяется новая память на N*0.(P) меньше. Классический случай, когда память мы увеличиваем в два раза, а память уменьшаем в 0.75

Список

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

Так в чем разница между LinkedList и просто List?

Конечно, мы должны рассмотреть дефолтную реализацию, а где ее можно посмотреть? Ну, слава опенсорсу, есть решение! Вы можете найти исходный код и изучить реализацию этих структур данных на GitHub репозитории Microsoft.

List

LinkedList

Итак, посмотрев на поля классов, мы с вами узнали, что List - это динамический массив, в то время как Linked List - связный список!

Частые добавления/удаления и редкий поиск? - пользуйтесь LinkedList. Часто ищете и редко добавляете элементы? - List.

И казалось бы, сложность поиска для LinkedList - O(N), а добавление/удаление O(1), тогда для List поиск O(1), а добавление/удаление O(N)? Нуу, не совсем… O(1*)

Амортизированное время для динамического массива

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

Доказательство вы можете почитать здесь

Вывод

Конечно вы можете следовать рекомендации что я указывал, однако не все так просто в рамках производительного кода. Однако я могу предложить вам интересную задачу, которая может вас немного подготовить к выбору между двумя нашими вариантами :)

Итак, вспомнили немного базовые структуры, узнали, где смотреть реализации структур от самих разработчиков, что такое амортизированное время и что в рамках производительности может быть не все так однозначно.

Надеюсь пост, как и задача , которую вы решили, был интересен и познавателен для вас.

А на сегодня все, до новых встреч!