C linked list inserting node at the end without replacing previous node

Question

I'm having some trouble with my insertion method for a linked list in C. It looks like every insertion i make only replaces the previous one. so at the end the list always contains only one cell . i think the problem starts with "insertToEndList" function. Do you see any reason why it's failing?

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

typedef struct listNode{
    int* dataPtr;
    struct listNode* next;
}ListNode;

typedef struct list
{
    ListNode* head;
    ListNode* tail;
}List;

void deleteFromBeginnigOfList (List *list);
void deallocateListCell (ListNode *cell);
void freeList (List *list);
void printList (List *list);
void insertDataToBeginningList (List *list, int num);
void addToBeginningList (List *list, ListNode *cell);
List merge (List list1, List list2);
ListNode *createCell (int num);
void addToEmtyList(List *list, ListNode *cell);
void addToEndList(List *list, ListNode *cell);
void insertDataToEndList(List *list, int num);
void makeEmptyList(List *list);
List getList();
void main()
{

    List lst1, lst2, mergedList;

    lst1 = getList();
    lst2 = getList();
    mergedList = merge(lst1,lst2);

    printf("Merged list:\n");
    printList(&mergedList);

    freeList(&lst1);
    freeList(&lst2);
    freeList(&mergedList);

}

List getList()
{
    List res;
    int size, num, i;

    makeEmptyList(&res);

    printf("Please enter the number of items to be entered:\n");
    scanf("%d", &size);

    printf("Please enter the numbers:\n");
    for(i = 0; i < size; i++)
    {
        scanf("%d", &num);
        insertDataToEndList(&res, num);
    }

    return res;

}
void makeEmptyList(List *list){
    list->head=list->tail=NULL;
}
void insertDataToEndList(List *list, int num){

    ListNode *cell_to_add= createCell (num);
    if (list->head==NULL)
        addToEmtyList(list, cell_to_add);
    else
        addToEndList(list, cell_to_add);
}
ListNode *createCell (int num){
    ListNode *cell=(ListNode*)malloc(sizeof(ListNode));
    if (!cell)
    {
        printf("memory allocation failed\n");
        exit(1);
    }
    cell->dataPtr=&num;
    cell->next=NULL;

    return cell;
}
void addToEmtyList(List *list, ListNode *cell){
    list->head=list->tail=cell;
}
void addToEndList(List *list, ListNode *cell){
    list->tail->next=cell;
    list->tail=cell;
}
List merge (List list1, List list2){
    List merge_res; 
    ListNode *curr_cell1=list1.head, *curr_cell2=list2.head; 
    ListNode *cell_to_add;

    makeEmptyList (&merge_res); 
    while (curr_cell1 && curr_cell2) 
    {
        if (*(curr_cell1->dataPtr)>*(curr_cell2->dataPtr))
        {
            insertDataToEndList(&merge_res, *(curr_cell1->dataPtr));
            curr_cell1=curr_cell1->next;
        }
        else
        {
            insertDataToEndList(&merge_res, *(curr_cell2->dataPtr));
            curr_cell2=curr_cell1->next;
        }
    }
    while (curr_cell1)
    {
        insertDataToEndList(&merge_res, *(curr_cell1->dataPtr));
        curr_cell1=curr_cell1->next;
    }
    while (curr_cell2)
    {
        insertDataToEndList(&merge_res, *(curr_cell2->dataPtr));
        curr_cell2=curr_cell2->next;
    }
    return merge_res;
}

void printList (List *list){
    ListNode *curr_cell=list->head;

    while (curr_cell)
    {
        printf("%d, ", *(curr_cell->dataPtr));
        curr_cell=curr_cell->next;
    }
}
void freeList (List *list){
    while (list->head)
        deleteFromBeginnigOfList(list);
}
void deleteFromBeginnigOfList (List *list){
    ListNode *cell_to_delete=list->head;
    list->head=list->head->next;
    if (list->head==NULL)
        list->tail=NULL;
    deallocateListCell (cell_to_delete);
}
void deallocateListCell (ListNode *cell){
    free(cell->dataPtr);
    free (cell);
}

