Достоинства и недостатки связных списков

Перечислим преимущества связных списков.

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

2) На основе концепции связности элементов можно создавать бесконечное множество различных структур данных, что позволяет формировать в памяти ЭВМ разнообразные информационные модели для различных предметных областей.

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

4) Динамические связные структуры создаются, хранятся и обрабатываются в самой большой по объему области оперативной памяти - куче (heap). Это дает возможность с помощью таких структур решать серьезные задачи, требующие много памяти.

Основным недостатком связных списков является то, что затраты времени на получение доступа к их элементам зависят от количества элементов. Для получения доступа к некоторому i-ому элементу необходимо выполнить переходы по ссылкам вплоть до искомого элемента. Чем больше элементов в списке, тем больше переходов придется совершить.

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

Наконец, в элементах связных списков приходится размещать структурные ссылки, число которых зависит от степени связности К. Для К‑связной структуры затраты памяти на ссылки составляют К*SizeOf(Poiner) байт на каждый элемент.