C, чтобы сделать вторую копию связанного списка

Я писал код C, чтобы скопировать содержимое связанного списка в другой список. Я хочу знать, есть ли более эффективный способ сделать это.

Что лучше?

struct node *copy(struct node *start1) { struct node *start2=NULL,*previous=NULL; while(start1!=NULL) { struct node * temp = (struct node *) malloc (sizeof(struct node)); temp->info=start1->info; temp->link=NULL; if(start2==NULL) { start2=temp; previous=temp; } else { previous->link=temp; previous=temp; } start1=start1->link; } return start2; } 

ИЛИ ЖЕ

 struct node *copy(struct node *start1) { if(start1==NULL) return; struct node *temp=(struct node *) malloc(sizeof(struct node)); temp->info=start1->info; temp->link=copy(start1->link); return temp; } 

Для копирования одного связанного списка в другой связанный список у вас нет другого варианта, кроме как выполнить итерацию по одному и сохранить значения ко второму в общем числе времени O(n) . Вы уже это делаете. Нет лучшего способа сделать это, если между элементами, которые хранятся, не существует какой-либо связи.

Рекурсивное решение может быть лучше смотреть, но на самом деле оно будет менее эффективным .

Изменить: для измененного вопроса

Итеративная версия лучше .

Примечание: LOC не имеет прямого отношения к эффективности.

Не переходя рекурсивный, речь идет о самом компактном, который вы можете получить:

 struct node *copy(struct node *org) { struct node *new=NULL,**tail = &new; for( ;org; org = org->link) { *tail = malloc (sizeof **tail ); (*tail)->info = org->info; (*tail)->link = NULL; tail = &(*tail)->link; } return new; } 

Для скорости , на самом деле, может быть лучший способ сделать это. Как всегда, единственный реальный способ сказать – сравнить его.

  • В зависимости от относительной стоимости итерации
    • (что само по себе зависит от того, как и в каком порядке вы выделили свои узлы, а также в кеше и архитектуре памяти)
  • по сравнению с бесплатным распределением магазинов
    • (что может зависеть от того, в каком состоянии находится ваша куча, сколько других streamов, возможно, будет иметь к нему доступ, статуса физической памяти в ОС хоста и т. д.),
  • это может быть быстрее:

    • потратить одну итерацию, считая длину исходного списка

       int len = 0; for (start2 = start1; start2 != NULL; start2 = start2->link) ++len; 
    • выделить место для всех необходимых узлов в одном блоке

       struct node *temp = malloc(len * sizeof(*temp)); 
    • а затем провести вторую итерацию, связывающую ваш массив узлов

       int i = 0; for (start2 = start1; start2 != NULL; start2 = start2->link) { temp[i].info = start2->info; temp[i].link = &temp[i+1]; } temp[len-1].link = NULL; 

Как я уже сказал, я не обещаю, что это будет быстрее (и это, безусловно, уродливее), но это может быть в некоторых системах с некоторыми компиляторами при некоторых условиях. Конечно, это не стартер, если остальная часть вашего кода предполагает, что вы можете free отдельные узлы по своему усмотрению.


Для элегантности , естественно, побеждает recursion.

Простой итеративный подход, как правило, будет хорошим компромиссом, хотя и между элегантным, но может взорваться, если у вас нет привлекательного компилятора TCO-ing и выше, что, откровенно говоря, немного уродливо и выиграет от объяснительного комментария.