Linked list Implementation in C with structure

Question

I'm using this structure as a linked list:

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

 }node_t;

And everything works fine until I put struct node_t* next before int value field, then I have a lot of trash values working with that structure. Is it about wrong implementation or something else in the code?

Answer 1

You are calling your structure Node and defining a node_t type. Then you are using node_t as if it was the name of the structure and not the type.

Try this

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

Or

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

If you call it struct Node, then

struct Node {
    int value;
    /* The compiler doesn't know what `struct Node' is yet */
    struct Node *next;
    /* But you can always declare pointers, even of types the compiler
     * doesn't know everything about. Because the size of a pointer
     * does not depend on the type of the pointee.
     */
};

In your example, it's even worse. You typedefed something that is a new type as the compiler understand it, to use it you MUST not use struct. The whole idea behind typedefing is that you DEFINED a new type, so suppose the following

typedef struct Node node;

then to declare a pointer of type node (note, again node IS A TYPE),

node *anode;

but you attempted something like

struct node *anode;

and it's wrong because there is no struct node in the code above, it's struct Node.

Another mistake in your code is that, the node_t type does not exist when the compiler finds the

struct node_t *next;

which is already wrong because if the type were defined before the struct which is possible like this

typedef struct Node node_t

it'd still be wrong to use struct on the node_t type, because for the compiler node_t is not a struct it's a new type, which in turn is simply an alias for struct Node.

Typedefing structures in my experience is more trouble than benefit anyway. And it's not so hard to type struct Something instead of just Something. It also has the benefit of being more explicit, so if another programmer reads your code, they will immediately know that Something is a struct.

Note: I deliberately changed the name to node because it's considered bad practice to suffix your own defined types with _t. It's not necessarily a bad thing, but over the years that I've been working with this I developed some habits and one of them is not to use _t as a suffix for my own defined types. Which by the way only exist in my code if they will improve readability a lot. Otherwise I simply use the name of the structure with the struct keyword.

Answer 2

You are using a non existing type node_t. The type doesn't exist because the type struct Node is not even complete and you are using it's alias. Another thing to remember while using typedefs with structures don't use struct keyword along with alias eg.

/* This is correct */
typedef struct Node
{
    int x;
    struct Node *next;
} node_t;

/* while these are incorrect */

/* Prefixing struct keyword to a typedef'ed type */
struct node_t *listhead;

/* The type is inclomplete and you are using an alias of the type
   which doesn't even exist */
typedef struct Node
{
    int x;
    node_t *next;
};