// Linked list implementation in C

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

// Creating a node
struct node {
  int value;


 struct node *next; //What is this, what are we doing here?
};

// print the linked list value
void printLinkedlist(struct node *p) {
  while (p != NULL) {
    printf("%d ", p->value);
    p = p->next;
  }
}

int main() {
  // Initialize nodes
  struct node *head;
  struct node *one = NULL;
  struct node *two = NULL;
  struct node *three = NULL;

  // Allocate memory
  one = malloc(sizeof(struct node));
  two = malloc(sizeof(struct node));
  three = malloc(sizeof(struct node));

  // Assign value values
  one->value = 1;
  two->value = 2;
  three->value = 3;

  // Connect nodes
  one->next = two;
  two->next = three;
  three->next = NULL;

  // printing node-value
  head = one;
  printLinkedlist(head);
}

I want to ask what are we doing here with this line of code? it's in the creating a node part of the code (top).

struct node *next;

Are we assigning a pointer type struct variable for the sturct node but its inside of the same struct, assigning a variable named *next inside the same struct? But that isn't allowed, right?

we can either declare the variable out side the } and between ; or in the main() function part of the code only, Isn't it?

Like

main()
{
struct node *next;
}

Again, then I came across a post mentioning it as a pointer to the structure itself, can anyone explaine how can we do this inside the same struct?

CodePudding user response：

The next member points to another instance of struct node. Graphically, we usually represent it like this:

 ––––––– ––––––        ––––––– ––––––   
| value | next |––––> | value | next |
 ––––––– ––––––        ––––––– –––––– 

A struct type cannot contain an instance of itself - we can’t create a type like

struct node {
  int value;
  struct node next;
};

for two reasons:

• The type definition isn’t complete until the closing }, and you cannot create an instance of an incomplete type;

• The type would require infinite storage (struct node contains a member next of type struct node which contains a member next of type struct node which contains a member next of type struct node...);

However, we can declare next as a pointer to struct node, since we can create pointers to incomplete types. The size and representation of a pointer is independent of the size and representation of the type it points to.

CodePudding user response：

What it means

The line struct node *next; is read as "next is a pointer to another struct node".

This is just a recursive structure declaration (definition):

struct node {
  int value;
 struct node *next; //What is this, what are we doing here?
};

It says a node consist of two parts:

1. an integer value
2. a pointer to another node.

The wiki article on linked lists has a nice visualization showing how one node points to another (or to NULL to end the chain).

How does it work?

As you noted, the interesting part is how the declaration can include a reference back to itself. The compiler handles this in two steps:

1. It sizes the struct as consisting of an int and a pointer (they're all the same size regardless of what they are pointing to).

2. Later it type checks the assignment and generates the appropriate assembly. When you write one->value = 1;, it makes sure the 1 is an integer and generates code to move 1 to the integer slot. And when your write one->next = two;, it verified that two is a pointer to a node and generates code to move that pointer to the second slot for the struct node pointer.