Отменить проверку NULL в поиске связанного списка

Question

Как исключить проверку NULL на каждой итерации цикла while, ищущего связанный список?

Answer 1

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

Добавлено:

См. Пример поиска часового ;мои извинения за язык.Я вспомнил стратегию от N.Вирта "Алгоритмы и датаструктуры" ;мои извинения за языки.

Answer 2

Вы просто не можете.

Пока вы выполняете итерацию по любой структуре данных, вы всегда хотите, чтобы ваш алгоритм работал по-разному, ЕСЛИ он достиг конца структуры, что требует какой-либо проверки.Это верно, какой бы ни была ваша структура данных, и она не зависит от «пути», который вы перебираете: for (int i = 0; i ; ++ i), for (iterator it = myList.begin (); it! = mylist.end () ; it ++), а ( currentNode.hasChildren () ), а ( javaIterator.hasNext () ) ...

Тем не менее, независимо от того, что делает ваш цикл, проверка наличия доступного объекта на NULL никогда не станет узким местом вашего алгоритма.Это даже трудно сделать менее трудоемким ...

ЕДИНСТВЕННЫЙ способ избежать проверки - избежать самого цикла, поэтому записывать каждый шаг, лежащий в цикле, но для этого необходимо знатьразмер связанного списка во время компиляции, и в этом случае ваш компилятор мог оптимизировать ваш код лучше, чем вы, вероятно, сделали бы сами; -)

Answer 3

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

Answer 4

Вы можете использовать круговой (зацикленный) связанный список, где последний элемент связан с первым.