Linked List implementation using C

Question

I am having trouble understanding something:

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

int main() {
    node* head = NULL;   /*here*/
    node* second = NULL;
    node* third = NULL;

What does that line node* head = NULL; do? Does it initialize a new node named head? Then why is the * there, my struct is typedefd as just node so in other cases while handling with data structures, I should use like node head = NULL in this case.

Later in this code, I have

    head = (struct node*)malloc(sizeof(node));

which, I guess, allocates the space for that node. And this part

    head->info = 1;
    head->next = second;

sets the data and pointer part of the head node. Did I understand this correctly?

You'll need to have a good understanding of pointers before you'll be able to implement a linked list. You may want to take a step back, read up on them then revisit this problem. — Carcigenicate
– Carcigenicate, Commented Aug 14, 2020 at 20:20
Instead of jumping head-first into "competitive coding" take time to familiarize yourself with the fundamentals first. There are a lot of good C reference books and introduction courses worth using. — tadman
– tadman, Commented Aug 14, 2020 at 20:21
Just Started Competitive Coding + learning Linked Lists == slow motion train wreck. Linked Lists in C are a never end cause of headaches even among professionals. Take a step back and really study pointers. — Michael Dorgan
– Michael Dorgan, Commented Aug 14, 2020 at 20:21
Short answer - head is made NULL because it is pointing to an empty list. As items are created then added to this list, it will update to point at the beginning of the list of pointers. — Michael Dorgan
– Michael Dorgan, Commented Aug 14, 2020 at 20:23

Ashlesha Sunil Agate · Accepted Answer · 2020-08-14 20:56:20Z

2

what does that line " node * head = NULL; " does ??

So, node* is kind of a data type that you have created using typedef struct code. So when you do node* head, you are actually defining a pointer to node datatype. Since initially no linkedlist has been implemented, the head will not point anywhere hence, it points to NULL.

PLEASE NOTE : head is not a new node, it is a pointer to the datatype - node

head = (struct node*)malloc(sizeof(node))

Here, you are correct - we are allocating memory for a node type, but we return the address of the memory space and store it in head.

head->info = 1;

head->next = second;

head -> info is for storing the data value, and head -> next , next is the pointer to the next node (if any) in our linked list implementation. next and head have the same data type " node* "

answered Aug 14, 2020 at 20:56

Ashlesha Sunil Agate

631 silver badge5 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

LSerni · Accepted Answer · 2020-08-14 20:25:21Z

1

does it initialize a new "node" named head?

No. It initializes a pointer to somewhere, and instructs the compiler that this somewhere will then have to be interpreted as a "node" structure. So, for example, "head->info" will mean that the first two or four or eight bytes, depending on integer size on your machine, will be interpreted as an integer value.

Actually, the pointer is then initialized to NULL, so it doesn't point anywhere at all.

When building the list, you will create new nodes, and then head will be updated to point to the first of these nodes. Head being NULL would mean that the list is empty.

answered Aug 14, 2020 at 20:25

LSerni

57.7k10 gold badges70 silver badges110 bronze badges

Comments

arfneto · Accepted Answer · 2020-08-14 22:50:06Z

Maybe one reason of this seem to be difficult is that

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

is the definition of a Node and not the definition of a linked list. More on that below.

But node* head = NULL; declares head as a pointer to node, a structure representing a single node of a list. Inside node, info is the data part, and could be anything, like a pointer to a giant useful structure of data. In this case, just a number. And next is the link part, and will point to the next node on your list.

In your program, as a pointer to node, head can point to a structure like that, having a data part, the info field, and a pointer to another node, the next field. Sometimes there is also a pointer to the previous node too, and it is said to be a double linked list for obvious reasons.

But this is not a linked list in itself. Just a pointer to a node, and it is now pointing to nothing since it has been initialized to NULL.

You can write

node my_node;

and now we have a node. my_node has two fields and you can write

my_node.info = 1;
my_node.next = NULL;

and say you have a linked list of just one node. And you can even make head point to it by using the operator 'address of', the ampersand, by writing

head = &my_node;

that takes the address of my_node and put into a pointer, well, to a node. This is what pointers are meant for.

Or you can write

head = (node*) malloc( sizeof(node) );

And allocate memory just the size of a node. And then head is not pointer to NULL anymore. It is pointer to an area of the size of a node and be used as such. You can now write

head->info = -3456;
head->next = NULL;

Note that in the case of a pointer you use the operator -> to access the field, not the dot as in the example of my_node above, a local variable in you program.

You can stop reading now if is clear what head is, and the meaning of the declaration in your program. What follows is just a more complete example

(An arguably more useful) Other Linked List structure

struct c_node
{
    void*           data;
    struct c_node*  next;
    struct c_node*  prev;
};
typedef struct c_node CNode;

struct c_list
{
    char*   name;
    int     capacity;
    int     size;
    CNode*  start;
    CNode*  end;
};
typedef struct c_list _List;

Note that on the example of _List above things can get more meaning. One could just write

_List my_linked_list;

but my_linked_list here has nodes, a parameter that you keep the actual size of the list, a possible limit of capacity, pointers to the start and the end of the list to make life simpler. And even a name.

When creating the list you set things up as in


_List* create_list(const char* name, int capacity)
{
    _List* list = (_List*) malloc( sizeof(_List) );
    list->capacity = capacity;
    list->size = 0;
    list->start = list->end = NULL;

    list->name = (char*)malloc(strlen(name) + 1);
    strcpy(list->name, name);
    return list;
}

and create a list by just calling

_List* = create_list("My First 100 Nodes", 100);

Note that in this case the data is just a pointer, the void* data; part of the node structure, CNode, so this thing can point to anything, creating an abstract data structure, a container of things.

This is just a part of an example and the intent is just to show how (I believe) more clearly the purpose and structure of a linked list. Much more than just a node.

Collectives™ on Stack Overflow

Linked List implementation using C

3 Answers 3

Comments

Comments

(An arguably more useful) Other Linked List structure

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

(An arguably more useful) Other Linked List structure

Comments

Your Answer

Sign up or log in

Post as a guest

Related