I believe that the learning program of the ape friends are familiar with the linked list , This is a kind of storage structure that we encounter when learning data structure , On the issue of linked list , It's not as simple as we think , of course , It's not that hard . For beginners , It is abstract and complicated , We often think that , Abstract things need to be understood abstractly , We often see this in books , Abstract data structure , The way those definitions are made , It often makes beginners a little confused . Data structure needs strong logical thinking to understand , The problem of algorithm is usually not well solved , Logical thinking is not innate , What's more important is that we build this kind of thinking in the process of learning . It's like the synapses that we often build in our brains , Think more , Multi operation , You can be smart . therefore , We should have confidence and passion for this .

Linked list is a kind of discontinuous physical storage unit , Non sequential storage structure , The logical order of data elements is realized by the pointer link order in the linked list . A linked list consists of a series of nodes （ Each node is called a list element ） form , Nodes can be dynamically generated at runtime . Each node consists of two parts ： One is the data field where data elements are stored , The other is a pointer field that stores the address of the next node .
Compared with linear table order structure , Complex operation . Because it doesn't have to be stored in order , Linked list can be achieved when inserting O(1) The complexity of , It's much faster than the other linear sequential table , But finding a node or accessing a specific number of nodes requires O(n) Time of , The corresponding time complexity of linear table and sequential table is respectively O(logn) and O(1).

#include<stdio.h>
#include<stdlib.h>
{
char data;
head = (node*)malloc(sizeof(node));// Apply space for head node
node* p1, * p2;
char data;
head->next = NULL;// Must be preceded by a pointer to NULL, Otherwise, it's a wild pointer .
while ((data = getchar()) != '\n') { p1 = head;//p1 The pointer points to the head node p2 =
(node*)malloc(sizeof(node));// utilize p2 Pointer to create a new node p2->data = data;// Data field assignment
// The following is the key to establish a single linked list by head insertion p2->next = p1->next; p1->next = p2; } return head;
}
// The following is to traverse the created linked list
void print(link_list L) {
node* p;
p = L->next;
while (p!=NULL)
{
printf("%c", p->data);
p = p->next;
}

}
// Principal function
void main() {
link_list L = NULL;
L = creatlist(L);
print(L);

}
// Establishment of single chain list by tail insertion
#include<stdio.h>

#include<stdlib.h>

{
char data; struct linkednode* next;
}node, * link_list;// Structure and renaming of linked list node

link_list creat()// Create a linked list. The return type is the first address of the list

{
link_list L; node* p1, * p2; char data; L =
(node*)malloc(sizeof(node));// Open up storage space p2 = L; while ((data = getchar()) !=
'\n')// Enter enter to end input { // Table building process of tail insertion method p1 = (node*)malloc(sizeof(node)); p1->data =
data; p2->next = p1; p2 = p1; } p2->next = NULL; return L;
}

void print(link_list L)// Output the linked list

{
node* p; p = L->next; while (p != NULL) { printf("%c", p->data); p = p->next;
} printf("\n");
}

void main()

{
link_list L = NULL; printf(" Please input linked list node :\n"); L = creat(); print(L);
}
// Bold style, let's think about it here , Difference between head inserting and tail inserting in table building , Let's take a look at the key code of table building with head insertion method ： p2->next = p1->next;p1->next = p2;
The order of these two codes must not be reversed
Key code of tail interpolation ：p2->next = p1;p2 = p1;
It's easy to understand
This code can be understood by drawing , I hope you can think about it .

One more thing is important , It's about the wild pointer , We are not using the pointer after , It must be released , Otherwise you are vs There are also problems with running code in , You can try it yourself , There is a sentence at the end of the list ,
p2->next =
NULL; Think about why ,, Here, the tail insertion method is used to establish the linked list ,p2 Pointer moves to p1 place , After inserting nodes at the end , The successor of the tail is temporarily unknown , There is no direction , So you don't have to point to the node after you insert it NULL, Otherwise, there will be problems during traversal ,vs There will be access problems .

When creating linked list by head insertion method , If you apply for space for the head node , You need to point its successor to it for the time being KULL, such as head->next=NULL, You can think of this as an initialization . If not , It's not rigorous , It's very likely that something will go wrong .
last , I hope you can learn data structure well , It is very helpful for programming , We learn together , Common progress . Welcome to leave a message .

Technology
Daily Recommendation
views 1469
views 234
views 214
views 213
views 191
views 181