Двунаправленная итерация по односвязному списку

Question

В настоящее время я изучаю экзамен Data Structures и столкнулся с вопросом об итерации.

Возможно ли реализовать двунаправленный итератор над односвязным списком? Если да, то как это осуществить?

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

Answer 1

Этот ответ подразумевает, что список должен всегда оставаться односвязный:

Вам нужно всего лишь указатель на первый элемент и указатель на текущий элемент.

Когда вы идите вперед, увеличьте количество счетчиков, чтобы узнать, сколько раз вы повторяли. (Вставки МОГУТ аннулировать итераторы!). Назовем эту переменную count

Теперь, если вы хотите, чтобы перебирать в обратном направлении k значения из текущего элемента, вы знаете, что вам нужно перебирать форвард с первым элементом count - k раз.

EDIT: Конечно, мы можем повысить эффективность; этот ответ является своего рода грубой силой.

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

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

Answer 2

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

Answer 3

Альтернативой было бы: при создании итератора создать массив, размер которого является размером связанного списка, но не заполняет его. Храните индекс в итераторе вместе с «текущим узлом». Каждый раз, когда итератор перемещается вперед, также помещайте ссылку на узел в массив с соответствующим индексом. Чтобы переместить итератор назад, просто уменьшите индекс и посмотрите в массив, чтобы увидеть, какой узел вы уже посетили. Я думаю, что это в значительной степени эквивалентно «стек», упомянутому @DarthVader. Преимущество этого было бы, если вы ожидаете, что вызывающий абонент сделает лот обратного хода; простое другое решение, упомянутое другими, принимает O (n) каждый раз, когда выполняется обратный обход, но с использованием метода, подобного массиву, будет O (1). Недостатком было бы немного больше бухгалтерского учета, когда итератор продвигается вперед. В реальной жизни преимущества и недостатки должны быть взвешены. Для относительно небольшого списка это может оказаться неоправданным. Но предположим, что вам был предоставлен большой файл на диске с односвязными записями, и вы хотите, чтобы итератор проходил через файл; если вы хотите дать итератору возможность вернуться назад, вы не хотите перечитывать весь файл, чтобы найти предыдущий узел.