insert element at nth position in the linked list - C

Question

my program shows list is empty. I think I'm making mistake on re-linking the nodes to the head. Help me figure it out.

void insert(struct node** headRef, int index, int Data)
{
  int i, distanceFromHead = 1;
  struct node* head = *headRef;
  struct node* temp1 = (struct node*)malloc(sizeof(struct node)); //node to be inserted.
  temp1->data = Data;
  if(index == 0)
  {
    temp1->next = head;
    head = temp1;
    return;
  }
  while(head != NULL)
  {
    if(distanceFromHead == index)
    {
        temp1->next = head->next;
        head->next = temp1;
        *headRef = head;
        return;
    }
    head = head->next;
    distanceFromHead++;
  }

}

@pat initially the `head` is having the address of first node. When I'm adding the node at position 1, `temp1->next = head` assigns the address of 1st node (initially stored in head) to the 'next' field of the "node to be inserted". As the new node inserted is the 1st node of the list, now the address of this new node should be assigned to head. So `head = temp1` assigns the address of `temp1` node(the 1st node) to the head — surjit, May 26 '17 at 04:55
`head` is a local variable of the function and dies when the function returns. You should be assigning to `*headRef` — pat, May 26 '17 at 04:57
Note that if you're asked to add a node at position 10 in a list with 3 nodes, the code leaks the newly allocated node. — Jonathan Leffler, May 26 '17 at 05:08
yeah.. Thanks. It's working.. But one thing I don't understand. Inside `while` I'm using `head`, not `headRef` but it's still working. How?? — surjit, May 26 '17 at 05:16

score 0 · Answer 1 · edited May 26 '17 at 05:06

0

You're using head to iterate through the linked list and if index matched with distance then updating headref.

Problem is *headRef = head in while..if

And in if(index == 0) assign temp1 to *headref i.e. *headref=temp1

edited May 26 '17 at 05:06

Jonathan Leffler

730,956
141
904
1,278

answered May 26 '17 at 04:40

Pravin

371
1
15

that line `*headRef = head;` doesn't make any difference I think.. if I remove it, still problem remains the same.. when I use function of signature `struct Node* insert(Node *head,int index, int data)` code works fine.. I'm having problem when I pass the head as refference – surjit May 26 '17 at 04:47
1

Yes, that's the point. Your are updating head reference and after insert head referring to nth node or NULL – Pravin May 26 '17 at 05:01
@Jonathan Leffler how can I prevent memory leak in this program? – surjit May 26 '17 at 05:35
@Surjit If you are running the application on Linux you can use Valgrind to help you in finding memory leaks. For windows you can have a look at [this](https://stackoverflow.com/questions/14235858/free-application-to-check-memory-leaks-in-windows-x64) discussion. – AmeyaVS May 26 '17 at 05:44
What about Windows?? – surjit May 26 '17 at 05:46
@suraj As mentioned by @Jonathan memory allocated to temp1 did not gets freed if `while(head != NULL)` hits first instead of `if(distanceFromHead == index)`. Handle all cases & do code walk through or debug code, – Pravin May 26 '17 at 05:51
@Pravin what to do to prevent memory leak in this program.. how to free temp1 for invalid index? – surjit May 26 '17 at 07:08
After `while` you can add check `if(head==NULL && distance – Pravin May 26 '17 at 07:13
@surjit : make sure you always append the new node to the list if you reach the end before reaching the position. – Jonathan Leffler May 26 '17 at 07:24

score 0 · Accepted Answer · answered May 26 '17 at 09:35

Your have two conditions:

finding the postion for insertion in the Linked list
not falling off the end of the Linked List

And, of course, you have to assign to *headRef, not to some local pointer variable. And you should not call malloc before you are absolutely sure you really need the memory.

You can combine the two conditions in a single loop:

void insert1(struct node **headRef, int index, int Data)
{
  struct node *temp1;
  int distanceFromHead = 0;

  for( ; *head; head = &(*head)->next) {
    if(distanceFromHead == index) break;
    distanceFromHead++;
  }

  if (distanceFromHead != index) return; // index not found: list too short

  temp1 = malloc(sizeof *temp1); //node to be inserted.
  temp1->data = Data;
  temp1->next = *head;
  *head = temp1;
}

You dont need the distanceFromHeadvarable; you could just as well decrement the index:

void insert2(struct node **headRef, int index, int Data)
{
  struct node *temp1;

  for( ; *head; head = &(*head)->next) {
    if(!index) break;
    index--;
  }
  if (index) return; // index not found: list too short

  temp1 = malloc(sizeof *temp1); //node to be inserted.
  temp1->data = Data;
  temp1->next = *head;
  *head = temp1;
}

Now, the test for index!=0 is repeated after the loop. This can be avoided by moving the insertion inside the loop, and jumping out afterwards:

void insert3(struct node **headRef, int index, int Data)
{

  for( ; *head; head = &(*head)->next) {
    struct node *temp1;
    if(index--) continue;

    temp1 = malloc(sizeof *temp1); //node to be inserted.
    temp1->data = Data;
    temp1->next = *head;
    *head = temp1;
    break; // or : return;
  }

  return;
}

insert element at nth position in the linked list - C

2 Answers2