На этом шаге мы рассмотрим первый случай удаления звена.

    Пусть нам известен указатель Res на удаляемое звено. Возможны два случая:

• удаляемый элемент является последним в двунаправленном списке,
• удаляемый элемент не является последним в двунаправленном списке.

    Вначале рассмотрим ситуацию, когда он не последний, то есть (*Res).sled!=NULL. Изобразим схему "до", соответствующую этому случаю:

Рис.1. "Начальная" позиция

1. Исключим звено из списка, "перенастроив" указатели предыдущего и последующего звеньев:

       (*(*Res).sled).pred = (*Res).pred;
       (*(*Res).pred).sled = (*Res).sled;
   

   
   Рис.2. "Перенастройка" указателей

2. Осталось только удалить звено, на которое указывает Res, из heap-области:

       delete Res;
   

   
   Рис.3. Освобождение памяти

    Пусть теперь удаляемый элемент оказался последним.

    Взгляните на схему "до":

Рис.4. "Начальная" позиция

1. "Настроим" указатели предпоследнего элемента и конца списка:

       (*(*Res).pred).sled = NULL;
       ksp = (*ksp).pred;
   

   
   Рис.5. "Настройка" указателей

2. Теперь удалим из кучи звено, на которое указывает Res:

       delete Res; 
   

   
   Рис.6. Возврат памяти в кучу

    Запишем функцию для удаления звена, на которое указывает ссылка:

void Delete (node **nsp, node **ksp, node *Res)
// Удаление звена из двунаправленного списка.
// *nsp - указатель на начало списка,
// *ksp - указатель на конец списка,
// Res  - указатель на удаляемое звено.
{
  if ((*Res).sled!=NULL)
    { (*(*Res).sled).pred = (*Res).pred;
      (*(*Res).pred).sled = (*Res).sled; delete Res;}
  else
    { (*(*Res).pred).sled = NULL; *ksp = (**ksp).pred; delete Res;}
}

    На следующем шаге мы продолжим знакомиться с алгоритмами удаления звена.

Предыдущий шаг Содержание Следующий шаг