A question about add element at the end of a linked list

user_13541333 0
Viewed 68

I tried to write a program to add some nodes in a linked list. When I compile and run it, I get a segmentation fault. Could anyone tell me where the problem is?

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

struct node{
    int data;
    struct node* link;
};                          // define a structure

struct node* first;         //the first node;

void insert(int n)          // function to insert element at the end
{
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    struct node* ptr = first;
    temp->data = n;
    temp->link = NULL;
    while(ptr->link != NULL)
    {
        ptr = ptr->link;
    }
    ptr->link = temp;
}

void Print()                //function to print out the element
{
    struct node* ptr = first;
    printf("List is:");
    while(ptr != NULL)
    {
        printf("%d ",ptr->data);
        ptr = ptr->link;
    }
}

int main()
{
    int i,k,n;
    first = NULL;
    printf("How many numbers you want to insert?");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        printf("Enter:");
        scanf("%d",&k);
        insert(k);
    }
    Print(); //Print out the linked list
    return 0;
}
linked-list c
4 Answers

When you attempt to insert the first element in the list, first is NULL which means you set ptr to NULL. Then when you check ptr->link != NULL at the start of the loop you dereference a NULL pointer which invokes undefined behavior.

Before attempting to traverse the list, check if first is NULL and if so set it to the new node and return.

void insert(int n)
{
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    struct node* ptr = first;
    temp->data = n;
    temp->link = NULL;

    if (!first) {
        first = temp;
        return;
    }
    while(ptr->link != NULL)
    {
        ptr = ptr->link;
    }
    ptr->link = temp;
}
user_16871190

In the following section, ptr is being assigned to first, which is initialized to null:

struct node* first;         //the first node;

void insert(int n)          // function to insert element at the end
{
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    struct node* ptr = first;
    temp->data = n;
    temp->link = NULL;
    while(ptr->link != NULL)
           |_____Dereference of null pointer occurs here.
    ...

In this section, Test first, and if null assign it to temp and return.

But your question is really asking how to 'add element to the end of a linked list', (which I am interpreting as 'appending a new node to the end of a linked list'.) If that interpretation is correct, then the function doing that requires knowing something about the existing list. The prototype of your existing function includes only data, but needs to also include a reference to the existing list. The following uses the name append, to more accurately what I believe you want to do, and includes both a reference to the existing list, and the data.

void append(struct node** head_ref, int new_data);//(int n in your code)

In designing a function to do this, the following ideas should be included:

  • Create a new node new_node
  • Create a pointer to last node
  • assign input value new_data to new_node->data
  • initialize new_node->next to NULL
  • test head reference to see if list is empty, if so set new_node to head
  • if not empty, loop through until end of list
  • assign last->next to point to new_node

Example implementation: 

void append(struct node** head_ref, int new_data) 
{ 
    struct node* new_node = malloc(sizeof(struct node)); 
    struct node *last = *head_ref;  
    new_node->data  = new_data; 
    new_node->link = NULL; 
    if (*head_ref == NULL) 
    { 
       *head_ref = new_node; 
       return; 
    } 
    while (last->link != NULL) 
        last = last->link; 
    last->link = new_node; 
    return; 
}

This implementation accommodates a series of calls to append to a list, whether its the very first list item, or to a list that is already populated.

A simple calling example - with a graphic showing what its results look like in memory: 

int main(void)
{  
    for(int i=0;i<10;i++)
    {  
        append(&first, i);
    }
    return 0;
}

enter image description here

user_6451280

Your node first is declared to be a pointer and later set to NULL. Just turn your first-node into a value ( or malloc space for it ).

Admin1

When you first call insert, first is NULL. The following is your problem:

void insert(int n)          // function to insert element at the end
{
    ...
    struct node* ptr = first;
    ...
    while(ptr->link != NULL)
    ...
}

You're dereferencing ptr which is NULL. Add an if check in insert to see if ptr is NULL. Something like this:

if(ptr == NULL)
{
    first = tmp;
}
else
{
    while(ptr->link != NULL)
        ptr = ptr->link;
    ptr->link = temp;
}

You should have a similar check in Print.

user_29939600
Related