Что такое Dummy Head?

Question

Так что я хочу точно знать, что такое фиктивный узел head/dummy (не знаю, что использовать) в связанном списке. Я нашел это на своих курсах на факультете, но без объяснений. Может ли кто-нибудь сказать мне определение и дать мне пример, может быть?

Answer 1

Dummy-узлы больше похожи на хак и обычно используются, когда вы хотите избежать написания дополнительного кода для краевых случаев.

Рассмотрим следующий случай вставки на хвост в связанном списке:

void insertAtTail(Node node, int i){ 

Node new = new Node(i); 

node.next = new; 

return new; 

} 

Это прекрасно работает, когда узел не является нулевым. Но представьте сценарий, в котором мы пытаемся выполнить insertAtTail() в пустом списке. Вышеупомянутый письменный код не будет работать, если узел имеет значение NULL. Поэтому мы, чтобы обработать края случай проверки, если узел является нулевым:

Node insertAtTail(Node node, int i){ 

Node new = new Node(i); 

if(node == null) {return new;} 

node.next = new; 

return new; 

} 

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

Node dummy = new Node(0); 

Теперь мы переходим этот фиктивный узел вызывающей функции:

insertAtTail(dummy, 5); 

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

Node insertAtTail(Node dummy, int i){ 

Node new = new Node(i); 

dummy.next = new; 

return new; 

} 

Как вы можете видеть, я удалил чек на нуль здесь.