Pointer learning diary (IV) use structure and pointer (linked list)

typdef struct node
{
struct node *link;
int value;
}Node;

Node* new;// Create a pointer to the structure new

new = (node*）malloc（sizeof（node));
I want to explain this sentence specifically .
First ,new Is a pointer variable to the structure .
secondly ,malloc yes void The pointer , This means that it can be converted to any type of pointer ,
and （node） Is the cast character . Force the return value to Pointer of structure （ And new The same type ）, and sizeof（node） Is to allocate this size of memory space to new.

Linked list ：
When the teacher taught the pointer in the first semester of freshman , Many students do not understand the use of pointers , Then I only know that pointer is learning C and C++ It's a headache , Of course, some students even talk loudly after class “C and C++ It's entirely possible not to learn , The pointer is so troublesome , Learn later JAVA Isn't the front end fragrant ”. This one , I am also a freshman , We don't know whether it's right or wrong , But as OLE told uncle , Meet with difficulties , Face it with a smile . If the pointer cannot be turned off ,c and c++ Basically, it came to an end , Less c and c++ The company of , I want to say that I must pay a certain price in the future （ Is it a little far away ？） All in all , The first nightmare of many students when they learn data structures as freshmen is linked lists , The linked list is probably the first program for all beginners to use pointers on a large scale .

typedef struct NODE
{
    
        struct NODE *link;
		int          value;
}Node;//typedef Definer , It can be used directly in the future Node Define new values 

#include<stdlib.h>
#include<stdio.h>
/* Let's use insert function to explain here */

/ The code here draws on some 《C And a pointer 》 If you are interested in the teaching code in, you can refer to the original book /
int insert(Node* current,int new_value)
{
    
	Node* previous;
	Node* new;
	
	while(current->value < new_value)
	{
    
		previous = current;
		current = current->link;
	}
	
	new = (Node*)malloc(sizeof(Node));
	if(new = NULL)
	{
    
		return -1;
	}
	
	new->value = new_value;

	new->link = current;
	previous->link = new;
	return 1;
}

Do you think this code is good ？ wrong , This code has limitations , If the inserted value is smaller than the first value ,
Then the system will report an error ！ Because there was no while loop ,previous It is not assigned at all , Indirect access to a NULL The value of is not allowed ！
And if you enter a value that is larger than all the values, it is not possible , here current The value pointed to is also NULL, Not for one NULL Indirect access by pointer to ！
So we can improve the cycle

while（current->value < new_value&&current！=NULL）
{
    
	previous = current;
	current = current->link;
}

But if you think about it carefully, you will find , This can only solve the second problem , The first problem has not been solved .
We might as well conduct a thorough optimization , Whether it is inserted in the first place or at the end is a special case .

The key to eliminating special situations lies in ： We have to realize that , Each node in the linked list has a pointer to it . For the first node , This pointer is the root pointer ; For other nodes , This pointer is the previous node link Field . The point is that each node has a pointer to it ！

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

int insert(Node** linkp,int new_value)//linik Is a pointer to the pointer 
{
    
	Node* current;
	Node* new;
    while((current = *linkp) != NULL && current->value < new_value)
    {
    
    	linkp = &current->link;
    	// When we call a member in a class or a member in a struct   We need to use it  ->  Operator 
    }
    
    new = (Node*)malloc(sizeof(Node));
    if(new == NULL)
    {
    
    	return -1;
    }
    new->value = new_value;
	
	new->link = current;
	*linkp = new;
	
	return 1;
}

I still admire this optimization , Assign the address that needs to be changed to linkp, then current Assign a value to new->link, because current->link No change , So nothing will happen to the linked list .