Списки

6.1. Списки

Список, известный также как последовательность, является контейнером, хранящим элементы в некотором порядке, обычно в порядке их вставки. Математически он представляет всюду определенную функцию, отображающую целочисленный интервал 1.. count в множество G. Это напоминает массивы, но разница в том, что count может свободно изменяться при вставке новых элементов.

Рисунок показывает список, составленный из пяти элементов. Стрелка просто показывает, что порядок имеет значение. Те же элементы, но организованные в другом порядке, составляют другой список.

Возможны различные реализации списков. В EiffelBase они поддерживаются такими классами, как LINKED_LIST, TWO_WAY_LIST, ARRAYED_LIST, MULTI_ARRAYED_LIST. В данном разделе описываются свойства, общие для всех этих вариантов, заданные в классе LIST. Более подробно будет рассмотрен важный вариант связного списка, а затем будет дан обзор других вариантов. Реализация не будет обсуждаться во всех деталях, но примеры реализации и базисные идеи будут рассмотрены. Для получения полной картины следует обратиться к библиотеке классов EiffelBase и проанализировать соответствующие тексты.

Классы, задающие списки, рассматривают список не просто как коллекцию элементов, но как машину, которая в любой точке своего существования имеет состояние, характеризуемое курсором:

Это не новое понятие. Когда мы рассматривали линии метро как список станций, мы уже встречались с курсором.

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

Запросы, связанные с курсором

Мы должны позволять курсору списка, показанному на последнем рисунке, занимать позиции из расширенного интервала 0.. count + 1, а не из интервала 1.. count, где находятся элементы списка. Курсор может находиться левее первого элемента и правее последнего элемента списка. В полезности такого представления легко убедиться. Позицию курсора дает запрос:

index: INTEGER
          — Текущая позиция курсора.
        

Предложения, задающие инвариант, выглядят так:

non_negative_index: index >= 0
index_small_enough: index <= count + 1
        

Для характеристики двух экстремальных случаев позиции курсора введены два запроса:

before: BOOLEAN
            — Правда, что слева от курсора нет правильной позиции?
after: BOOLEAN
            — Правда, что справа от курсора нет правильной позиции?
        

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

Если в текущем состоянии курсор списка находится в позиции before или after, то мы говорим, что он "off":

off: BOOLEAN
            — Верно ли, что курсор вне списка?
        ensure
            definition: Result = (after or before)
        

Следующие предложения инварианта выражают свойства этих запросов (возможны также и соответствующие постусловия):

before_definition: before = (index = 0)
after_definition: after = (index = count + 1)
off_definition: off = (index = 0 or index = count + 1)
        

Другие запросы о курсоре:

is_first: BOOLEAN
                — Задает ли курсор первый элемент?
        ensure
                valid_position: Result implies (not is_empty)
is_last: BOOLEAN
                — Задает ли курсор последний элемент?
        ensure
                valid_position: Result implies (not is_empty)
        

Еще один важный запрос:

is_empty
            — Пуст ли список?)
        

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

В этом случае count равно нулю и максимальная позиция index, удовлетворяющая инварианту, count + 1, равна 1. В таком пустом списке курсор может быть либо в позиции 0, либо в позиции 1. В любом случае off будет иметь место, что следует из предложения инварианта:

empty_constraint: is_empty implies off
        

Заметьте повторяющееся накопление предложений инварианта, позволяющее выразить шаг за шагом наше понимание используемых структур объектов.

Почувствуй методологию: использование инвариантов

Для получения доступа к элементу в позиции курсора

используйте запрос

item: G
            — Элемент в позиции курсора.
        require
            not_off: not off
        

Этот запрос возвращает результат типа G, родовой параметр классов, задающих списки (LIST [G], LINKED_LIST [G] и т.д.). Обратите внимание на предусловие: в состоянии off (пустой список) нет текущего элемента.

Перемещение курсора

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

start
            — Переместить курсор в первую позицию
            — (не выполняется для пустого списка)
      ensure
            at_first: (not is_empty) implies is_first
finish
            — Переместить курсор в последнюю позицию
            — (не выполняется для пустого списка)
      ensure
            at_last: (not is_empty) implies is_last
        

Вызов start означает истинность is-first, а вызов finish означает истинность is-last. Для пустых списков это не справедливо, что отражено в постусловии. Курсор можно также перемещать на одну позицию вправо и влево:

forth
            — Переместить курсор в следующую позицию.
      require
            not_after: not after
      ensure
            moved_forth: index = old index + 1
