Каковы преимущества и недостатки использования динамического массива по сравнению со связанным списком?

Некоторые преимущества динамического массива перед связанным списком:

• Быстрый доступ к элементу по индексу. stackoverflow.com sergoff1.github.io Элементы хранятся последовательно, они попадают в кэш процессора при обращении к массиву и обрабатываются быстрее. sergoff1.github.io
• Массив занимает меньше памяти, так как с элементами не нужно хранить ссылки на «соседей». sergoff1.github.io

Некоторые недостатки динамического массива перед связанным списком:

• Долгие процедуры вставки и удаления. sergoff1.github.io При вставке нужно сдвигать все последующие элементы на 1 вправо, либо влево — при удалении. sergoff1.github.io
• Затратная процедура изменения размера массива. sergoff1.github.io

Некоторые преимущества связанного списка перед динамическим массивом:

• Быстрая вставка и удаление в любой позиции списка. stackoverflow.com Для вставки узла в середину достаточно изменить всего 2 ссылки. sergoff1.github.io
• Элементы могут храниться в различных областях памяти. sergoff1.github.io Список легко меняет свой размер. sergoff1.github.io
• Легко выделить часть списка, просто изменив поля HEAD и TAIL. sergoff1.github.io

Некоторые недостатки связанного списка перед динамическим массивом:

• Медленный доступ к индексу. stackoverflow.com Чтобы обратиться к элементу, необходимо перебрать всех его предшественников. sergoff1.github.io
• Время доступа к узлам больше, чем в массиве, так как они хранятся в разных областях памяти. sergoff1.github.io
• Можно двигаться лишь в одном направлении. sergoff1.github.io