Re: Fun linked list problem



On 29 Apr 2006 17:35:36 -0700
"Gene" <gene.ressler@xxxxxxxxx> wrote:

Murali wrote:
Given a singly linked list (implemented using pointers) implement a
Data Structure which allows you to traverse the list in either
direction. More specifically given any sequence of {next,prev}, you
should be able to print the corresponding elements of the list.

E.g.

List = [1,3,5,2,6,9,4]

Seq: {Start}NNNPPNNPNNN

will print

135253525269

You just reverse the links as you go forward and restore them as you go
backward. So you need only constant space overall and O(1) time per
node traversed.

Plus O(N) on the total distance into the list at the end for
backing out and restoring the original pointers. If there's going to
be a lot of traversing and you need the list usable from the start
afterwards double linking (with the xor trick if space is that important)
would seem to be a win.

--
C:>WIN | Directable Mirror Arrays
The computer obeys and wins. | A better way to focus the sun
You lose and Bill collects. | licences available see
| http://www.sohara.org/
.