back
            — Переместить курсор в предыдущую позицию.
      require
            not_before: not before
      ensure
            moved_back: index = old index – 1
        

Предусловия гарантируют, что индекс остается в границах, заданных предыдущими предложениями инварианта: non_negative_index и index_small_enough. Курсор можно установить в заданную позицию:

go_i_th (i: INTEGER)
            — Переместить курсор в i-ю позицию.
      require
            valid_cursor_position: i >= 0 and i <= count + 1
      ensure
            position_expected: index = i
        

Итерирование списка

Часто приходится применять одну и ту же операцию ко всем элементам списка. Предположим, что операция задается методом:

your_operation (x: G)
        

С этой ситуацией мы уже встречались при рассмотрении линий метро – общую форму задает цикл:

from
    your_list.start
until
    your_list.after
loop
    your_operation (your_list.item)
    your_list.forth
variant
    your_list.count – your_list.index + 1
end
        

Здесь операция применяется к некоторому существующему в вашей программе списку your_list. Эта же схема будет использована и в классах, задающих списки, для прохода по текущему списку, но в этом случае вызовы будут неквалифицированными – просто start, after, forth без your_list. Примеры скоро появятся в методах search и has, где разыскиваются нужные элементы списка.

Существуют вариации этой схемы, например, операция применятся к элементам списка, пока не встретится элемент, удовлетворяющий некоторому условию:

from
    your_list.start
until
    your_list.after or else your_condition (your_list.item)
loop
    your_operation (your_list.item)
    your_list.forth
variant
    your_list.count – your_list.index + 1
end
        

Такие схемы являются примером итерирования структуры данных.

Определение: итерирование

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

Примером реализации, использующей механизм итераций, который разделяется всеми классами, задающими списки, является процедура search, осуществляющая поиск элемента в списке. Ее текст выглядит так:

search (v: G)
        —Если курсор установлен в позиции before и список не пуст,
        — то курсор передвигается в начало списка.
        — При поиске курсор устанавливается на первом элементе, совпадающем с v.
        — Если такового нет, то курсор переходит в позицию after.
        do
            from
                if before and not is_empty then
                    forth
                end
            until
                    after or else item = v
            loop
                forth
            end
        end
        

Этот метод является командой, перемещающей курсор:

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

has (v: G)
                — Содержит ли структура вхождение v?
        local
            original_index: INTEGER
        do
            original_index:= index
            start
            search (v)
            Result:= not after
            go_i_th (original_index)
        end
        

Будучи запросом, has должна оставлять структуру в состоянии, предшествующем запросу. Поэтому здесь вводится локальная переменная original_index, запоминающая начальную позицию курсора и восстанавливающую ее в конце работы, благодаря методу go_i_th.

Как search, так и has требуют О(count) времени как в среднем, так и в максимуме.

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

В конце этой лекции мы вернемся к концепциям итерации и получим первое представление об общих механизмах, позволяющих применять стандартный механизм итерирования вместо того, чтобы каждый раз задавать явный цикл с start, forth, item и after.

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

Для добавления элемента в список – в его начало, конец или в позицию курсора – можно использовать одну из операций со следующими спецификациями:

put_front (v: G)
            — Добавить v в начало, не перемещая курсор.
put_left (v: G)
            — Добавить v слева от позиции курсора, не перемещая курсор.
        require
            not_before: not before
put_right (v: G)
            — Добавить v справа от позиции курсора, не перемещая курсор.
        require
            not_after: not after
extend (v: G)
            — Добавить v в конец, не перемещая курсор.
        

Как показывают комментарии, эти процедуры спроектированы так, чтобы не оказывать воздействия на курсор, поскольку нет причин, чтобы вставка изменяла текущую активную позицию курсора.

original_index:= index
finish
put_right (v)
go_i_th (original_index)
        

Для удаления элементов можно использовать:

remove
          — Удалить элемент в позиции курсора; передвинуть курсор к правому
          — соседу (или к after, если правого соседа нет).
      require
          item_exists: not off
      ensure
          removed: count = old count – 1
          after_when_empty: is_empty implies after
        

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

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

6.2. Связные списки

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

Основы связных списков

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

Теперь, благодаря механизму универсализации, возможно обобщение на произвольные структуры. Экземпляр LINKED_LIST[T] для некоторого типа T будет ссылаться на ноль или более связанных ячеек, принадлежащих классу LINKABLE[T]. Каждый экземпляр класса LINKABLE[T] содержит значение типа T и ссылку на другой экземпляр этого класса:

