Операции над списками

Основными операциями, которые выполняются над списками, являются перебор элементов списка, поиск заданного элемента, вставка в список нового элемента, удаление элемента из списка. Выполнение этих операций основано на изменении указателей.

2.1. Перебор элементов списка.

Эта операция выполняется для линейных списков очень часто и состоит в последовательном доступе к элементам списка – ко всем до конца списка либо до нахождения искомого элемента. Для каждого из перебираемых элементов осуществляется некоторая обработка его информационной части: сравнение с образцом, печать, модификация и прочее.

2.2. Вставка элемента в список.

Схематически выполнение этой операции представлено на рис. 12.3.

Мы видим, что указатель элемента эл2 теперь указывает не на элемент эл3, а на элемент эл5. Указатель элемента эл5 указывает на элемент эл3. Логическая последовательность элементов будет эл1, эл2, эл5, эл3, эл4. Подчеркнем еще раз, что в списке новый элемент эл5 физически не обязательно помещается за элементом эл2. Достаточно, чтобы он следовал за ним логически.

Рис. 12.3 Вставка элемента в середину односвязного списка

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

	head – указатель на начало

Эл2

Эл1

Рис. 12.4 Вставка элемента в начало односвязного списка

2.3. Удаление элемента из списка.

При удалении элемента Эл3 из списка, прежде всего, выполняется поиск этого элемента в списке, а затем его удаление. Результат удаления показан на рис. 12.5.

Рис. 12.5 Удаление элемента из списка

Теперь за элементом эл5 следует элемент эл4. Соответствующим образом изменился указатель элемента эл5. Элемент эл3 в списке теперь отсутствует, так как при просмотре списка, переходя от элемента к элементу в соответствии с указателями, мы на элемент эл3 не попадаем. Следует отметить, что удаление элемента из списка и удаление из памяти – это не одно и то же. Элемент Эл3 будет находиться в памяти до тех пор, пока мы не удалим его явно с помощью оператора delete.

Удаление элемента из начала списка показано на рис.12.6.

Рис. 12.6 Удаление элемента из начала списка