Как правильно использовать дозорные узлы?

Будет несколько (близко) связанных вопросов вместо одного. Для нашего удобства я пронумерую их соответствующим образом.

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

Мне дали базовую реализацию двусвязного списка (в нем хранятся только значения int), и задача состоит в том, чтобы изменить реализацию, чтобы она использовала дозорный узел, подобный этому:

Иллюстративное изображение (пока не разрешено вставлять изображения, извините)

Вопрос 1

Я предполагаю, что переменная head списка будет указывать на первый реальный узел (тот, что после дозорного узла), а переменная tail будет просто указывать на последний узел. Я прав или head должен указывать на дозорный узел? Я прошу здесь о передовой практике или наиболее стандартном подходе.

вопрос 2

Я понимаю, что при поиске значения в списке мне больше не нужно проверять значение nullptr, так как я использую дозорный узел. Поскольку список в основном сформировал круг благодаря дозорному узлу, я должен завершить его после итерации по всему списку и достижения его. Могу ли я сделать это, поместив значение, которое я ищу, в дозорный узел и использовать его в качестве своего рода дозорного значения, а затем проверить, возвращается ли результат из дозорного узла, когда цикл заканчивается? Некоторые источники утверждают, что дозорные узлы вообще не должны хранить никаких значений. Является ли мой подход правильным/достаточно эффективным?

Вопрос 3

При простом повторении, а не при поиске определенного значения (например, подсчет узлов, вывод всего списка в консоль), нужно ли мне проверять дозорный узел так же, как и для nullptr (для завершения цикла итерации) или есть ли другой или более умный способ сделать это?


c++ algorithm data-structures sentinel linked-list
person Sandwich    schedule 29.03.2018    source источник
comment
просто из любопытства, почему на вашем изображении последний узел списка не имеет следующего указателя на часовой?   -  person Srini    schedule 30.03.2018
comment
Хороший вопрос, я даже не заметил (я его не автор). Я бы автоматически предположил, что следующим за последним элементом будет дозорный узел, а предыдущий дозорный узел будет последним элементом. Таким образом, получится круг.   -  person Sandwich    schedule 30.03.2018
comment
Хорошо, тогда в этом случае это не просто двусвязный список, но введение часового сделало бы его модифицированным круговым двусвязным списком.   -  person Srini    schedule 30.03.2018

Ответы (1)


arrow_upward
3
arrow_downward

Ответ 1

Да, это допустимая позиция для сторожевого узла. head и tail могут указывать на фактическое начало и конец данных. Но ваши функции add и delete должны быть осведомлены об аберрациях, вызванных на границах списка благодаря дозорному узлу.

Ответ 2

Да, это допустимая стратегия поиска, и на самом деле она называется методом Elephant in Cairo.

Ответ 3

Да, цель дозорного узла — сообщить вам, что это дозорный узел. Вы можете просто поддерживать постоянный указатель (или любой другой язык, который поддерживает ваш выбор) на этот дозорный узел, чтобы проверить, находитесь ли вы на дозорном узле, или просто установить флаг в узле.

person Srini    schedule 29.03.2018
comment
Объявление Ответ 3 - добавить флаг в общую структуру/класс узла, например isSentinel, и проверить только это? - person Sandwich; 30.03.2018
comment
честно говоря, я бы предпочел подход с указателем, поскольку он делает меньше предположений, но да, если это невозможно, то флаг, подобный тому, что вы предложили, будет работать, когда дозорный узел является особым классом обычных узлов. - person Srini; 30.03.2018
comment
В моем случае подход с указателем кажется проще, спасибо. Возможно ли вообще эффективно использовать один дозорный узел без зацикливания списка? Я так не думаю, но, возможно, я ошибаюсь. - person Sandwich; 30.03.2018
comment
Можете ли вы уточнить? Если ваш дозорный узел находится в начале/конце списка, его цель состоит в том, чтобы уведомить вас о том, что когда вы передаете его, вы успешно зациклились на списке один раз. Я бы сказал, что часовой наиболее эффективно выполнил свою задачу, что вы имели в виду? - person Srini; 30.03.2018
comment
Возможно ли даже иметь один дозорный узел в начале/конце списка и поддерживать список линейным (не зацикливаться на узле - например, последний элемент не указывает на дозорный узел в начале). Я думаю, что это невозможно, но я уже видел слишком много противоречивого материала об узлах-стражах. - person Sandwich; 30.03.2018
comment
Я имею в виду, что технически вы могли бы, но эффективность вашего стража будет значительно снижена, и у вас есть 2 типа эндшпиля, которые нужно проверить. Если ваш дозорный будет сидеть в начале, но не в конце, то вам нужно проверить null в конце, и наоборот, если дозорный сидит в конце. В идеале дозорная стратегия в этом контексте является заменой проверки на нуль, поэтому я бы не рекомендовал - person Srini; 30.03.2018
comment
Я именно так и думал. Спасибо, ваш ответ и этот комментарий проясняют это для меня. Пометка как принятая. - person Sandwich; 30.03.2018