I am learning data structures and stuck at implementation of queues using linked-list in c

Question

I have written the below piece of code for implementing the queues and their operations(enqueue). The program compiled well with no errors but when the input is given for insertion(enqueue operation) the program stops working and shows a.exe has stopped working

The program contains create_node() function which returns a node, linkedlist initialize function, queue initialize function both of these functions are void functions, and insertion at the end of the linked list function is written which in turn calls the enqueue function. Note: There's no display function to print all the elements to queue

I think there might be something wrong with initialization functions but I am not sure about it.

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

typedef struct node node;

struct node
{
    int id;
    node *link;
};

typedef struct list
{
    node *head;
    node *tail;
    int number_of_nodes;
} List;

typedef struct queue
{
    List *ptr_list;
} Queue;


static node *create_node(int id,node *link)
{
    node *temp = (node*)malloc(sizeof(node));
    temp->id=id;
    temp->link=link;
    return temp;
    
}
void list_initialize(List *ptr_list)
{
    ptr_list  = (List*)malloc(sizeof(List));
    ptr_list->head=ptr_list->tail=NULL;
    ptr_list->number_of_nodes = 0;
}

void list_insert_rear(List *ptr_list, int id)
{L
    node *temp = create_node(id,NULL);
    if(ptr_list->tail==NULL)
    {
        ptr_list->head=ptr_list->tail=NULL;
        ptr_list->number_of_nodes++;
    }
    else
    {
        ptr_list->tail->link=temp;
        ptr_list->tail=temp;
        ptr_list->number_of_nodes++;
    }
}
void queue_initialize(Queue *queue_list)
{
    queue_list = (Queue*)malloc(sizeof(Queue));
    list_initialize(queue_list->ptr_list);
}
void queue_enqueue(Queue *ptr, int id)
{
    list_insert_rear(ptr->ptr_list,id); 
}
int main()
{
    Queue queue;
    queue_initialize(&queue);
    int choice, id, t;
    int loop = 1;
    while (loop)
    {
        scanf("%d", &choice);
        switch (choice)
        {
        case 0:
            scanf("%d", &id);
            queue_enqueue(&queue, id);
            break;
        default:
             loop =0;
             break;
        }
     }
}

what tests have you tried out to try and understand where the issues occur? also try to not use input from the user (scanf) for testing since you want reproducible and consistent results across your tests — Gilad, Oct 24 '20 at 21:04
Does this answer your question? [Changing address contained by pointer using function](https://stackoverflow.com/questions/13431108/changing-address-contained-by-pointer-using-function) — kaylum, Oct 24 '20 at 21:09
Read the linked post and then apply that to `list_initialize` — kaylum, Oct 24 '20 at 21:10
@1201ProgramAlarm can u please say what's wrong with that part. — KotlinOverflow, Oct 24 '20 at 21:11
In `list_initialize`, do what you did in `create_node` (i.e. return the pointer). You could rename it to `list_create` as that would be closer to it's new function. Then, in `queue_initialize`, do: `queue_list->ptr_list = list_create();`. Note that `queue_initialize` has the same problem (i.e. you're _not_ returning the pointer that you `malloc`ed). — Craig Estey, Oct 24 '20 at 21:18

score 0 · Answer 1 · 2020-10-24T21:47:19.633

This is a problem I actually ran in to a few times and can be tricky to spot. In list_initialize, you should use List **ptr_list.

In the first line of this function, you are changing the pointer, but only in the scope of this variable, so the pointer you put in doesn't actually point to the data anymore, this can be solved by making it a pointer to a pointer. (It's kinda hard to explain)

The function would be (didn't test it):

void list_initialize(List **ptr_list)
{
    List *ptr_listnew;
    ptr_listnew  = (List*)malloc(sizeof(List));
    ptr_listnew->head=ptr_listnew->tail=NULL;
    ptr_listnew->number_of_nodes = 0;
    *ptr_list = ptr_listnew;
}

This is also the case in queue_initialize, which requires the same kind of fix.

Craig Estey · Answer 2 · 2020-10-24T21:53:10.410

You are confusing/combining struct allocation and struct initialization so that your functions do neither well. (See my top comments). As a result, your struct pointers aren't initialized properly and you're getting UB (undefined behavior), most likely a SIGSEGV (segfault).

Although a single function can do both, separating them can give you some insight.

Side note: Don't cast the result of malloc. See: Do I cast the result of malloc?

Here's a refactored version. Original code is marked with #if 0 and new code is marked with #if 1. Bug/fixes are annotated.

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

typedef struct node node;

struct node {
    int id;
    node *link;
};

typedef struct list {
    node *head;
    node *tail;
    int number_of_nodes;
} List;

// NOTE/STYLE: use more descriptive names
typedef struct queue {
#if 0
    List *ptr_list;
#else
    List *queue_list;
#endif
} Queue;

static node *
create_node(int id, node *link)
{
    node *temp = (node *) malloc(sizeof(node));

    temp->id = id;
    temp->link = link;

    return temp;
}

void
list_initialize(List *ptr_list)
{
// NOTE/BUG: you are blowing away caller's pointer value
#if 0
    ptr_list = malloc(sizeof(List));
#endif
    ptr_list->head = ptr_list->tail = NULL;
    ptr_list->number_of_nodes = 0;
}

#if 1
List *
list_create(void)
{
    List *ptr_list;

    ptr_list = malloc(sizeof(List));
    list_initialize(ptr_list);

    return ptr_list;
}
#endif

void
list_insert_rear(List *ptr_list, int id, int time)
{
    node *temp = create_node(id, NULL);

    if (ptr_list->tail == NULL) {
        ptr_list->head = ptr_list->tail = NULL;
        ptr_list->number_of_nodes++;
    }
    else {
        ptr_list->tail->link = temp;
        ptr_list->tail = temp;
        ptr_list->number_of_nodes++;
    }
}

void
queue_initialize(Queue *queue_list)
{
// NOTE/BUG: you are blowing away caller's pointer value
#if 0
    queue_list = malloc(sizeof(Queue));
#endif
    queue_list->queue_list = list_create();
}

#if 1
Queue *
queue_create(void)
{
    Queue *queue_list;

    queue_list = malloc(sizeof(Queue));
    queue_initialize(queue_list);

    return queue_list;
}
#endif

// NOTE/BUG: wrong prototype
#if 0
void
queue_enqueue(Queue *queue, int id)
#else
void
queue_enqueue(Queue *queue, int id, int time)
#endif
{
// NOTE/BUG: not enough arguments for call
#if 0
    list_insert_rear(queue->queue_list, id);
#else
    list_insert_rear(queue->queue_list, id, time);
#endif
}

int
main(void)
{
    Queue queue;

    queue_initialize(&queue);
    int choice, id, t;
    int loop = 1;

#if 1
    t = 0;
#endif

    while (loop) {
        scanf("%d", &choice);
        switch (choice) {
        case 0:
            scanf("%d", &id);
            queue_enqueue(&queue, id, t);
            ++t;
            break;
        default:
            loop = 0;
            break;
        }
    }

#if 1
    return 0;
#endif
}

I am learning data structures and stuck at implementation of queues using linked-list in c

2 Answers2