Как показано на рисунке, реализация включает два класса.

При нормальном использовании клиентскому приложению требуется только класс LINKED_LIST. Класс LINKABLE необходим для реализации, представляя очень простое понятие ячейки списка, которая может быть связана с другой подобной ячейкой: типичный экземпляр выглядит следующим образом:

Реализация методов класса LINKED_LIST основана на запросах класса LINKABLE и связанных сеттер-командах:

item: G
            — Значение в ячейке.
right: LINKABLE [G ]
            — Следующий элемент.
put (x): G
            — Установить значение элемента равным x.
        ensure
            set: item = x
put_right (other: LINKABLE [G])
            — Связывание с ячейкой other.
        ensure
            set: right = other
        

Вставка и удаление

Следующий рисунок показывает, как класс LINKED_LIST реализует команду put_right, которая должна добавлять элемент справа от курсора, не перемещая сам курсор. Для связного списка достаточно создать новую ячейку LINKABLE и обновить ссылки:

Реализация метода использует два вызова put_right из класса LINKABLE. Обратите внимание также на то, что требуется особый разбор случая, когда список пуст и before истинно:

put_right (v: G)
            — Добавить v справа от позиции курсора, не меняя его положения.
        require
            not_after: not after
        local
            p: LINKABLE [G ] — Ячейка должна быть создана
        do
            create p.make (v)
            if before then — Специальный случай before:
                p.put_right ( first_element)
                first_element:= p
                active:= p
            else — Общий случай:
                p.put_right (active.right)
                active.put_right ( p)
            end
ensure
                next_exists: active.right /= Void
                inserted: (not old before) implies active.right.item = v
                inserted_before: (old before) implies active.item = v
        end
        

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

Процедура remove удаляет ячейку списка в позиции курсора. Спецификация, заданная ранее, устанавливает, что курсор передвигается в следующую позицию, непосредственно справа от той, где он находился, что показана на следующем далее рисунке. Реализация должна изменить две ссылки.

Для изучения текста процедуры следует обратиться к фактической реализации – процедуре remove из класса LINKED_LIST. Она более сложная, чем put_right, поскольку необходимо учитывать больше специальных случаев, в частности, когда курсор установлен на первом или последнем элементе. Целесообразно вначале разобрать текст более простой процедуры – remove_right.

Обращение связного списка

В качестве заключительной иллюстрации алгоритмов, манипулирующих ссылками, рассмотрим метод, единственный в этой лекции, не включенный в момент написания этого текста в состав соответствующего класса LINKED_LIST библиотеки EiffelBase (нет никаких объективных причин, чтобы не сделать это теперь). Мы хотим создать процедуру, обращающую элементы списка. Основная идея ясна, поскольку мы уже писали функцию, решающую эту задачу. Теперь мы должны справиться с двумя дополнительными проблемами: обобщением на произвольные связные списки и необходимостью обращения существующего списка на том же месте, что делает нашу задачу более сложной.

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

Время программирования!

class MY_INTEGER_LIST inherit LINKED_LIST [INTEGER] feature
              reverse do … Разместите здесь Ваш код … end
end
        

Нет необходимости изменять другие свойства родительского класса.

Проблема такого подхода связана с его эффективностью: первый проход по списку потребует count итераций, второй count – 1, третий count – 2 и т.д., так что общее число итераций равно count (count + 1) / 2, что означает $$O (count^2)$$. Мы же хотим иметь алгоритм со сложностью O(count). Начнем его проектировать. Он начинается так же, как и версия для функции с единственным циклом, но изменяет структуру цикла на месте, не создавая нового списка:

В этом промежуточном состоянии:

Здесь присутствуют все признаки хорошего инварианта итеративного процесса, где процесс может рассматриваться как последовательная аппроксимация. Достаточно тривиально обеспечить начальную истинность инварианта, установив pivot как исходный first_element и first_element – void. Инвариант вырабатывает желаемый результат по завершении, когда i является последней позицией исходного списка, first_element даст нам полностью обращенный список! Когда же инвариант выполняется в промежуточном состоянии, то несложно расширить его на следующий элемент списка, изменяя значение трех ссылок, как показано на следующем рисунке:

Код такой итерации цикла достаточно прост:

i:=first_element
first_element:= pivot              — Операция, помеченная А на рисунке
pivot:= pivot.right            — Операция В
first_element.put_right (i)            — Операция С
        

