Включение элемента в список после заданного

Необходимо включить новый элемент после элемента списка, заданного ссылкой Work2 (рис. 13).

Алгоритм состоит из следующих шагов.

Процедура Включить В Список (X, Work2)

• 1. BH(Workl).
• 2. Workl—>Data = X.

• 3. Work 1 —>Next = Work2—>Next.
• 4. Work2^Next = Workl.

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

Включение элемента в конец списка

Зная алгоритм включения элемента после заданного, поставленную задачу можно решить следующим образом. Просмотрев весь список найти последний его элемент и вставить новый элемент за последним.

Однако такой метод допустим только для списков с небольшим количеством элементов. Если же количество элементов в списке велико, то такой алгоритм по очевидным причинам неэффективен. Лучшее решение - ввод второго указателя, указателя на последний элемент списка.

Недостаток метода создания списка путем включения элемента в конец заключается в том, что первый из включаемых элементов нужно обрабатывать иначе, чем остальные.

Включение элемента в список перед заданным элементом

Пусть требуется включить элемент X, заданный ссылкой Workl, перед элементом списка, заданным ссылкой Work2. Алгоритм решения этой задачи не очевиден, хотя и прост.

Трудность заключается в том, что в односвязном списке нет возможности вернуться к элементу, предшествующему данному. Однако, как вы увидите из алгоритма, это и не требуется. Достаточно включить новый элемент после текущего, а потом поменять местами значения информационных полей (рис. 14).

Процедура Включить_Перед(Х, Work2)

• 1. ВП(Workl)
• 2. Workl^Data = Work2^>Data.
• 3. Workl —ext = Work2—>Next.
• 4. Work2^Next = Workl.
• 5. Work2^Data = X.

Рис. 14. Включение элемента в список перед заданным

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

Удаление элемента, следующего за заданным

Сначала рассмотрим алгоритм исключения элемента, следующего за элементом, на который указывает World (рис. 15).

Процедура Исключить (Workl)

• 1. Если Workl^Next-O, выход
• 2. Work2 = Workl —>Next (получить адрес исключаемого элемента).
• 3. Workl—>Next = Work2^Next.
• 4. OIJ(Work2).

Рис. 15. Удаление элемента, следующего за заданным