[TL;DR!](https://en.wiktionary.org/wiki/TL;DR). Please try to create a [Minimal, Complete, and Verifiable Example](http://stackoverflow.com/help/mcve) and show us instead. — Some programmer dude, Aug 12 '15 at 12:43
`list->head->next==NULL` this condition in `if` you assume list is empty but list can have 1 node only. That should be taken care of .You should check if `head` is null or not for empty list. — ameyCU, Aug 12 '15 at 12:45
I'm having a hard time understanding how this code executes at all without segfaulting. In `getList`, you first call `makeEmptyList` which sets `list->head=NULL`, then you call `insertDataToEndList` which accesses `list->head->next` (i.e. dereferencing the null pointer `list->head`). When I compile and run the program it crashes at this point. — nemetroid, Aug 12 '15 at 12:55
[Please don't cast the result of `malloc()`](http://stackoverflow.com/a/605858/3233393). — Quentin, Aug 12 '15 at 13:46
does have to be singly linked? a doubly liked list with a sentry node is a lot easier to verify for correctness. see [example](http://pastebin.com/HC1DLK4M) — sp2danny, Aug 12 '15 at 13:59

V. Couvignou · Answer 1 · 2015-08-12T14:00:27.423

In this function, you access to list->head->next but on the first insertDataToEndList, list->head == NULL since you used makeEmptyList so the result will be a segmentation fault. Also, you want to check if the list is Empty so do list->head == NULL instead.

void insertDataToEndList(List *list, int num)
{    
    ListNode *cell_to_add= createCell (num);
    if (list->head->next==NULL)
        addToEmtyList(list, cell_to_add);
    else
        addToEndList(list, cell_to_add);
}

In this method, you have to set the first and the last node of your list, not the next so replace by list->head and list->tail instead of lis->head->nest. and list->tail->next.

void addToEmtyList(List *list, ListNode *cell)
{
    list->head->next=list->tail->next=cell;

}

You can do that instead :

ListNode *createCell (int num)
{
    ListNode *cell=(ListNode*)malloc(sizeof(ListNode));
    if (!cell)
    {
        printf("memory allocation failed\n");
        exit(1);
    }
    int *temp = (int*)malloc(sizeof(int));
    *temp = num;
    cell->dataPtr=temp;
    cell->next=NULL;

    return cell;
}

Else, I advise you to do one assignement by line to be more lisible.

score 1 · Answer 2 · answered Aug 12 '15 at 13:51

There are a few errors here. Most are relatively simple pointer errors:

In one place you have

curr_cell2=curr_cell1->next;

where it should be

curr_cell2 = curr_cell2->next;

In addToEmtyList, you have

list->head->next=list->tail->next=cell

but if the list is empty, then both head and tail are null. Similarily, the condition in insertDataToEndList should check list->head and not list->head->next.

A more aggravating error is that you're taking the address of a local variable (num) and saving it in each cell. Saving the address of a local variable is something you should almost never do, since the pointer will become invalid as soon as you leave its scope (in this case, when you leave createCell).

What you should do, if you really want to have a pointer to the data, is allocate memory for it separately. I.e.:

ListNode *createCell (int num){
    ListNode *cell=(ListNode*)malloc(sizeof(ListNode));
    int *data = malloc(sizeof(*data));

    if (!cell || !data)
    {
        printf("memory allocation failed\n");
        exit(1);
    }

    *data = num;
    cell->dataPtr=data;
    cell->next=NULL;

    return cell;
}

Another option is to change listNode to contain an int instead of an int*. Then you'd have

typedef struct listNode{
    int data;
    struct listNode* next;
}ListNode;

and in createCell simply

cell->data = num;

C linked list inserting node at the end without replacing previous node

2 Answers2