Is there any way to find an element in an unsorted doubly linked list given an element and pointer from which we can navigate? (we can't use head/tail pointers since the list is infinite)
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
8
Infinite/unbounded in both directions? Zig-zag.
answered Sep 9 '17 at 23:42
-
$\begingroup$ Would that work something like this? - steps in powers of 2 in alternating directions (2 steps left, 4 steps right,.....until we find the element)? $\endgroup$ – Sridhar Sep 10 '17 at 8:32
-
$\begingroup$ @Sridhar No, just keep two pointers, left and right and decrement left and increment right. $\endgroup$ – Pål GD Sep 10 '17 at 14:13
-
$\begingroup$ @PålGD that would work of course, but the question suggested "an element and pointer" in singular. $\endgroup$ – Hendrik Jan Sep 10 '17 at 15:16
-
-
$\begingroup$ Thanks for the idea. The complexity would be exponential right? $\endgroup$ – Sridhar Sep 11 '17 at 2:45
