Визуализатор связного списка

Односвязный список: вставка в начало, конец и после заданного узла; удаление и поиск. Наглядно видно, как переставляются указатели next.

Динамические структуры Односвязный список Указатели

Состояние списка

Список пуст.

Операции

Ключевые операции

Вставка в начало
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, мы потеряем адрес следующего узла и не сможем к нему обратиться.

Задание

  1. Добавьте три узла в конец списка. Сколько операций перехода по ссылке выполнит программа?
  2. Вставьте узел после заданного ключа. Поменяйте местами две строки в AddAfter — что произойдёт?
  3. Реализуйте «разворот списка» без создания нового. Подсказка: нужно три указателя — prev, cur, next.
  4. Добавьте операцию «удалить все узлы с чётными значениями», аккуратно обрабатывая случай удаления головы.