Thread: Efficiently adding to the end of a linked ist

Hey,

I have a code that works fine, but I have a question about efficiency.

Here is a snippet of my code

Code:

void insert_at_end ( listNode * ptr, int data )
{
listNode temp;
temp=*ptr;


if(*ptr==NULL)
{


temp=malloc(sizeof(lNode));
temp->n=data;
temp->next=NULL;
*ptr=temp;
return;
}
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=malloc(sizeof(lNode));
temp->next->n=data;
temp->next->next=NULL;
temp=temp->next;


}

What this does it gets the head of the linked list, goes until the end, and then tacks on another node. I noticed that this has O(N) complexity, and will be super inefficient if I have a large list(like a billion nodes or something).

Is there a more efficient way of adding at the end, WITHOUT using a tail pointer? I know it could be done in O(1) time with a tail pointer, but I'm not sure I'll be able to use tail pointers in labs and such.

Thanks!
Thanks!

Nope. If all you have is the head, you're stuck with O(n). If you're prevented from using a tail pointer, you might make a small comment in the code describing the relative inefficiency of going through the entire list vs using a pointer to the end. If you're lucky your instructor will appreciate that you noticed such a detail.