Заметьте необходимость временной переменной i для записи исходного значения first_element, так, чтобы мы могли связать новый первый элемент в последней операции С.

Приведем полный алгоритм, соединяя все вместе. Для выражения варианта – следует заботиться о завершаемости цикла – добавим целочисленную переменную с, подсчитывающую итерации, или, что то же, записывающую позицию текущего first_element.

reverse
            — Изменить связи элементов в обратном порядке.
            — (Нет предусловия – будет работать и для пустого списка.)
            — Не перемещает курсор.
        local
            pivot, i: LINKABLE [G ] ; c: INTEGER
        do
            from
                pivot:= first_element ; first_element:= Void ; c:= 0
            invariant
            — с – индекс элемента first_element, если он есть в исходном списке;
                — список, начинающийся с first_element, включает все элементы
                — в обращенном порядке вплоть до позиции с в исходном списке;
                — список, начинающийся с pivot, включает все элементы в исходном
                —порядке, начиная с позиции с.
            until
                pivot = Void
            loop
                i:= first_element
                first_element:= pivot
                pivot:= pivot.right
                first_element.put_right (i)
                c:= c + 1
            variant
                count – c + 1
            end
        end
        

Убедитесь, что вы хорошо понимаете алгоритмы reverse и put_right, поскольку они демонстрируют основные идеи реализации операций над связными списками. Они также демонстрируют трудности, возникающие при работе со ссылками, и напоминают о принципе программирования ссылок – такие операции должны быть частью специальных, тщательно спроектированных кластеров или частью профессиональных библиотек общецелевого назначения, но не должны быть частью приложения, реализующего "бизнес-логику" программы.

Производительность операций над связным списком

Можно оценить стоимость операций над связным списком.

Интересный случай представляет операция extend, добавляющая элемент в конец списка. Как отмечалось, она может быть реализована через операцию finish, за которой следует операция put_right и go_i_th, если требуется восстановить позицию курсора. Поэтому суммарная сложность операции есть O(count). Часто при создании списка приходится поочередно добавлять новые элементы в конец списка. В этом случае позволительно оставлять курсор в конце списка, тогда для реализации extend нужно выполнить операции put_right и forth, что дает сложность O(1).

Некоторые операции, работающие в позиции курсора, более хитро устроены, чем put_right и remove_right: им может, например, понадобиться ссылка на элемент, стоящий слева от курсора. Таковой является операция remove, удаляющая элемент под курсором. Включение атрибута previous, указывающего на левого соседа, позволяет сохранить сложность O(1) для таких операций, но несколько снижает эффективность других операций, поскольку требует обновления атрибута при выполнении ряда действий.

Интерфейс LINKED_LIST и других списковых классов не делает очевидного различия между forth, передвигающим курсор на одну позицию вправо, и back, двигающим курсор в обратном направлении. Однако производительность этих операций кардинально отличается: forth – O(1), в то время как back имеет сложность O(count), будучи реализована как

start
go_i_th (index – 1)
        

При добавленном атрибуте previous сохраняется сложность O(1), но только при однократном выполнении back, так что в общем случае введение этого атрибута мало чем помогает в эффективности этой операции. Симметричные структуры, такие как двусвязные списки TWO_WAY_LIST, рассматриваемые ниже, устраняют эти трудности.

Дадим обзор сложности выполняемых операций. Вначале рассмотрим операции вставки удаления.

Сложность операций по изменению позиции курсора:

Глобальные операции могут требовать прохода по списку:

6.3. Другие варианты списков

Класс LINKED_LIST представляет одну из возможных реализаций списков. Существуют и другие варианты.

Двусвязный список

В реализации LINKED_LIST предпочтение отдается проходу по списку слева направо, и как следствие, возникает существенное различие в эффективности методов forth и back. Класс TWO_WAY_LIST представляет полностью симметричную структуру. Платой за это являются потери в памяти, так как вместо LINKABLE с одной связью приходится использовать класс BI_LINKABLE, в котором каждая ячейка имеет две ссылки – вперед и назад:

Класс TWO_WAY_LIST содержит не только ссылку first_element, но и, дополняя симметрию, ссылку last_element на последний элемент списка:

В результате симметрии операции, требующие левого просмотра, такие как remove_left и put_left, так же как и их правосторонние двойники, имеют эффективность O(1), а метод back становится так же хорош, как и метод forth.

Абстракция и ee следствия

