Структуры и алгоритмы обработки данных

       

Односвязный список, как самостоятельная структура данных


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

Пример:

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

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

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



Содержание раздела