В настоящее время я готовлюсь к экзамену по структурам данных и столкнулся с вопросом об итерации.
Можно ли реализовать двунаправленный итератор для односвязного списка? Если да, то как его реализовать?
У меня возникла идея сначала пройти по связанному списку вперед и сохранить временный связанный список, который содержит узлы в обратном направлении. Но обход этого временного списка привел бы к тому, что итератор допускает только обратный обход.
Этот ответ предполагает, что список ВСЕГДА должен оставаться односвязным:
Вам нужен только указатель на первый элемент и указатель на текущий элемент.
Когда вы выполняете итерацию вперед, увеличивайте некоторый счетчик, чтобы узнать, сколько раз вы выполняли итерацию. (Вставки МОГУТ сделать итераторы недействительными!). Назовем эту переменную count
Теперь, если вы хотите повторить k значений текущего элемента в обратном направлении, вы знаете, что вам нужно выполнить итерацию ВПЕРЕД от первого элемента count - k раза.
РЕДАКТИРОВАТЬ: Конечно, мы можем повысить эффективность; этот ответ является своего рода подходом грубой силы.
Как упоминалось в одном из комментариев, вы можете помещать указатели в стек при итерации вперед, а затем извлекать их при итерации назад.
Если список не всегда должен оставаться односвязным, то вы можете добавлять обратные ссылки по мере повторения вперед, а затем удалять эти ссылки при повторении назад (хотя кто знает, зачем вам это нужно).
Вы всегда можете использовать переменную, которая отслеживает текущий узел. Если вы хотите пройти вперед, просто сделайте это, как обычно. Если вы хотите двигаться назад, просто начните с первого узла, а затем продолжайте двигаться, пока следующий узел не сравняется с текущим узлом.
Альтернативой может быть: когда итератор создан, создайте массив, размер которого равен размеру связанного списка, но не заполняйте его. Сохраняйте индекс в итераторе вместе с «текущим узлом». Каждый раз, когда итератор перемещается вперед, также помещайте ссылку на узел в массив по соответствующему индексу. Чтобы переместить итератор назад, просто уменьшите индекс и посмотрите в массиве, какой узел вы уже посетили. Я думаю, что это в значительной степени эквивалентно «стеку», упомянутому @DarthVader. Преимущество этого будет в том случае, если вы ожидаете, что вызывающая программа будет выполнять много обхода в обратном направлении; простое решение, о котором упоминали другие, требует O (n) каждый раз, когда выполняется обратный обход, но использование метода, подобного массиву, будет O (1). Недостатком будет немного больше учета, когда итератор перемещается вперед. В реальной жизни необходимо взвесить преимущества и недостатки. Для относительно небольшого списка это может быть нецелесообразно. Но предположим, что вам дан большой файл на диске с односвязными записями, и вам нужен итератор, который проходит через файл; если вы хотите дать итератору возможность вернуться назад, вам не нужно перечитывать весь файл только для того, чтобы найти предыдущий узел.
