Учебник неправильный. Первый член списка не имеет пригодного для использования «предыдущего» указателя, поэтому требуется дополнительный код для поиска и разъединения элемента, если он оказывается первым в цепочке (обычно 30 % элементов являются головными в своей цепочке, если N=M (при отображении N элементов в M слотов; каждый слот имеет отдельную цепочку.))
РЕДАКТИРОВАТЬ:
Лучшим способом использования обратной ссылки является использование указателя на ссылку, которая указывает на нас (обычно это ->следующая ссылка предыдущего узла в списке).
struct node {
struct node **pppar;
struct node *nxt;
...
}
тогда удаление становится:
*(p->pppar) = p->nxt;
И приятной особенностью этого метода является то, что он одинаково хорошо работает для первого узла в цепочке (чей указатель pppar указывает на некоторый указатель, который не является частью узла.
ОБНОВЛЕНИЕ 11 ноября 2011 г.
Поскольку люди не понимают моей точки зрения, я попытаюсь проиллюстрировать. В качестве примера есть хеш-таблица table (по сути, массив указателей) и набор узлов one, two, three, один из которых нужно удалить.
struct node *table[123];
struct node *one, *two,*three;
/* Initial situation: the chain {one,two,three}
** is located at slot#31 of the array */
table[31] = one, one->next = two , two-next = three, three->next = NULL;
one->prev = NULL, two->prev = one, three->prev = two;
/* How to delete element one :*/
if (one->prev == NULL) {
table[31] = one->next;
}
else {
one->prev->next = one->next
}
if (one->next) {
one->next->prev = one->prev;
}
Теперь очевидно, что приведенный выше код — это O(1), но есть кое-что неприятное: ему по-прежнему нужны array и индекс 31, так что в большинстве случаев узел является «самостоятельным», и указателя на узел достаточно, чтобы удалить его из цепочки, кроме случаев, когда он является первым узлом в своей цепочке; тогда потребуется дополнительная информация, чтобы найти table и 31.
Далее рассмотрим эквивалентную структуру с указателем на указатель в качестве обратной ссылки.
struct node {
struct node *next;
struct node **ppp;
char payload[43];
};
struct node *table[123];
struct node *one, *two,*three;
/* Initial situation: the chain {one,two,three}
** is located at slot#31 of the array */
table[31] = one, one-next = two , two-next = three, three->next = NULL;
one->ppp = &table[31], two->ppp = &one->next, three->ppp = &two-next;
/* How to delete element one */
*(one->ppp) = one->next;
if (one->next) one->next->ppp = one->ppp;
Примечание: никаких особых случаев, и нет необходимости знать родительскую таблицу. (рассмотрите случай, когда существует более одной хэш-таблицы, но с одинаковыми типами узлов: операция удаления все равно должна знать, из какой таблицы следует удалить узел).
Часто в сценарии {prev,next} особых случаев избегают, добавляя фиктивный узел в начале двусвязного списка; Но это также должно быть выделено и инициализировано.
person
wildplasser
schedule
12.11.2011
