Inserting a node into a linked list c

Question

Okay This is the code for insering a node into a linked list.

vec_store holds seq and size. Variable seq holds the vectors and a pointer. and vec_mag takes magnitude of vectors.

For some reason, the (vec_mag(v)<=vec_mag(temp2->next->data)) doesn't work which is the last condition.

Any1 can solve the problem? By the way this is C code.

vector last_vec(vec_store s){  
 node temp3;  
 temp3=s->seq;  
 while (temp3->next!=NULL)  
  {temp3 = temp3->next;  
 }  
  return temp3->data;  
}  


void insert_vec(vec_store s, vector v){  
node temp1,temp2,temp4;  
int i;  
temp1 = malloc(sizeof (struct node_record));  

if(s->seq==NULL){  
 s->seq=temp1;  
 temp1->next=NULL;  
 temp1->data=v;  
 s->size++;  
 printf("1\n");  
}  
else if(vec_mag(v)<=vec_mag(s->seq->data)){  
 s->size++;  
 temp2=s->seq;  
 temp1->data=v;  
 temp1->next=temp2;  
 s->seq=temp1;  
 printf("2\n");  
}  

else if(vec_mag(v)>=vec_mag(last_vec(s)))  
{  s->size=s->size+1;   
  temp4=s->seq;  
  while (temp4->next!=NULL)  
  {temp4 = temp4->next;  
  }  
  temp1->next=NULL;  
  temp1->data=v;  
  temp4->next=temp1;  
  printf("3\n");  
}  
else{  
 temp2 = s->seq;  
 temp4 = s->seq;  
 for(i=0;i<s->size-1;i++){  
  if(vec_mag(v)<=vec_mag(temp2->next->data)){     
  temp1->data = v;  
  temp1->next = temp2->next;  
  temp2->next=temp1;  
  printf("4\n");  
  s->size++;  
  break;  
  }    
 }  

}  
}

Answer 1

The problem is that in that loop, you don't actually move along the list at all.

Answer 2

"Anon" is correct - you loop the variable i through the size of the list, you don't shift the pointers before the comparison.

But there are more issues here.

I'm not sure what your data structures look like since you haven't posted their source, but I'm going to assume that you mean the nodes (temp1 - temp4) to be node pointers instead of full instances of the structures.

This is a good effort, but there are excessive variables used, needless computations and unnecessary copy-by-value's. Nothing computationally wrong with that if you get the result you were looking for, but I don't think it's doing exactly what you'd want it to and it makes it a bit harder to trace/maintain. Sometimes it makes a world of difference to set things up in logical blocks with a couple of comments.

I haven't tried to compile this (try to just read the logic and comments), but you might have more luck with something like the following (apologies for the c++ comments in C code):

// construct the node and its data first (except for the next pointer)
// - it's going to be inserted no matter what the list is like
node* inserted = (node*) malloc(sizeof(struct node));
inserted->data = v;
// store the vector magnitude so you don't have to compute it on every comparison
double v_mag = vec_mag(v);

// Case 1 - empty list
if (s->seq == NULL)
{
    inserted->next = NULL;
    s->seq = inserted;
}
// Case 2 - in case there's only one element in the list
// (this is me being too lazy to work this step into the main logic in case 3)
else if (s->seq->next == NULL)
{
    t1_mag = vec_mag(s->seq->data);
    if (v_mag <= t1_mag)
    {
     //insert
     inserted->next = s->seq;
     s->seq = inserted;
    }
    else
    {
     //append
     inserted->next = NULL;
     s->seq = inserted;
    }
}
// Case 3 - there are at least 2 elements in the list
else
{
    // set the temporary nodes to the first 2
    node* temp1 = s->seq;
    node* temp2 = temp1->next;
    // store their magnitudes
    double t1_mag = vec_mag(temp1->data);
    double t2_mag = vec_mag(temp2->data);
    // while we aren't at the list, and we aren't at a spot where the node should be inserted
    while (temp2 != NULL && !(v_mag >= t1_mag && v_mag <= t2_mag ))
    {
     // shift the two to the next in the line
     temp1 = temp2;
     // no need to recompute this magnitude from the last step - just copy it
     t1_mag = t2_mag;
     temp2 = temp2->next;
     t2_mag = vec_mag(temp2->data);
    }
    // if we can trust the integrity of the list, either temp2 is null (at the end of the list),
    // or another node (we found a suitable place to insert).
    // Either way, just blindly insert the node.
    inserted->next = temp2;
    temp1->next = inserted;
}
// Node has been inserted
s->size++;