CODEWITHSUNDEEP
clinked-list
wanaryytel
wanaryytel

Reputation: 3482

Some misconception with linked list implementation

It seems that I have a major misconception as to how I can implement a linked list in C. As far as I can understand (and this code is as simplified as can be!), this should work, but instead returns a segmentation fault. Also worth noting that if I comment out everything below MARKER, it seems to be working, but there is probably an underlying issue that makes it all faulty.

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


typedef struct node
{
    int val;
    struct node *next;
} node;


int main (void)
{
    node *pode;
    node *nx, *vx, *sx;

    pode = (node *) malloc(1 * sizeof(node));
    pode->val = 12;

    pode = (node *) realloc(pode, 2 * sizeof(node));
    pode->next = (pode + 1);
    (pode + 1)->val = 66;

    pode = (node *) realloc(pode, 3 * sizeof(node));
    pode->next = (pode + 2);
    (pode + 2)->val = 33;

    pode = (node *) realloc(pode, 4 * sizeof(node));
    pode->next = (pode + 3);
    (pode + 3)->val = 44;


    printf("%d\n", pode->val);

    nx = pode->next;
    printf("%d\n", nx->val);

    // MARKER
    vx = nx->next;
    printf("%d\n", vx->val);

    sx = nx->next;
    printf("%d\n", sx->val);

    return 0;
}

Where's the boo-boo?

Upvotes: 0

Views: 88

Answers (2)

Jerry101
Jerry101

Reputation: 13357

Well, your first mistake is using realloc(). That's easy to get burned with because it might or might not move the node, causing any pointers to it to become dangerous dangling pointers.

Linked lists are all about linking the nodes together with pointers, so there's no reason to reallocate one node into a larger node, and that defeats the ability to splice the list by changing pointers. Generally, you'd allocate each node separately. (In some cases a program might deallocate list nodes by putting them into a "free" list for very fast deallocation and later reallocation.)

Your second mistake is forgetting to set each node's next pointer as soon as you allocate the node. Don't rely on the allocator to clear it.

Even if the code did set all the next pointers correctly, realloc() may move the node, breaking all those pointers.

Finally, if you step through the running program in a debugger (e.g. CLion), you'll be able to see where you have dangling pointers.

Upvotes: 3

pm100
pm100

Reputation: 50110

There are 2 issues here. Why does my code crash? Is this the 'right', 'idiomatic' way to do linked lists?

Second one first. No it is not. The normal way is to malloc each node separately and link the together. What you are really building is a resizable array. you need

    node *pode; // the head
    node *n, *prev;

    pode = (node *) malloc(sizeof(node));
    pode->val = 12;

    n = (node *) malloc(sizeof(node));
    pode->next = n;
    n->val = 66;
    prev = n;
    n = (node *) malloc(sizeof(node));
    prev->next = n;
   n->val = 33;
    prev = n;
    n = (node *) malloc(sizeof(node));
    prev->next = n;
    n->val = 44;
etc.

to find out why your code crashes run it under a debugger

Upvotes: 1

Related Questions