Efficiently adding to the end of a linked ist

This is a discussion on Efficiently adding to the end of a linked ist within the C Programming forums, part of the General Programming Boards category; Hey, I have a code that works fine, but I have a question about efficiency. Here is a snippet of ...

  1. #1
    Registered User
    Join Date
    Oct 2011
    Posts
    13

    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!

  2. #2
    cas
    cas is offline
    Registered User
    Join Date
    Sep 2007
    Posts
    987
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. adding to linked list
    By camel-man in forum C Programming
    Replies: 15
    Last Post: 10-09-2011, 02:13 PM
  2. help with adding item to linked list in C
    By omega666 in forum C Programming
    Replies: 6
    Last Post: 04-04-2011, 09:46 PM
  3. Adding nodes into linked list
    By Suchy in forum C++ Programming
    Replies: 1
    Last Post: 04-29-2007, 04:03 PM
  4. Me again! This time adding to the linked list
    By Welshy in forum C++ Programming
    Replies: 2
    Last Post: 07-13-2005, 08:10 AM
  5. Adding a node to a linked list
    By slopeski007 in forum C Programming
    Replies: 2
    Last Post: 02-01-2003, 11:31 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21