Здесь я должен рассказать небольшую историю с полей сражения. Как-то программисты одной из компаний объясняли своему менеджеру, что объектно-ориентированный инструментарий слишком медленный. Менеджер попросил старшего разработчика провести инспекцию кода, в результате чего было обнаружено, что на экземплярах LINKED_LIST многократно выполняется операция back. Заменив этот класс на TWO_WAY_LIST, получили ускорение работы в 23 раза. После этого программисты жили счастливо и никогда не говорили о потере скорости генерируемого кода.

Мораль: абстракция – краеугольный камень современного программирования – учит двум важным урокам.

Во-первых, она показывает существование рисков: вполне разумно и красиво рассматривать back как операцию, применимую ко всем спискам. Действительно, мы видели, что back реализована для односвязных списков. Если рассматривать список просто как список, абстракция с ее техникой полиморфизма и динамического связывания позволяет забыть, что иногда мы имеем дело с двусвязным списком, где back имеет эффективность O(1), а иногда может появляться односвязный список, возвращающий back в медлительное сообщество методов O(n). Наш первый урок состоит в том, что в практике профессиональной разработки ПО, где производительность является одним из важнейших ограничений, не следует позволять преимуществам функциональной абстракции подавлять свойства эффективности.

Если первый урок высвечивает возможную темную сторону абстракции, то второй урок свидетельствует о ее заслугах. Для достижения ускорения достаточно было изменить всего лишь несколько объявлений, заменив тип LINKED_LIST на TWO_WAY_LIST. Без ОО-методов и абстракции детали реализации были бы глубоко запрятаны внутрь приложения и изменения были бы более существенными и трудными.

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

Списки на массивах

Для представления списков можно использовать массивы вместо ссылочных структур:

Класс ARRAYED_LIST библиотеки EiffelBase обеспечивает эту реализацию. Пусть вас не смущает, что используется класс ARRAY: экспортируемые методы, видимые клиентам ARRAYED_LIST, те же, что и у класса LIST, реализуются методами класса ARRAY, такими как item и put. Внутренне, как показано на рисунке, lower равно 1, так что имеет место следующий инвариант класса: capacity = upper – lower + 1, откуда следует, что capacity = upper, так что верхняя граница задает физический размер массива.

У массива число его элементов count совпадает с его емкостью capacity. Но это не верно для списка, построенного на массиве: count является числом элементов списка, в то время как capacity – это максимально возможное число элементов, которое может изменяться при необходимости. На приведенном выше рисунке count равно 5, а capacity равно 9, и индексы элементов списка находятся в пределах от 1 до count. Инвариант класса включает свойство count <= capacity.

Курсор задается целочисленной переменной index, которая в классе ARRAYED_LIST реализована как атрибут. Еще один признак, отличающий массив от списка, построенного на массиве, состоит в том, что индекс массива меняется от 1 до capacity ( от lower до capacity), но index может меняться, как принято в списках, от 0 до capacity + 1.

Реализация не обязана размещать элементы списка, начиная с нижней границы. Для поддержки левосторонней вставки полезно рассматривать массив как круговую структуру с двумя маркерами на концах, – эта техника будет описана при рассмотрении круговых очередей. Реализация не представляет сложностей, однако позволяет для очередей избавиться от фатального ограничения списков на массивах – вставка и удаление требуют перемещения всех элементов слева или справа от курсора. Эти операции дорогостоящие и требуют O(n) времени. Удаление элементов можно откладывать, оставляя пустоты, но в какой-то момент потребуется провести O(n) сжатие массива. Если при вставке окажется, что достигнута емкость массива, то придется массив перестраивать, увеличивая емкость, а это, как отмечалось ранее, дорогостоящая операция.

Эти свойства существенно ограничивают полезность списков, построенных на массивах. Они представляют интерес для определенного круга сценариев, где изначально создается список, после чего он остается в относительно стабильном положении с небольшим числом вставок и удалений. Тогда список на массивах дает преимущества, особенно если часто выполняются операции по произвольному доступу к элементам по индексу – операция go_i_th(i) имеет сложность O(1), а не O(n), как для связных списков.

Мультимассивные списки

На тему списков вариаций может быть множество. Одной из таких вариаций является класс MULTI_ARRAY_LIST, соединяющий преимущества массивов и связных списков. Платой за это служит дополнительная сложность, как можно видеть, анализируя код этого класса. Такой список является двусвязным списком, элементы которого – списки, построенные на массивах:

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