Linked Lists: Inserting at the end using last pointer.

Question

I'm learning linked lists, and want to know whether the following program (basically InsertAtEnd function) I've made for inserting elements at the end of the list is correct.

The basic idea is that *HEAD points to the first element of the list and *LAST points to the last element. This saves the time and calculations in traversing to the last element of the list and then adding elements.

#include<stdio.h>
#include<stdlib.h>

// Structure for the list element/node
struct node 
{
 int data; // Stores the data
 struct node *next; // Points to the next element in the list.
};

int InsertAtEnd(struct node **, struct node **, int); /*Declaration of the function which 
                                                    inserts elements at the end.*/

int main()
{
 struct node *HEAD=NULL; //Points to the first element in the list.
 struct node *LAST=NULL; //Points to the last element in the list.
 int i=1;

 for(i=1;i<11;i++)
   {
     InsertAtEnd(&HEAD,&LAST,i);
   }
 }

// Function to insert element at the end.
int InsertAtEnd(struct node **headref,struct node **lastref,int i)
 {
   struct node *newnode=malloc(sizeof(struct node)); /*Allocates memory for the newnode 
                                                     and store the address in pointer 
                                                     newnode*/
   newnode->data=i; // Assign value to the data variable of the newnode.
   newnode->next=NULL; // Assign NULL to the next pointer of the newnode.

   if(*headref==NULL) //Checks if the list is empty.
    {
      *headref=newnode; // Places the address of the new node in HEAD pointer.
      *lastref=newnode; // Places the address of the new node in LAST pointer.

       return 0; //Exit function
    }

/* If the list is not empty, then make the next pointer of the present last node point to the new node*/

   (*lastref)->next=newnode;

   *lastref=(*lastref)->next; // Increment LAST to point to the new last node.

    return 0;
}

The questions that I want to specifically ask are:

a) Is the above code for adding elements at the end (i.e InsertAtEnd function) correct? (Note: I tested it on my machine and it works as expected. But I still want to confirm from you people)

b)Is the code (InsertAtEnd function) efficient?

c)Will the efficiency of the code (InsertAtEnd function) be affected if I try to make a longer list.

d)Are there more efficient and simple algorithms to insert elements at the end? Can you direct me to them?

Answer 1

This code is invariant with the size of the list (other than the special case for empty), i.e. it's a constant-time algorithm. So it's probably pretty hard to come up with a more-efficient insertion algorithm.

However, the only part that might be improved is the use of malloc(). It looks like you're allocating each node individually. If you're prepared to use more memory than you really need, you might consider allocating multiple nodes at once, so you have fewer calls to malloc(). So when you try to create a node, it first checks whether you have any free nodes left in the pool. If yes, then simply hook up the pointers. If not, you'll need to allocate a new pool. Clearly, this will require more complex code.

Answer 2

a) It seems correct

b) It is. You could make the function return void, because you don't need that int return value

c) No. In other words the execution time is constant.

d) malloc takes time. You could use a buffering technique, to malloc a chunk of nodes in advance and then take the next node from the buffer. When the buffer becomes empy, allocate another chunk. The chunk dimensions could be configured or even (complex) computed using statistical algorithms.

Moreover, you don't check for malloc's NULL return, but it could fail.

Answer 3

a) The result of malloc is not checked. It can return NULL under low-memory conditions, causing a crash. The rest of the algorithm is correct, I believe.

B+C+D) It is very efficient; it is O(1) mening that the time it takes to insert the LAST element is constant. In fact I can not think of an simpler and more efficient algorithm.

Answer 4

a) Yes, it should work (assuming that your list never gets corrupted and has headref != NULL but lastref == NULL).

What's the point of the return value if it's always 0?

b) Other than it allocating memory for every node, sure. That's a design decision on your end, but a different solution would be a lot more complex and beyond the scope of this exercise.

As for the function itself - the nice thing about linked lists is that they're O(1). Now removing an element is a different matter, that will be slower unless you have a double-linked list.

c) No. It's O(1). As you see, there are no loops or anything involved, you do the exact same steps regardless of whether there's 5 or 5000 elements in the list.

d) You can avoid the check for the list being empty by using a sentinel, i.e. a dummy node in lieu of the headref. You just place a node somewhere in memory and set lastref to it. Now you don't need to have to handle having an empty list as a special case.

Answer 5

a) I think your code is correct in the sense that it does what you expect it to do. You might want to check the return value of malloc.

b) Your code is in my opinion also efficient. The only thing I could think of is the line *lastref=(*lastref)->next; which I would replace by *lastref=newnode;. But I think this will be optimized by almost every compiler automatically.

c) Your method has constant runtime (O(1)), so adding to a bigger list will not change runtime. However, traversing the list might be faster if the elements are stored continuously in memory.

d) I don't think that insertAtEnd can be implemented seriously faster. You could try to store elements continously in memory, and check for return of malloc.

The only thing I personally do when implementing such stuff is:

• create an own struct for the whole linked-list-data-structure (holding size and head- and lastElement-pointers)

• I would not restrict the list to hold integers but arbitrary elements (thus void*s)

Answer 6

One more thing I would like to ask is. You said that I don't need a return statement. Then how will I exit the "if" statement? I mean, if I pass an empty list then the if statement is executed, but if I don't return 0 then the next two statements will also be executed. Isn't it? I think I should just place the last two lines in an else block. Will that suffice? or am I making a logical error?

Answer 7

Sorry, this doesn't answer the question but I thought you might find it useful. I offer a slight change of approach:

int InsertAtEnd(struct node ***, int); /*Declaration of the function which 
                                         inserts elements at the end.*/

struct node *HEAD=NULL; //Points to the first element in the list.
struct node **LAST=&HEAD; //Points to the last (NULL) *pointer* in the list.

// Function to insert element at the end.
int InsertAtEnd(struct node ***lastrefref,int i) // no need to pass HEAD
{
    struct node *newnode=malloc(sizeof(struct node)); /*Allocates memory for the newnode 
                                                        and store the address in pointer 
                                                        newnode*/

    // And here we should be checking for errors...

    newnode->data=i; // Assign value to the data variable of the newnode.
    newnode->next=NULL; // Assign NULL to the next pointer of the newnode.

    **lastrefref = newnode; // Put new element at end of list
    *lastrefref=&(newnode->next); // Update last pointer location
}

The calling convention loses an argument, and there's no conditional required. If you want quick access to the last list element this loses out a little because it's not as simple.

struct <anything> ***

is starting to get silly, mind.