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

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

 

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

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

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

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

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

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

 

		previous

 

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

 

 

 

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

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

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

 

 

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

 

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

 

delete

 

 

 

 

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