Учебник не прав. Первый член списка не имеет полезного «предыдущего» указателя, поэтому требуется дополнительный код, чтобы найти и отсоединить элемент, если он окажется первым в цепочке (обычно 30% элементов являются главой их цепочки, если N = M, (при отображении N элементов в M слотов; каждый слот имеет отдельную цепочку.))
EDIT:
Лучший способ, чем использовать обратную ссылку, - это использовать указатель на ссылку, которая указывает на нас (обычно это -> следующая ссылка предыдущего узла в списке)
struct node {
struct node **pppar;
struct node *nxt;
...
}
удаление становится:
*(p->pppar) = p->nxt;
И приятной особенностью этого метода является то, что он одинаково хорошо работает для первого узла в цепочке (чей указатель pppar указывает на некоторый указатель, который не является частью узла.
ОБНОВЛЕНИЕ 2011-11-11
Поскольку люди не видят мою точку зрения, я попытаюсь проиллюстрировать. В качестве примера приведена хеш-таблица 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} можно избежать особых случаев, добавив фиктивный узел в начале двойного связанного списка; Но это тоже должно быть выделено и инициализировано.