Состояние списка
Список пуст.
Операции
Ключевые операции
Вставка в начало
void AddFirst(PNode &Head, PNode NewNode) {
NewNode->next = Head; // новый узел указывает на бывшую голову
Head = NewNode; // голова списка переставляется на новый узел
}
Вставка после узла p
void AddAfter(PNode p, PNode NewNode) {
NewNode->next = p->next; // ВАЖНО: сначала на следующий узел
p->next = NewNode; // и только потом — ссылка от p
}
Удаление узла по значению
void DeleteNode(PNode &Head, PNode OldNode) {
PNode q = Head;
if (Head == OldNode) Head = OldNode->next;
else {
while (q && q->next != OldNode) q = q->next;
if (q == NULL) return;
q->next = OldNode->next;
}
delete OldNode;
}
Порядок операций важен. Если в
AddAfter сначала изменить
p->next, мы потеряем адрес следующего узла и не сможем к нему обратиться.
Задание
- Добавьте три узла в конец списка. Сколько операций перехода по ссылке выполнит программа?
- Вставьте узел после заданного ключа. Поменяйте местами две строки в
AddAfter— что произойдёт? - Реализуйте «разворот списка» без создания нового. Подсказка: нужно три указателя — prev, cur, next.
- Добавьте операцию «удалить все узлы с чётными значениями», аккуратно обрабатывая случай удаления головы.