5
$\begingroup$

Assume you have a single-linked list of length n. The list is immutable. A node node has a method next and node.next() returns a reference to the successor of node. node.print() prints the value of node node or does some other stuff, such etails don't matter.

Is it possible to print the nodes of the list in reverse order in linear time using only a constant amount of space?


Details:

For the last element of a list next points to a special node named NIL that represents the end of a list. For NIL next() and print() are not defined.

The following simple pseudocode program prints the nodes in the order of the list. FIRST_NODE points to the first node of the list. Variable names that store references to nodes are prefixed by 'node_'.

node_current=FIRST_NODE
while node_current!=NIL
    node_current.print()
node_nurrent=node_current.next()

This algorithm calls of the medthod next n-times and there is one variable that can hold a reference to a node.

To print the k-th node of the list one can traverse the list from the start node to the k-th node in k steps. So to print the list in reverse order the following algorithm works

node_first=FIRST_NODE
node_last=NIL
while node_last!=node_first
    node_current=node_first  
    while node_current!=node_last:
        node_previous=node_current
        node_current=node_current.next()
    node_previous.print()
    node_last=node_previous

It needs about $\frac{n^2}{2}$ calls of method next and needs 4 variables that can hold a reference to a node: node_first (the first node of the list), node_last (the last node that was printed), node_current (the node that is currently investigated) , node_previous (the predecessor of node_current)

It can be shown that there are algorithms that need about $O(n^{\frac{1}{k}})$ space and $O(n)$ time for an arbitrary choosen k from {2,3,4,...} to print a single-linked list in reversed order. It is also possible to do this in $O(\log n)$ space and $O(n \log n)$ time. This can be found here

Can one do this better?

My question: Is there an algorithm with $O(1)$ space complexity and $O(n)$ time complexity that prints such a list in reverse order?


Please note that the definition of the problem excludes an algorithm that prints a list in reversed order in linear time with $O(1)$ space for node references while changing the references of the list:

The list is traversed form start to end and the references are reversed during this traversal: the reference from a node to its successor is overwritten by a reverence to its predecessot. If on arrives at the and of the list is straersed form the former end (which is now the start) to the former start (which is now the end) and the nodes are printed.

$\endgroup$
  • $\begingroup$ I'd say no, because it sounds very similar to palindromes on a TM $\endgroup$ – adrianN Jan 16 '17 at 8:12
  • $\begingroup$ @adrianN THank you for this hint. It will take some time until I have analyzed this. $\endgroup$ – miracle173 Jan 16 '17 at 8:28
  • $\begingroup$ Can I have a different definition of next() ? Reason, if a singly linked list is using an XOR Linked List encoding , forward and reverse can be done Once started, going forward or reverse is easy. $\endgroup$ – Phillip Williams Jun 20 '17 at 22:01
  • $\begingroup$ @PhillipWilliams No. I am aware of this smart method. But I am not interested in how a double linked list can be implemented space efficiently- $\endgroup$ – miracle173 Jun 20 '17 at 22:45
  • $\begingroup$ After re-looking at you message, you already have a solution, that you did for O(n) you provided a link to here $\endgroup$ – Phillip Williams Jun 21 '17 at 5:31
3
$\begingroup$

That no such algorithm exists is a classical result attributed to Paterson and Hewitt, though they offer no proof. Swamy and Savage do offer a proof, determining the optimal running time as a function of the memory usage $p$ (number of pointers, roughly) when $p = O(\log n)$, showing that it is $\Theta(pn^{1+1/p})$. In particular, if $p$ is constant then the optimal running time is $\omega(n)$.

$\endgroup$
3
$\begingroup$

No, there is no such algorithm. This is proved in Theorem 2 of "Almost Optimal Hash Sequence Traversal" by Coppersmith and Jakobsson.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.