I'm having a problem creating a linked list [duplicate]

Question

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

void insert_front(struct node* head, int block_number);
void insert_rear(struct node* head, int block_number);
void print_list(struct node* head);

struct node {
    int block_number;
    struct node* next;
};

int main(void)
{
    struct node* list = NULL;

    insert_front(list, 10);
    insert_rear(list, 20);
    insert_front(list, 30);
    insert_rear(list, 40);

    print_list(list);

    return 0;
}

void insert_front(struct node* head, int block_number)
{
    struct node* p = malloc(sizeof(struct node));
    p->block_number = block_number;
    p->next = head;
    head = p;
    return head;
}

void insert_rear(struct node* head, int block_number)
{
    struct node* p = malloc(sizeof(struct node));
    p->block_number = block_number;
    p->next = NULL;

    if (head == NULL) {
        head = p;
    }
    else {
        struct node* q = head;
        while (q->next != NULL) {
            q = q->next;
        }
        q->next = p;
    }
}

void print_list(struct node* head)
{
    struct node* p = head;
    while (p != NULL) {
        printf("--> %d ", p->block_number);
        p = p->next;
    }
    printf("\n");
}

When I ran it, there was no result at all.

Now, in the insert_front function p->block_number = block_number, a message appears saying that the NULL pointer 'p' is being dereferenced... (The same thing appears in the insert_rear function.)

Could it be that I am declaring the pointer wrong?

Answer 1

Both insert_front and insert_rear need to convey possibly head modification back to the caller, and the caller needs to reap that information. Both should be declared to return struct node *, do so, and the code in main react accordingly. E.g.:

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>

struct node * insert_front(struct node *head, int block_number);
struct node * insert_rear(struct node *head, int block_number);
void print_list(struct node *head);

struct node
{
    int block_number;
    struct node *next;
};


int main(void)
{
    struct node *list = NULL;

    list = insert_front(list, 10);
    list = insert_rear(list, 20);
    list = insert_front(list, 30);
    list = insert_rear(list, 40);

    print_list(list);

    return 0;
}

struct node *insert_front(struct node *head, int block_number)
{
    struct node *p = malloc(sizeof(struct node));
    p->block_number = block_number;
    p->next = head;
    head = p;
    return head;
}

struct node *insert_rear(struct node *head, int block_number)
{
    struct node *p = malloc(sizeof(struct node));
    p->block_number = block_number;
    p->next = NULL;

    if (head == NULL)
    {
        head = p;
    }
    else
    {
        struct node *q = head;
        while (q->next != NULL)
        {
            q = q->next;
        }
        q->next = p;
    }
    return head;
}

void print_list(struct node *head)
{
    struct node *p = head;
    while (p != NULL)
    {
        printf("--> %d ", p->block_number);
        p = p->next;
    }
    printf("\n");
}

Output

--> 30 --> 10 --> 20 --> 40 

I leave the memory leaks for you to resolve.

Answer 2

In C all variables are passed by value – if you pass a pointer, then it is copied, too (not the pointed to object, of course...), and function parameters, apart from being initialised from outside, are nothing more than local variables. Thus via head = p; you just assign the local copy of the outside pointer, not the latter itself!

To fix that you have two options:

1. Return the new head and make the user responsible for re-assigning the returned value to his own head pointer.
2. Accept the head as pointer to pointer.

With second approach a user cannot forget to re-assign the (potentially) new head, so that's what I'd go with:

void insert_whichEver(node** head, int block_number)
{
    // use `*head` where you had `head` before...
} 

void demo()
{
   node* head = NULL;
   insert_front(&head, 1012);
}

And in insert_front drop return head;, a function with void cannot return anything concrete and does not require a return at all (but bare return; can be used to exit a function prematurely).