Основными операциями, которые выполняются над списками, являются перебор элементов списка, поиск заданного элемента, вставка в список нового элемента, удаление элемента из списка. Выполнение этих операций основано на изменении указателей.
2.1. Перебор элементов списка.
Эта операция выполняется для линейных списков очень часто и состоит в последовательном доступе к элементам списка – ко всем до конца списка либо до нахождения искомого элемента. Для каждого из перебираемых элементов осуществляется некоторая обработка его информационной части: сравнение с образцом, печать, модификация и прочее.
2.2. Вставка элемента в список.
Схематически выполнение этой операции представлено на рис. 12.3.
Мы видим, что указатель элемента эл2 теперь указывает не на элемент эл3, а на элемент эл5. Указатель элемента эл5 указывает на элемент эл3. Логическая последовательность элементов будет эл1, эл2, эл5, эл3, эл4. Подчеркнем еще раз, что в списке новый элемент эл5 физически не обязательно помещается за элементом эл2. Достаточно, чтобы он следовал за ним логически.
Рис. 12.3 Вставка элемента в середину односвязного списка
Вставка элемента в начало односвязного списка показана на рис. 12.4. В данном случае переустанавливается указатель на начало списка на вновь вставленный элемент Эл3, а элемент Эл3 указывает на бывший первый элемент списка.
|
|
|
Рис. 12.4 Вставка элемента в начало односвязного списка
2.3. Удаление элемента из списка.
При удалении элемента Эл3 из списка, прежде всего, выполняется поиск этого элемента в списке, а затем его удаление. Результат удаления показан на рис. 12.5.
Рис. 12.5 Удаление элемента из списка
Теперь за элементом эл5 следует элемент эл4. Соответствующим образом изменился указатель элемента эл5. Элемент эл3 в списке теперь отсутствует, так как при просмотре списка, переходя от элемента к элементу в соответствии с указателями, мы на элемент эл3 не попадаем. Следует отметить, что удаление элемента из списка и удаление из памяти – это не одно и то же. Элемент Эл3 будет находиться в памяти до тех пор, пока мы не удалим его явно с помощью оператора delete.
Удаление элемента из начала списка показано на рис.12.6.
Рис. 12.6 Удаление элемента из начала списка