Пространственный анализ сложности функции обхода связанного списка в обратном порядке? - PullRequest
Новая
       30

Пространственный анализ сложности функции обхода связанного списка в обратном порядке?

0 голосов
/ 23 октября 2019

Учитывая узел со следующей структурой: 

typedef struct listElementStruct{
  void* data;
  size_t size; //size of data not list
  struct listElementStruct* next;
  void (*print_func)(void*); //pointer to one of the custom print functions
} listElement;

Имеет ли эта функция постоянную память O (1) или линейную O (n) сложность пространства? 

void reverse_traverse(listElement* start){

  listElement* current = start;
  int size_of_list=0;

  while(current != NULL){
      current=current->next;
      size_of_list++;
  }

  int nextVisit = size_of_list;

  While(nextVisit>=0){
     current = start;
     for(int i=0;i<nextVisit;i++){
         current = current->next;
     } 
     current->print_func(current->data);
     nextVisit--;
  }
}
...