Сравнение последовательного и связанного распределения

Критерий	Последовательные распр.	Связанные распр.
1.Доступность к элементу.	Массив   K адрес(Хк)=адрес(Х1) + К*размер(Хi) O(1) Реализует модель с произвольным доступом к элементу	ЛСС   O(n)   Реализует модель с последовательным доступом.
2.Расположение в памяти	Область должна быть единой, однако как правило операционная система (ОС) память выделяет по страничное, при этом размер страницы может быть меньше чем требуемый размер под страницу. Последовательность областей – таблицы дескрипторов областей, выделенных под массив. Задается под ОС, следует разделять динамический и статический массив. Статические элементы должны умещаться в 64Мб, а если нет – то создаются динамические массивы, которым доступно всё ОЗУ ОС. Доступ к элементу динамического массива на порядок медленнее доступа к статическому массиву.	Это изначально динамический список. Поэтому ему доступно всё адресное пространство ОС.
3.Добавление элемента Пусть требуется добавить новый элемент в позиции с номером k.	О(N)	Вставка заключается в трех шагах 1. Выделение памяти под новый элемент
4.Удаление элемента – аналогично	О(N)
5.Объединение или соединение.	= О(N)	Объединение ЛСС заключается в том, что вместо признака конца первого списка записывает адрес первого элемента первого списка. Казалось что доступ к последнему элементу первого списка осуществится за О(N). Однако для экономии операций, если алгоритм ориентирован на регулярное слияние, то кроме головы можно хранить и хвост а’ и в’, которые указывают на последний элемент. Тогда операция добавления элемента в конец списка будет, осуществляется O(1).

Примечание 3,4: заметим, что добавление и удаление в ЛСС осуществляется очень быстро, однако надо получить доступ к k-му элементу, трудоемкость примерно одинакова.