How to initialize a data structure (eg. linked list) with functions in C?

Question

#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node * next;
} Node;

typedef struct List {
    Node* data;
} List;

List* create_list(unsigned int length) {
    List* new;
    (*new).data = (Node*)malloc((sizeof(Node))*length);
    return new;
}

int main() {
    List* list = create_list(10);
    return 0;
}

I know how to create a Linked List obj in Python and still trying to figure out how to do it in C. This code throws me a segmentation fault every time I run it. Please send help.

You deference `new` (`(*new).data`) before initializing it. `-fsanitize=address` can help find these problems. — ikegami, Nov 14 '20 at 18:27
OT: Why use `(*new).data` instead of the equal (and shorter to both read and write) `new->data`? — Some programmer dude, Nov 14 '20 at 18:40
Also OT: Generally you [should not cast the result of `malloc`](https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). — Some programmer dude, Nov 14 '20 at 18:41
More on topic: You allocation doesn't create a "list", but merely an array of `Node` structures. — Some programmer dude, Nov 14 '20 at 18:42

dspr · Answer 1 · 2020-11-14T22:04:16.573

I give you an example. Note that the List structure would not really needed in this case because the first node (the head) is already the list. However a list structure could be useful in some cases, for instance to keep trace of the list length.

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

typedef struct Node {
    int value;
    struct Node * next;
} Node;

typedef struct List {
    Node* head;
    int length;
} List;

A function to print the list :

void printList(List *list) 
{
   if (!list) return;
   Node * cur = list->head;
   while(cur) {
       printf("%d ", cur->value);
       cur = cur->next;
   }
   printf("\n");
}

A function to free the list. Because each node is allocated separately, it must be freed separately too :

void freeList(List *list) 
{
    if (!list) return;
    Node * cur = list->head;
    while(cur) { 
        Node *next = cur->next;
        free(cur); 
        cur = next;
    }
    free(list);
}

Node and List creation :

Node* createNode (int value) 
{
   Node * new = malloc((sizeof(*new)));
   if (!new) return NULL; 
   new->value = value;
   return new;
}

List* create_list(unsigned int length) 
{
    List* lst = malloc((sizeof(*lst)));
    if (!lst) return NULL;

    int value = 1;
    lst->length = length;
    lst->head = createNode(value++);
    Node * tail = lst->head;

    // Creates the wanted number of nodes giving 
    // a simple incremented number as its value
    // Each node is linked to the next
    while (--length > 0) {
        Node * new = createNode(value++); 
        tail->next = new;
        tail = new;
     }
     return lst;
}
    
int main() {
    List* list = create_list(10); //Create the list with 10 nodes
    printList(list);              //Print it => 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
    freeList(list);               //Free it
    return 0;
}

Why do: `void * new = malloc((sizeof(Node)));` and then: `((Node *)new)->value = value;`? How about: `Node *new = malloc(sizeof(*new));` and then: `new->value = value;`? — Craig Estey, Nov 14 '20 at 20:44
@Craig Estey : I thought that the compiler was not happy with `Node *new = malloc(sizeof(Node));` and that a cast was necessary, but in fact no. So it's simpler like that, thanks for pointing that. — dspr, Nov 14 '20 at 21:32
dspr, @Craig Estey did suggest `new = malloc(sizeof(*new));`. Curious: stay with `new = malloc((sizeof(Node)));`? — chux - Reinstate Monica, Nov 14 '20 at 21:52
@chux - Reinstate Monica : I think that the two expressions are valid, am I wrong ? — dspr, Nov 14 '20 at 22:00
Both are valid. `new = malloc(sizeof *new);` is easier to code right, review and maintain. — chux - Reinstate Monica, Nov 14 '20 at 22:02

How to initialize a data structure (eg. linked list) with functions in C?

1 Answers1