As we all know, the linked list is a data structure, and the linked list has the advantages that arrays and other sequential lists do not have, so how do we learn the linked list?
The author also read a lot of information and didn't understand it, but finally when I understood it, I found that most of the authors' writing methods were too old-fashioned and deliberately made the template out, which was very difficult to understand, so I had the idea of writing one by myself.
In fact, it is very simple. For those without foundation, we only need to master the creation of linked list, insert elements, delete elements and traverse output elements. For more in-depth study, we should read articles written by more professional people.
I The first is the form of linked list:
struct node{
int x=0; //This is the data stored in each linked list space.
struct node *next; //This is a pointer to the next space.
};
II First look at the first content, create a linked list and make it empty.
#include<iostream>
#include<stdlib.h>
using namespace std;
struct node{
int x=0;
struct node *next;
};
//How to write in the main function
int main()
{
struct node *head； //Head pointer
struct node *node=(struct node*)malloc(sizeof(struct node));
//First linked list space
node->x=1; //You can make it equal to the number you want
node->next=NULL; //The pointer to the first space is null
head=node; //Let the head pointer point to our first space
return 0;
}
//two
//Create a new function to create a linked list, so you also need to use the main function
struct node * create()
{
struct node *list;
struct node *node=(struct node*)malloc(sizeof(struct node));
//First linked list space
node->x=1; //You can make it equal to the number you want
node->next=NULL; //The pointer to the first space is null
list=node; //Let the head pointer point to our first space
return list;
}
int main()
{
int i;
struct node *head,*node;
head=create(); //Call this function
return 0;
}Note: at this time, we can see that head is a head pointer, and its first element is 1, while its next pointer is empty. At this time, a linked list with the first element not empty and the pointer empty is created. The first element can also be the element we enter. At this time, we must pay attention that we can't do any operation on head, It acts as a head pointer. We need it when we want to find elements or output.
III So how do we input elements? (look at the code first and then explain it)
Note: when creating the linked list, we need to pay attention to one point, that is, we need to first apply for a space and input the elements, and then let the last pointer of our linked list point to it, and then we update the last pointer of the linked list to facilitate the input of the next element
#include<iostream>
#include<stdlib.h>
using namespace std;
struct node{
int x=0;
struct node *next;
};
//one
//Input directly in main, which is more suitable for novices. You can ignore the reason for the function.
int main()
{
int i,j,k,a,b;
struct node *head,*node=(struct node*)malloc(sizeof(struct node));
node->x=1;
node->next=NULL;
head=node;
for(i=2;i<5;i++)
{
struct node* tmp=(struct node*)malloc(sizeof(struct node));
tmp->x=i; //It can be self input data, such as scanf ("% d", & TMP - > C);
tmp->next=NULL; //Make its pointer null to facilitate subsequent traversal.
node->next=tmp; //Let the pointer of node point to the newly created space.
node=node->next; //Then update the node pointer to the node pointer to point to the next one.
}
return 0;
}
//two
//Using a function for input is actually copying the above code and writing it outside. (as we all know, inline function)
void scanff(struct node * list)
{
int i;
struct node *node;
node=list;
for(i=2;i<5;i++)
{
struct node* tmp=(struct node*)malloc(sizeof(struct node));
tmp->x=i; //It can be self input data, such as scanf ("% d", & TMP - > C);
tmp->next=NULL;
node->next=tmp;
node=node->next;
}
}
int main()
{
int i;
struct node *head,*node;
head=create(); //Call this function
scanff(head); //Input in the calling function,
return 0;
}
IV Next, I have to talk about traversing the output
Similarly, looking at the code first, it is very simple to create a pointer and let it point to the head pointer, because every time we input, the last pointer is NULL, so as long as P is not empty, we can output the data, and then we update p to point to the next one.
struct node*p;
p=head; //Remember, don't move the head pointer. Replace it with a p pointer
while(p)
{
cout<<p->x;
p=p->next;
}
V Delete an element. If you can understand the above, it will not be a problem. In the example, the value of the element is used as the deletion standard,
void det(struct node* p, int n) //Note that the passed in p is the header pointer and n is the value of the deleted element
{
struct node *num;
while(p->x!=n) //When the element pointed to by p is not n, we let it point to the next one
{
num=p; //One thing to note is that we must remember the structure of the pointer to p every time
p=p->next; //This place is a little abstract. I'll explain it separately later. Remember to write it like this first.
}
num->next=p->next; //At this time, num - > next should point to N, and P - > next points to which one after n is
What? Because we while It was updated before it came out p，After the update, p->x by n，p->next Points to the next one, before the update? num->next Is pointing n So let's point to n Pointer to (i.e num)Point to p of next Pointer, skipped n This element.
free(p); //Finally, you just need to free up the space where p is located
p=num->next;
}
Vi Insert an element (the last content, be patient) if it is inserted according to the size and the size is different (if there are the same, I believe you can easily write it after reading it. I'm not trying to save trouble, but it's really difficult to understand when there are few restrictions on the first contact)
struct node* insert(struct node *p ,int n)
{
struct node *list;
struct node *tmp=(struct node*)malloc(sizeof(struct node));
list=p; //Easy to return head pointer;
tmp->x=n;
tmp->next=NULL;
struct node *num;
if(p->x>=n) //If the inserted element should be in the first place
{
list=tmp; //In the returned list, the header pointer is updated, and the original header pointer address becomes the second.
tmp->next=p;
}
else
{
while(p->x<n&&p->next!=NULL)
{
num=p;
p=p->next;
}
if(p->next==NULL) //When the inserted element is in the last bit
p->next=tmp;
else //Insert element in the middle
{
num->next=tmp;
tmp->next=p;
}
}
return list;
}
VII Look at the complete combination
#include<iostream>
#include<stdlib.h>
using namespace std;
struct node{
int x=0;
struct node *next;
};
struct node* insert(struct node *p ,int n)
{
struct node *list;
struct node *tmp=(struct node*)malloc(sizeof(struct node));
list=p;
tmp->x=n;
tmp->next=NULL;
struct node *num;
if(p->x>=n)
{
list=tmp;
tmp->next=p;
}
else
{
while(p->x<n&&p->next!=NULL)
{
num=p;
p=p->next;
}
if(p->next==NULL)
p->next=tmp;
else
{
num->next=tmp;
tmp->next=p;
}
}
return list;
}
struct node * create()
{
struct node *list;
struct node *node=(struct node*)malloc(sizeof(struct node));
node->x=1;
node->next=NULL;
list=node;
return list;
}
void scanff(struct node * list)
{
int i;
struct node *node;
node=list;
for(i=2;i<5;i++)
{
struct node* tmp=(struct node*)malloc(sizeof(struct node));
tmp->x=i;
tmp->next=NULL;
node->next=tmp;
node=node->next;
}
}
int main() //Main function
{
int i;
struct node *head,*node;
head=create(); //Create table
scanff(head); //Input element
head=insert(head,1);//Insert an element
struct node *p;
p=head; //output
while(p)
{
cout<<p->x;
p=p->next;
}
return 0;
}