reverse print an immutable linked list with less than O(n) space

Question

Working on this problem, and my ideas is doing recursive and during each recursion, reverse print 2nd half of the linkedlist, then reverse print 1st half of the linkedlist. So that additional space is O(log n) -- which is for additional space for recursive stack, but it is more than O(n) for time (O(n log n) - combined calls on each of (log n) levels of recursion iterate whole list to cut each portion in half).

Are there algorithms that achieve the same goal - reverse print an immutable single linked list with less than O(n) space and at most O(n) time?

Source code (Python 2.7):

class LinkedListNode:
    def __init__(self, value, next_node):
        self.value = value
        self.next_node = next_node
    @staticmethod
    def reverse_print(list_head, list_tail):
        if not list_head:
            return
        if not list_head.next_node:
            print list_head.value
            return
        if list_head == list_tail:
            print list_head.value
            return
        p0 = list_head
        p1 = list_head
        while p1.next_node != list_tail and p1.next_node.next_node != list_tail:
            p1 = p1.next_node
            p1 = p1.next_node
            p0 = p0.next_node
        LinkedListNode.reverse_print(p0.next_node, list_tail)
        LinkedListNode.reverse_print(list_head, p0)
if __name__ == "__main__":
    list_head = LinkedListNode(4, LinkedListNode(5, LinkedListNode(12, LinkedListNode(1, LinkedListNode(3, None)))))
    LinkedListNode.reverse_print(list_head, None)

Answer 1

This is an O(n) time and O(sqrt(n)) space algorithm. In the second part of the post it will be extended to a linear time and O(n^(1/t)) space algorithm for an arbitrary positive integer t.

High-level idea: Split the list into sqrt(n) many (almost) equal-sized parts. Print the parts one after the other in reverse order using a naive linear-time, linear-space method, from the last to the first.

To store the start nodes of the parts we need an array of size O(sqrt(n)). To revert a part of size approximately sqrt(n) the naive algorithm needs an array to store references to the node of the part. So the array has a size of O(sqrt(n).

---

One uses two arrays (lsa and ssa)of size k=[sqrt(n)]+1 =O(sqrt(n)) (lsa ... large step array, ssa .. small step array)

Phase 1: (if the size of the linked list is not known find out n, its length): move through the list from start to end and count the elements of the list, this needs n steps

Phase 2: Store each k-th node of the single linked list in the array lsa. This needs n steps.

Phase 3: Process the lsalist in reverse order. Print each part in reverse order This takes also n steps

So the runtime of the algorithm is 3n = O(n) and its pace is about 2*sqrt(n) = O(sqrt(n)).

This is a Python 3.5 implementation :

import cProfile
import math

class LinkedListNode:
    def __init__(self, value, next_node):
        self.value = value
        self._next_node = next_node

    def next_node(self):
        return(self._next_node)

    def reverse_print(self):
        # Phase 1
        n=0
        node=self
        while node:
            n+=1
            node=node.next_node()
        k=int(n**.5)+1

        # Phase 2
        i=0
        node=self
        lsa=[node]
        while node:
            i+=1
            if i==k:
                lsa.append(node)
                i=0
            last_node=node
            node=node.next_node()
        if i>0:
            lsa.append(last_node)

        # Phase 3
        start_node=lsa.pop()
        print(start_node.value)
        while lsa:
            last_printed_node=start_node
            start_node=lsa.pop()
            node=start_node
            ssa=[]
            while node!=last_printed_node:
                ssa.append(node)
                node=node.next_node()

            ssa.reverse()
            for node in ssa:
                print(node.value)


    @classmethod
    def create_testlist(nodeclass, n):
        ''' creates a list of n elements with values 1,...,n'''
        first_node=nodeclass(n,None)
        for i in range(n-1,0,-1):
            second_node=first_node
            first_node=nodeclass(i,second_node)
        return(first_node)

if __name__ == "__main__":
    n=1000
    cProfile.run('LinkedListNode.create_testlist(n).reverse_print()')
    print('estimated number of calls of next_node',3*n)

It prints the following output (at the end is the output of the profiler that shows the number of function calls):

>>> 
 RESTART: print_reversed_list3.py 
1000
999
998
...
4
3
2
1
         101996 function calls in 2.939 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    2.939    2.939 <string>:1(<module>)
     2000    0.018    0.000    2.929    0.001 PyShell.py:1335(write)
        1    0.003    0.003    2.938    2.938 print_reversed_list3.py:12(reverse_print)
        1    0.000    0.000    0.001    0.001 print_reversed_list3.py:49(create_testlist)
     1000    0.000    0.000    0.000    0.000 print_reversed_list3.py:5(__init__)
     2999    0.000    0.000    0.000    0.000 print_reversed_list3.py:9(next_node)    
   ...

estimated number of calls of next_node 3000
>>>     

The number of calls to next_node() is 3000 as expected

---

Instead of using the naive O(m) space algorithm to print the sublist of length m in reversed order one can use this O(sqrt(m)) space algorithm. But we must find the right balance between the number of sublists and the length of the sublists:

Phase 2: Split the simple linked list into n^(1/3) sublists of length n^(2/3). The startnodes of these sublists are stored in an array of length n^(1/3)

Phase 3: Print each sublist of length m=n^(2/3) in reversed order using the O(sqrt(m)) space algorithm. Because m=n^(2/3) we need m^(1/2)=n^(1/3) space.

We now have a O(n^(1/3)) space algorithm that needs 4n time and so is still O(n)

We can repeat this again by splitting into n^(1/4) sublists of length m=n^(3/4) tha are processed by the O(m^(1/3)) = O(n^(1/4)) space algorithm that needs 5n=O(n) time.

We can repeat this again and again and arrive a the following statement:

The immutable simply linked list of size n can be printed in reversed order using t*n^(1/t)=O(n^(1/t)) space and (t+1)n =O(n) time where t is an arbitrary positive integer

---

If one does not fix t but selects t depending from n such that n^(1/t)) about 2, the smallest useful array size, then this results in the O(nlog(n)) time and O(log(n)) space algorithm described by the OP.

