Bi-Directional Iteration over a Singly Linked List

Question

I'm currently studying for a Data Structures exam, and encountered a question regarding iteration.

Is it possible to implement a bi-directional iterator over a singly-linked list? If so, how would one go about implementing it?

I had an idea to first forward traverse the linked list and store a temporary linked list that holds nodes in the reverse direction. But traversing this temporary list would result in an iterator that only allows for backwards traversal.

Answer 1

This answer assumes that the list must ALWAYS remain singly-linked:

You only need a pointer to the first element and a pointer to the current element.

When you iterate forward, increment some counter to know how many times you've iterated. (Insertions MAY invalidate iterators!). Let's call this variable count

Now, if you want to iterate backwards k values from the current element, you know that you need to iterate FORWARDS from the first element count - k times.

EDIT: Of course we can improve efficiency; this answer is kind of a brute-force approach.

As one of the comments mentioned, you could push pointers into a stack as you iterate forward, and then pop them off as you iterate backwards.

If the list doesn't always have to remain singly-linked, then you can add backwards links as you iterate forwards, and then remove those links if you iterate backwards (although who knows why you'd want to).

Answer 2

You could always use a variable which keeps track of the current node. If you want to traverse forward, just do as you would normally. If you want to move backwards, just start at the first node and then keep on moving until next node equals current node.

Answer 3

An alternative would be: when the iterator is created, create an array whose size is the size of the linked list, but don't populate it. Keep an index in the iterator along with the "current node". Every time the iterator is moved forward, also put the node reference in the array at the appropriate index. To move the iterator backward, just decrement the index and look in the array to see what node you've already visited. I think this is pretty much equivalent to the "stack" mentioned by @DarthVader. The advantage to this would be if you expect the caller to do a lot of backward traversal; the simple solution others have mentioned takes O(n) every time a backward traversal is done, but using a method like an array would be O(1). The disadvantage would be a little more bookkeeping when the iterator is moved forward. In a real-life case, the advantages and disadvantages would have to be weighed. For a relatively small list, it may not be worthwhile. But suppose you were given a large disk file with singly-linked records, and you want an iterator that goes through the file; if you want to give the iterator the ability to go backwards, you don't want to reread the entire file just to find a previous node.