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).
The use of linked list structure can overcome the disadvantage that array linked list needs to know the data size in advance , Linked list structure can make full use of computer memory space , Flexible dynamic memory management . But the linked list loses the advantage of random array reading , At the same time, the linked list increases the pointer field of the node , The space cost is quite large . The most obvious advantage of linked lists is that , Regular arrays arrange associated items in a different way than the data items are ordered in memory or on disk , Data access is often converted in different order . Linked lists allow you to insert and remove nodes at any location on the list , But random access is not allowed . There are many different types of linked lists ： One way linked list , Double linked list and circular list . Linked list can be implemented in many programming languages . image Lisp and Scheme The built-in data type of such language includes the access and operation of linked list . Programming language or object oriented language , as C,C++ and Java Generating linked lists with variable tools . The content of these definitions can be received on Baidu Encyclopedia , Here's an excerpt . Let's talk about the specific process of establishing a single linked list . Here is my code , There are detailed notes . Establishing single chain list by head inserting method
#include<stdio.h>
#include<stdlib.h>
typedef struct linklist
{
char data;
struct linklist* next;
}node, * link_list;
link_list creatlist(link_list L) {
link_list head = NULL;// Initialization header
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>
typedef struct linkednode
{
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