Часовой подход с двусвязным списком - PullRequest
Новая
       81

Часовой подход с двусвязным списком

0 голосов
/ 22 сентября 2019

Я просматриваю двусвязный список на Java, я читаю о Стражах в двусвязном списке из Книга .В котором говорится, что

Во избежание некоторых особых случаев при работе вблизи границ двусвязного списка, это помогает добавить специальные узлы на обоих концах списка: узел заголовка в началесписка, и трейлер узел в конце списка.Эти «фиктивные» узлы известны как часовые (или охранники), и они не хранят элементы первичной последовательности

Что это за особые случаи?Зачем нам подход Sentinels?Это обязательно?Если мы используем обычный подход (без часовых) для двусвязного списка, это не спасет память этих дополнительных узлов?При составлении двойного связного списка с круговым подходом мы должны удалить часовых?

1 Ответ

0 голосов
/ 22 сентября 2019

В заметках Википедии кратко упоминается использование сторожевого узла для упрощения реализации связанных списков.

Стражный узел - это фиктивный узел, который идет в начале списка.

В двусвязном списке сторожевой узел указывает на первый и последний элементы списка.Нам больше не нужно хранить отдельные указатели для заголовка и хвоста списка, как мы делали со списками с односвязными связями.

Нам также не нужно беспокоиться об обновлении указателей головы и хвоста, поскольку, как мы увидим, это происходит автоматически, если мы вставляем после сторожевого узла, следовательно, добавляем элемент в список или вставляем перед элементомсторожевой узел, следовательно, добавление элемента в список.

Мы могли бы исключить контейнерный объект, который мы использовали для односвязных списков, поскольку сторожевой узел может отслеживать как первый, так и последний элементы в списке.Если бы мы сделали это, мы бы вернули пользователю указатель на сторожевой узел.

Однако структуры данных, как правило, разрабатываются с помощью объекта-контейнера, который обеспечивает связь между пользователем структуры данных и реализацией структуры данных, поэтому мы сохраним объект-контейнер.

Ответ @ 6502 на Как сторожевой узел дает преимущества по сравнению с NULL? очень полезен.

Ниже приведен код удаления узла в двухкратномсвязанный список узлов, где NULL используется для обозначения конца списка и где два указателя первый и последний используются для хранения адреса первого и последнего узла: 

// Using NULL and pointers for first and last
if (n->prev) n->prev->next = n->next;
        else first = n->next;
if (n->next) n->next->prev = n->prev;
        else last = n->prev;

, и это тот же код, гдевместо этого есть специальный фиктивный узел, чтобы отметить конец списка, и где адрес первого узла в списке хранится в следующем поле специального узла, а последний узел в списке хранится в поле prev поляспециальный фиктивный узел: 

// Using the dummy node
n->prev->next = n->next;
n->next->prev = n->prev;

Аналогичное упрощение также присутствует при вставке узла;например, чтобы вставить узел n перед узлом x (с x == NULL или x == и фиктивным значением, означающим вставку в последнюю позицию), код будет: 

// Using NULL and pointers for first and last

n->next = x;
n->prev = x ? x->prev : last;
if (n->prev) n->prev->next = n;
        else first = n;
if (n->next) n->next->prev = n;
        else last = n;

и 

// Using the dummy node
n->next = x;
n->prev = x->prev;
n->next->prev = n;
n->prev->next = n;

Как вы можете видеть, подход фиктивного узла удален для двусвязного списка всех особых случаев и всех условий.

...