Проблема концов списка и циклические списки
Основной сложностью при работе со списками является необходимость проверки множества вариантов при выполнении операций над элементом списка, в том числе:
-список пустой;
-элемент единственный;
-элемент в начале списка;
-элемент в конце списка;
-элемент в середине списка.
Особенно это заметно при работе с двусвязными списками. Для решения проблемы " концов списка" удобно бывает сделать его циклическим, то есть вместо указателей NULL записывать:
-указатель на последний элемент в качестве указателя на предыдущий в первом элементе списка;
-указатель на первый элемент в качестве указателя на последующий в последнем элементе списка.
Тогда единственный элемент в циклическом списке будет иметь указатели на самого себя, а в процессе просмотра конец списка определяется фактом возвращения на его начало. В качестве примера рассмотрим функции просмотра циклического списка и включения элемента в его конец.
//------------------------------------------------------bk53-06.cpp
// Просмотр циклического списка
void scan(list2 *ph)
{
list2 *p;
if (ph ==NULL) return;
p = ph;
do { /* ... */
p = p->next;
}
while (p != ph); // возврат к началу списка
}
// ------------------------- Включение в конец списка
list2 *insert(list2 *ph, int v)
{
list2 *p = new list;
p->val = v;
p->next = p->pred = p; // указатели на самого себя
if (ph ==NULL)
return p; // включение в пустой список
list2 *pr; // текущий и предыдущий элементы списка
pr = ph->pred; // в циклическом списке l предыдущий
// l от первого - последний
pr->next = p; // l следующий за последним = новый
ph->pred = p; // l предыдущий для первого = новый
p->pred = pr; // l предыдущий для нового = последний
p->next = ph; // l следующий за новым = первый
return ph;
}
При выполнении операций над циклическим списком необходимо следить за его заголовком. Например, операция включения в начало списка будет отличаться от включения в конец списка только перемещением заголовка на новый элемент:
ph = p;
