Удалите элемент из набора из 1 элемента.

Question

Если вы хотите, чтобы один или несколько элементов списка с одним и тем же списком выполняли один или несколько элементов, вам необходимо установить задний указатель to null?

Читаю C++ Структуры Plus данных по Нелл Dale, и в главе 5.2, он пишет в своем методе Dequeue:

if (front == NULL) 
    rear == NULL; 

Я задаюсь вопросом, почему это необходимо. Единственная причина, я могу думать о том, как он реализует Ставить в отношении пустого множества:

if (rear == NULL) 
    front = newNode; 
else 
    rear->next = newNode; 
rear = newNode; 

Но не может ли это условие будет изменено на if (front == NULL)

Answer 1

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

• A1: front указывает на первый элемент, если он существует; NULL В противном случае
• A2: rear указывает на последний элемент, если он существует; NULL иначе

Вы утверждаете, что инварианты в качестве альтернативы может быть этим:

• B1: front указывает на первый элемент, если он существует; NULL иначе
• B2: rear указывает на последний элемент, если он существует

Теперь они похожи, но не идентичны. Инверторы B не требуют никакого специального значения rear, когда список пуст. Теперь вы можете использовать инварианты B для реализации списка, конечно, поскольку он допускает дискриминацию между пустым и непустым состоянием, и этого достаточно, чтобы обеспечить правильные реализации.

Но это ничего не говорит о том, лучше ли A или B на практике. Если вы используете инварианты B, функция заглянуть в последний элемент не может просто вернуть значение rear, так как его значение может быть любым, если очередь пуста; вы должны сначала проверить значение front.

// for the A2 invariant 
return rear ; 

// for the B2 invariant 
return (front == NULL) ? NULL : rear ; 

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

Все это говорит о том, что это главный случай для опасностей преждевременной оптимизации. Дополнительное назначение указателя на NULL почти никогда не будет проблемой производительности. Скорее всего, проблема заключается в введении дефекта во время обслуживания, когда кто-то полагается на инварианты А, когда существующий код использует B. А инварианты A когнитивно проще, потому что front и rear настроены аналогично, причем не имеют особого поведения. Инварианты B могли бы работать лучше, но ценой сложности. Любой выбор может быть лучше в зависимости от ваших обстоятельств.

Мораль этой истории: Всегда документируйте свои инварианты.