Предположим, мы реализуем связанный список, используя массив.Скажем, каждый элемент состоит из ключа и индекса следующего элемента.
Теперь вставка и удаление амортизируются O (1), если я не ошибаюсь.Если массив становится полным или слишком пустым, нам нужно выделить новый тип, имеющий двойной или половину размера.
Мы могли бы деамортизировать вставку, используя массив с изменяемым размером, как указано в Изменяемые размеры массивов в оптимальное время иSpace .Короче говоря, вместо одного огромного массива у нас есть меньшие массивы, и по мере роста набора данных меньшие массивы постепенно превращаются в большие массивы.У него есть довольно четкие границы времени выполнения каждой операции.
Но теперь, как мы можем деамортизировать удаление?
Это насколько я понял: мыможет поддерживать «свободный список».Помимо обычного «головного» индекса, мы будем отслеживать первый свободный индекс, который, в свою очередь, указывает на следующий свободный индекс и так далее.По сути, структура состоит из двух взаимосвязанных связанных списков, а именно списка данных и свободного списка.
Однако после большого количества удалений мы могли бы сидеть с массивом, полным «дыр».Перестройка всего объекта в половину размера за один раз может оказаться невозможной для больших наборов данных.
Можем ли мы деамортизировать удаление?