If one chooses t=1 this results in the O(n) time and O(n) space naive algorithm.

---

Here is an implementation of the algorithm

import cProfile
import math
import time

class LinkedListNode:
    '''
    single linked list node
    a node has a value and a successor node
    '''
    stat_counter=0
    stat_curr_space=0
    stat_max_space=0
    stat_max_array_length=0
    stat_algorithm=0
    stat_array_length=0
    stat_list_length=0
    stat_start_time=0

    do_print=True
    def __init__(self, value, next_node):
        self.value = value
        self._next_node = next_node


    def next_node(self):
        self.stat_called_next_node()
        return(self._next_node)

    def print(self):
        if type(self).do_print:
            print(self.value)

    def print_tail(self):
        node=self
        while node:
            node.print()
            node=node.next_node()

    def tail_info(self):
        list_length=0
        node=self
        while node:
            list_length+=1
            last_node=node
            node=node.next_node()
        return((last_node,list_length))


    def retrieve_every_n_th_node(self,step_size,list_length):
        ''' for a list a of size list_length retrieve a pair there the first component 
        is an array with the nodes 
        [a[0],a[k],a[2*k],...,a[r*k],a[list_length-1]]]
        and the second component is list_length-1-r*k
        and 
        '''
        node=self
        arr=[]
        s=step_size
        index=0
        while index<list_length:
            if s==step_size:
                arr.append(node)
                s=1
            else:
                s+=1
            last_node=node
            node=node.next_node()
            index+=1
        if s!=1:
            last_s=s-1
            arr.append(last_node)
        else:
            last_s=step_size
        return(arr,last_s)


    def reverse_print(self,algorithm=0):
        (last_node,list_length)=self.tail_info()
        assert(type(algorithm)==int)
        if algorithm==1:
            array_length=list_length
        elif algorithm==0:
            array_length=2
        elif algorithm>1:
            array_length=math.ceil(list_length**(1/algorithm))
            if array_length<2:
                array_length=2
        else:
            assert(False)
        assert(array_length>=2)
        last_node.print()
        self.stat_init(list_length=list_length,algorithm=algorithm,array_length=array_length)
        self._reverse_print(list_length,array_length)
        assert(LinkedListNode.stat_curr_space==0)
        self.print_statistic()



    def _reverse_print(self,list_length,array_length):
        '''
        this is the core procedure  of the algorithm
            if the list fits into the array
                store it in te array an print the array in reverse order
            else
                split the list in 'array_length' sublists and store
                    the startnodes of the sublists in he array
                _reverse_print array in reverse order
        '''
        if list_length==3 and array_length==2: # to avoid infinite loop
            array_length=3
        step_size=math.ceil(list_length/array_length)
        if step_size>1: # list_length>array_length:
            (supporting_nodes,last_step_size)=self.retrieve_every_n_th_node(step_size,list_length)
            self.stat_created_array(supporting_nodes)
            supporting_nodes.reverse()
            supporting_nodes[1]._reverse_print(last_step_size+1,array_length)
            for node in supporting_nodes[2:]:
                node._reverse_print(step_size+1,array_length)
            self.stat_removed_array(supporting_nodes)
        else:
            assert(step_size>0)
            (adjacent_nodes,last_step_size)=self.retrieve_every_n_th_node(1,list_length)
            self.stat_created_array(adjacent_nodes)
            adjacent_nodes.reverse()
            for node in adjacent_nodes[1:]:
                node.print()
            self.stat_removed_array(adjacent_nodes)

    # statistics functions

    def stat_init(self,list_length,algorithm,array_length):
        '''
        initializes the counters
        and starts the stop watch
        '''
        type(self)._stat_init(list_length,algorithm,array_length)

    @classmethod
    def _stat_init(cls,list_length,algorithm,array_length):
        cls.stat_curr_space=0
        cls.stat_max_space=0
        cls.stat_counter=0
        cls.stat_max_array_length=0
        cls.stat_array_length=array_length
        cls.stat_algorithm=algorithm
        cls.stat_list_length=list_length
        cls.stat_start_time=time.time()

    def print_title(self):
        '''
        prints the legend and the caption for the statistics values
        '''
        type(self).print_title()

    @classmethod
    def print_title(cls):
        print('   {0:10s} {1:s}'.format('space','maximal number of array space for'))
        print('   {0:10s} {1:s}'.format('',     'pointers to the list nodes, that'))
        print('   {0:10s} {1:s}'.format('',     'is needed'))
        print('   {0:10s} {1:s}'.format('time', 'number of times the method next_node,'))
        print('   {0:10s} {1:s}'.format('',     'that retrievs the successor of a node,'))
        print('   {0:10s} {1:s}'.format('',     'was called'))
        print('   {0:10s} {1:s}'.format('alg',  'algorithm that was selected:'))
        print('   {0:10s} {1:s}'.format('',     '0:   array size is 2'))
        print('   {0:10s} {1:s}'.format('',     '1:   array size is n, naive algorithm'))
        print('   {0:10s} {1:s}'.format('',     't>1: array size is n^(1/t)'))
        print('   {0:10s} {1:s}'.format('arr',  'dimension of the arrays'))
        print('   {0:10s} {1:s}'.format('sz',  'actual maximal dimension of the arrays'))
        print('   {0:10s} {1:s}'.format('n',    'list length'))
        print('   {0:10s} {1:s}'.format('log',    'the logarithm to base 2 of n'))
        print('   {0:10s} {1:s}'.format('n log n',    'n times the logarithm to base 2 of n'))               
        print('   {0:10s} {1:s}'.format('seconds',    'the runtime of the program in seconds'))               

        print()
        print('{0:>10s} {1:>10s} {2:>4s} {3:>10s} {4:>10s} {5:>10s} {6:>5s} {7:>10s} {8:>10s}'
              .format('space','time','alg','arr','sz','n','log', 'n log n','seconds'))

    @classmethod
    def print_statistic(cls):
        '''
        stops the stop watch and prints the statistics for the gathered counters
        '''
        run_time=time.time()-cls.stat_start_time
        print('{0:10d} {1:10d} {2:4d} {3:10d} {4:10d} {5:10d} {6:5d} {7:10d} {8:10.2f}'.format(
            cls.stat_max_space,cls.stat_counter,cls.stat_algorithm,
            cls.stat_array_length,cls.stat_max_array_length,cls.stat_list_length,
            int(math.log2(cls.stat_list_length)),int(cls.stat_list_length*math.log2(cls.stat_list_length)),
            run_time
            ))

    def stat_called_next_node(self):
        '''
        counter: should be called
        if the next node funtion is called
        '''
        type(self)._stat_called_next_node()

    @classmethod
    def _stat_called_next_node(cls):
        cls.stat_counter+=1

    def stat_created_array(self,array):
        '''
        counter: should be called
        after an array was created and filled
        '''
        type(self)._stat_created_array(array)

    @classmethod
    def _stat_created_array(cls,array):
        cls.stat_curr_space+=len(array)
        if cls.stat_curr_space> cls.stat_max_space:
            cls.stat_max_space=cls.stat_curr_space
        if (len(array)>cls.stat_max_array_length):
            cls.stat_max_array_length=len(array)

    def stat_removed_array(self,array):
        '''
        counter: should be called
        before an array can be removed
        '''
        type(self)._stat_removed_array(array)

    @classmethod
    def _stat_removed_array(cls,array):
        cls.stat_curr_space-=len(array)

    @classmethod
    def create_testlist(nodeclass, n):
        '''
        creates a single linked list of
        n elements with values 1,...,n
        '''
        first_node=nodeclass(n,None)
        for i in range(n-1,0,-1):
            second_node=first_node
            first_node=nodeclass(i,second_node)
        return(first_node)

