Insert from back : Linked List

Question

I read the code from this site: http://www.codeproject.com/Articles/24684/How-to-create-Linked-list-using-C-C, but it gave me segmentation fault and I don't quite get it.

*I modified it to my struct

struct Node
{
    int type;
    char cmd[256];
    struct Node *next;
};

struct Node *head = NULL;

void insert(int val, char arr[])
{
    struct Node *temp1 = (struct Node*)malloc(sizeof(struct Node));
    struct Node *temp2 = (struct Node*)malloc(sizeof(struct Node));
    temp1 = head;
    while(temp1->next != NULL)
        temp1 = temp1->next;

    temp2->type = val;
    strcpy(temp2->cmd, arr);

    temp2->next = NULL;
    temp1->next = temp2;
}

What is wrong with this code?

OK, this problem is solved. Thx Guyz '^'! Do you know by any chance how to put charcters " (ASCII 34) into a printf string? (e.g. if I do printf("Print this "sentence""); it would give me error in sentence, cut I casted another set of "" inside a "". Thx a bunch.

Answer 1

First, you're failing to set the head pointer on initial insert. This can be done with a simple head-check, though it isn't needed if the insertion loop is setup correctly. Second, you're leaking memory. This isn't Java. overwriting a pointer holding the address of a dynamic allocation is as good as throwing memory out the window.

This is one way to do this without burying an if (head == NULL) special case in your insertion code. Contrary to popular opinion, you don't need that special case if you do it like this:

void insert(int val, char arr[])
{
    struct Node **pp = &head;
    while (*pp)
        pp = &(*pp)->next;

    *pp = malloc(sizeof(**pp));
    (*pp)->next = NULL;
    (*pp)->type = val;
    strcpy((*pp)->cmd, arr);
}

Just make sure head is initialized to NULL before doing any insertions, which it looks like you're doing correctly by looking at your updated post.

Finally, don't cast malloc() results in C programs.

Answer 2

You need to initialize head before you run the first insert:

/* This should go in main or some init function, before the first insert */
head = (struct Node *)malloc(sizeof(struct Node));
head->next = NULL;

Answer 3

Try this, it will correct the memory leak and check that head is valid. If you still had the segmentation fault, you should run a debugger to know exactly what is going.

void insert(int val, char arr[])
{
    struct Node *temp2 = malloc(sizeof(struct Node));
    temp2->type = val;
    strcpy(temp2->cmd, arr);
    temp2->next = NULL;

    if (head == NULL) {
      //list is empty, head must points on the created node
      head = temp2;
    }
    else {
      struct Node *temp1 = head;

      while(temp1->next != NULL)
        temp1 = temp1->next;

      temp1->next = temp2;
   }
}

EDIT : Now, this function should handle any case, even if head is null. (when list is empty)

Answer 4

See the link you referred, there also has a test file, http://www.codeproject.com/script/Articles/ViewDownloads.aspx?aid=24684, it will tell why you get this error, When insert from the back, it will first check the head if it is null and allocate space for the first element.

Blockquote

1  #include<iostream>
  2  
  3  using namespace std;
  4  
  5  typedef struct node
  6  {
  7      int data;   // will store information
  8      node *next; // the reference to the next node
  9  };
 10  
 11  
 12  int main()
 13  {
 14      node *head = NULL;  //empty linked list
 15      int info = 0, node_number = 0,  counter = 0;
 16      char ch;
 17  
 18      do{
 19          cout<<"\n\n";
 20          cout<<"0.Quit\n";
 21          cout<<"1.Insert at first\n";
 22          cout<<"2.Traverse\n";
 23          cout<<"3.Insert at last\n";
 24          cout<<"4.Insert after specified number of node\n";
 25          cout<<"5.Delete at first node\n";
 26          cout<<"6.Delete at last node\n";
 27          cout<<"7.Delete specified number of node\n";
 28          cout<<"8.Sort nodes\n";
 29  
 30          cout<<"Enter your choice: ";
 31          cin>>ch;
 32  
 33      switch(ch)
 34      {
 35  
 36      case '0': break;
 37  
 38      case '1': ....

  .....  case '3':{
           **// check linked list is empty**
           if(head==NULL)
           {
               cout<<"ENTER ANY NUMBER:";
               cin>>info;                        // take input data
               cout<<"Input data: "<<info;

               node *temp;                     // create a temporary node
               temp = (node*)malloc(sizeof(node)); // allocate space for node
               temp->data = info;               // store data(first field)
               temp->next = NULL;               // second field will be null
               head = temp;                    // transfer the address of 'temp' to 'head'
               counter++;
           }

           else
           {
               cout<<"ENTER ANY NUMBER:";
               cin>>info;                        // take input data
               cout<<"Input data: "<<info;
               node *temp1;                        // create a temporary node
               temp1=(node*)malloc(sizeof(node));  // allocate space for node
               temp1 = head;                   // transfer the address of 'head' to 'temp'
               while(temp1->next!=NULL)         // go to the last node
                   temp1 = temp1->next;         //tranfer the address of 'temp->next' to 'temp'

               node *temp;                 // create a temporary node
               temp = (node*)malloc(sizeof(node));// allocate space for node
               temp->data = info;               // store data(first field)
               temp->next = NULL;               // second field will be null(last node)
               temp1->next = temp;              // 'temp' node will be the last node
               break;
            }
   }