Массивы и связные списки

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

Definition

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

Scope

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

Core questions

• Когда непрерывное (массивное) хранение превосходит хранение с помощью указателей (список)?
• Как динамический массив достигает амортизированного постоянного времени добавления, несмотря на периодическое изменение размера?
• Каковы компромиссы в затратах между массивами и связными списками для вставки, удаления и доступа?
• Как стеки и очереди реализуются поверх этих структур?
• Как расположение в памяти влияет на реальную производительность через поведение кэша?

Key concepts

• непрерывная память
• индексированный доступ
• изменение размера динамического массива
• односвязные и двусвязные списки
• стеки (LIFO)
• очереди (FIFO)
• амортизированная стоимость
• локальность кэша

Key theories

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

Массивы поддерживают индексированный доступ за O(1), но вставку или удаление в середине за O(n), тогда как связные списки поддерживают вставку/удаление за O(1) при наличии узла, но доступ по позиции за O(n); правильный выбор зависит от набора операций.

Амортизированный рост динамических массивов

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

Clinical relevance

Массивы и списки являются основой почти каждой программы: динамические массивы реализуют типы списков/векторов по умолчанию в большинстве языков, очереди лежат в основе планирования и поиска в ширину, стеки лежат в основе управления вызовами функций и вычисления выражений, а компромисс между массивом и списком является рутинным практическим проектным решением, влияющим на производительность.

History

Массивы являются одними из самых ранних структур данных, присутствующих в первых языках программирования, а связные списки были введены для символьной и списковой обработки (в частности, в IPL Ньюэлла, Шоу и Саймона, а затем в Lisp) в конце 1950-х годов. Систематическое изложение Кнута в «Искусстве программирования» установило их канонический анализ.

Key figures

• Donald Knuth
• Robert Sedgewick

Seminal works

• knuth1997vol1
• cormen2009

Frequently asked questions

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

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

Почему добавление элементов в массив считается операцией с постоянным временем, если изменение размера копирует все?

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