if __name__ == "__main__":
    #cProfile.run('LinkedListNode.create_testlist(n).reverse_print()')
    n=100000
    ll=LinkedListNode.create_testlist(n)
    LinkedListNode.do_print=False
    ll.print_title()
    ll.reverse_print(1)
    ll.reverse_print(2)
    ll.reverse_print(3)
    ll.reverse_print(4)
    ll.reverse_print(5)
    ll.reverse_print(6)
    ll.reverse_print(7)
    ll.reverse_print(0)

And here are some results

   space      maximal number of array space for
              pointers to the list nodes, that
              is needed
   time       number of times the method next_node,
              that retrievs the successor of a node,
              was called
   alg        algorithm that was selected:
              0:   array size is 2
              1:   array size is n, naive algorithm
              t>1: array size is n^(1/t)
   arr        dimension of the arrays
   sz         actual maximal dimension of the arrays
   n          list length
   log        the logarithm to base 2 of n
   n log n    n times the logarithm to base 2 of n
   seconds    the runtime of the program in seconds

     space       time  alg        arr         sz          n   log    n log n    seconds
    100000     100000    1     100000     100000     100000    16    1660964       0.17
       635     200316    2        317        318     100000    16    1660964       0.30
       143     302254    3         47         48     100000    16    1660964       0.44
        75     546625    4         18         19     100000    16    1660964       0.99
        56     515989    5         11         12     100000    16    1660964       0.78
        47     752976    6          7          8     100000    16    1660964       1.33
        45     747059    7          6          7     100000    16    1660964       1.23
        54    1847062    0          2          3     100000    16    1660964       3.02

and

   space      maximal number of array space for
              pointers to the list nodes, that
              is needed
   time       number of times the method next_node,
              that retrievs the successor of a node,
              was called
   alg        algorithm that was selected:
              0:   array size is 2
              1:   array size is n, naive algorithm
              t>1: array size is n^(1/t)
   arr        dimension of the arrays
   sz         actual maximal dimension of the arrays
   n          list length
   log        the logarithm to base 2 of n
   n log n    n times the logarithm to base 2 of n
   seconds    the runtime of the program in seconds

     space       time  alg        arr         sz          n   log    n log n    seconds
   1000000    1000000    1    1000000    1000000    1000000    19   19931568       1.73
      2001    3499499    2       1000       1001    1000000    19   19931568       7.30
       302    4514700    3        100        101    1000000    19   19931568       8.58
       131    4033821    4         32         33    1000000    19   19931568       5.69
        84    6452300    5         16         17    1000000    19   19931568      11.04
        65    7623105    6         10         11    1000000    19   19931568      13.26
        59    7295952    7          8          9    1000000    19   19931568      11.07
        63   21776637    0          2          3    1000000    19   19931568      34.39