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
|
1 Answer
$\begingroup$
$\endgroup$
8
Infinite/unbounded in both directions? Zig-zag.
answered Sep 9, 2017 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$– SridharSep 10, 2017 at 8:32
-
$\begingroup$ @Sridhar No, just keep two pointers, left and right and decrement left and increment right. $\endgroup$– Pål GDSep 10, 2017 at 14:13
-
$\begingroup$ @PålGD that would work of course, but the question suggested "an element and pointer" in singular. $\endgroup$ Sep 10, 2017 at 15:16
-
-
$\begingroup$ Thanks for the idea. The complexity would be exponential right? $\endgroup$– SridharSep 11, 2017 at 2:45