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

Просмотр односвязного списка может производиться только последовательно, начиная с головы (с начала) списка. Если необходимо просмотреть предыдущий элемент, то надо снова возвращаться к началу списка. Это – недостаток по сравнению с массивами.

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

Пример Необходимо вставить элемент X в существующий массив между 5-м и 6-м элементами.

Для проведения данной операции в массиве нужно сместить “вниз” все элементы, начиная с X6 - увеличить их индексы на единицу. В результате вставки получаем следующий массив:

Данная процедура в больших массивах может занимать значительное время.

В противоположность этому, в связанном списке операция вставки состоит в изменении значения 2-х указателей и генерации свободного элемента. Причём время, затраченное на выполнение этой операции, является постоянным и не зависит от количества элементов в списке.