Использование барьера для упрощения условия перебора списка
При линейном поиске, если не использовать итератор, перед началом каждой итерации необходимо проверить не достигнул ли конец списка и является ли текущий элемент искомым элементом.
Проверять достижение конца списка необходимо из-за того, что точно не известно присутствует ли искомый элемент в списке. Если бы такой элемент точно был, то достаточно было бы проверять не является ли текущий элемент искомым элементом.
Чтобы сократить проверку, перед началом перебора можно добавить искомый элемент в конец списка. После цикла проверить, не выходит ли найденный элемент за границу изначального списка.
Такой подход называется использование барьера (sentinel).
Ссылки
- Алгоритмы и структуры данных. Новая версия для Оберона. Никлаус Вирт. ДМК Пресс. 2010. Глава 1. Фундаментальные структуры данных. 1.8. Поиск