C program to make a second copy of a linked list

Question

I was writing a C code to copy the contents of a Linked List onto another list. I want to know if there is a more efficient way of doing this.

Which is better?

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;
}

OR

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;
}

Are you looking for runtime efficiency, or a more compact/elegant way of doing this? — RonaldBarzell, Nov 29 '12 at 19:28
Recursively doing it would be very elegant, but you have to watch out lest you STACK OVERFLOW. Heheehehe, the puns write themselves today. Seriously though, you can only recurse so far unless you are using a tail recursive language, which C is not. — RonaldBarzell, Nov 29 '12 at 19:33
@user1161318 Real men use `goto` for recursion ;-) Although, certain C compiler implementations (i.e. GCC with extensions?) [can optimize for TCO](http://stackoverflow.com/questions/34125/which-if-any-c-compilers-do-tail-recursion-optimization) in certain cases .. but it has to be TCO'able to start. — , Nov 29 '12 at 19:34
Upvoted for the fact that you mentioned gcc possibly doing TCO. I remember someone noting this over a decade ago. Kudos! Alas, as it isn't standard behavior across compilers, one should not rely on it. — RonaldBarzell, Nov 29 '12 at 19:37
the recursive way is slower. because there is a function call which take more time comparing the loop — MOHAMED, Nov 29 '12 at 19:38
@MohamedKALLEL unless it does get TCO'd, of course. Even then, it's better to profile than to conjecture — Useless, Nov 29 '12 at 19:42

axiom · Accepted Answer · 2012-11-29T19:42:27.023

6

For copying one linked list to another linked list, you have no other option but to iterate through one and keep copying the values to the second, in a total of O(n)time. You are already doing it. There is no way to do better unless there is some relation among the elements that are stored.

A recursive solution may be better to look at, but it will in fact be less efficient.

Edit: For the changed question

The Iterative version is better.

Note : LOC has no direct relation with efficiency.

edited Nov 29 '12 at 19:42

answered Nov 29 '12 at 19:31

axiom

8,765
3
36
38

Is it possible to reduce the number of lines of code at least? – user Nov 29 '12 at 19:32
Lines of code has nothing to do with efficiency. Your question was on improving efficiency and i think i have answered it :) – axiom Nov 29 '12 at 19:34
you can reduce the number of lines. see my answer – MOHAMED Nov 29 '12 at 19:44
But it won't necessarily make it efficient. Plus see my comment. – axiom Nov 29 '12 at 19:47

score 1 · Answer 2 · answered Nov 29 '12 at 19:40

Without going recursive, this is about the most compact you can get:

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;
}

score 1 · Answer 3 · answered Nov 29 '12 at 19:53

For speed, there may in fact be a better way of doing it. As always, the only real way to tell is to benchmark it.

Depending on the relative cost of iteration
- (which may itself depend on how and in what order you allocated your nodes, as well as cache and memory architecture)
versus free store allocation
- (which may depend on what state your heap is in, how many other threads are likely to be accessing it, the physical memory status in the host OS, etc.)

it may be faster to:

spend one iteration counting the length of the source list

int len = 0;
for (start2 = start1; start2 != NULL; start2 = start2->link)
    ++len;

allocate space for all required nodes in a single block
```
struct node *temp = malloc(len * sizeof(*temp));
```

and then spend a second iteration linking up your array of nodes

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;

As I say, I'm not promising it will be faster (and it's certainly uglier), but it may be on some systems, with some compilers, under some conditions. Of course, it's a non-starter if the rest of your code assumes you can free individual nodes at will.

For elegance, recursion naturally wins.

The simple iterative approach is usually going to be a good compromise, though, between elegant but might explode unless you have a fancy TCO-ing compiler and the above, which is frankly a bit ugly and would benefit from an explanatory comment.

Well I was writing a program for this question because it was in the exercise of my Data Structures Text Book. Thanks for the insight on the efficiency though! :) — user, Nov 29 '12 at 19:58

C program to make a second copy of a linked list

3 Answers3

Linked