一、链表的概念
链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
二、链表和数组的区别：
1、数组静态分配内存，链表动态分配内存。
2、数组在内存中是连续的，链表是不连续的。
3、数组利用下标定位，查找的时间复杂度是O(1)，链表通过遍历定位元素，查找的时间复杂度是O(N)。
4、数组插入和删除需要移动其他元素，时间复杂度是O(N)，链表的插入或删除不需要移动其他元素，时间复杂度是O(1)。
数组的优点
1、随机访问性比较强，可以通过下标进行快速定位。
2、查找速度快
数组的缺点
1、插入和删除的效率低，需要移动其他元素。
2、会造成内存的浪费，因为内存是连续的，所以在申请数组的时候就必须规定七内存的大小，如果不合适，就会造成内存的浪费。
3、内存空间要求高，创建一个数组，必须要有足够的连续内存空间。
4、数组的大小是固定的，在创建数组的时候就已经规定好，不能动态拓展。
链表的优点
1、插入和删除的效率高，只需要改变指针的指向就可以进行插入和删除。
2、内存利用率高，不会浪费内存，可以使用内存中细小的不连续的空间，只有在需要的时候才去创建空间。大小不固定，拓展很灵活。
链表的缺点
查找的效率低，因为链表是从第一个节点向后遍历查找。
单链表和双链表
三、链表环问题
判断是否有环
定义一个快指针和一个慢指针，快指针一次走两步，慢指针一次走两步，会出现两种情况，情况一指针走到了空的位置，那就说明这个链表不带环。情况二两个指针相遇，说明这个链表带环。
获得入环节点
如果不考虑空间复杂度，可以使用一个map来记录走过的节点，这个指针一直向后遍历如果遇到空，说明这个链表不带环，也就没有入环节点，如果没有遇到空，如果遇到第一个在map中存在的节点，就说明回到了出发点，这个节点就是环的入口节点。如果不建立额外的空间，先使用快慢指针判断这个链表是否有环，如果有环将相遇节点记录，然后一个指针从链表的起始位置开始一次走一步，另一个指针从记录的节点开始一次走一步，当两个节点再次相遇，这个相遇节点就是环的入口节点。
以上转载自https://blog.csdn.net/Shuffle_Ts/article/details/95055467
四、链表的使用
1、链表的创建（头插法、尾插法）
#include<iostream> #include<stdlib.h> using namespace std; struct node { int x; node* next;//指向结构体的一个指针 }; node *Head, *End; void add(int m) { node *temp = (struct node*)malloc(sizeof(struct node));//强制类型转换+分配地址空间 //节点赋值，m是一个整数型的值，要把它变成结构体类型才能放进链表里 temp->x = m; temp->next = NULL; if (Head== NULL)//头指针为空，说明链表为空，那么temp即是头指针，也是尾指针 { Head = temp; End = temp; } else { //链表不为空的情况，让尾指针指向当前节点，同时尾指针后移，为下一次添加节点准备 End->next = temp; End = temp; //上面的是尾插，即在链表尾部加入节点 //如果在链表头部加入节点，让头指针指向当前节点，同时头指针前移就可以 //Head->next=temp; //Head=temp; } } int main() { Head = (struct node*)malloc(sizeof(struct node)); End = (struct node *)malloc(sizeof(struct node)); Head->next = NULL; End = Head; int n, m; cin>>n; for(int i=0;i<n;i++) { cin>>m; add(m); } node *temp = Head; while (temp->next!=NULL)//链表的遍历 { temp = temp->next; cout << temp->x << ' '; } cout<<endl; return 0; }
#include<iostream> #include<stdlib.h> using namespace std; struct node { int x; node* next;//指向结构体的一个指针 }; node *Head, *End; int main() { Head = (struct node*)malloc(sizeof(struct node)); End = (struct node *)malloc(sizeof(struct node)); End = Head; int n, m; cin>>n; for(int i=0;i<n;i++) { cin>>m; node *temp=(struct node*)malloc(sizeof(struct node)); temp->x=m; temp->next=NULL; End->next=temp; End=temp; } node *temp = Head; while (temp->next!=NULL)//链表的遍历 { temp = temp->next; cout << temp->x << ' '; } cout<<endl; return 0; }
2、链表的删除、插入和清空
void clear()//清空链表 { node *now=Head; while(now!=NULL) { node *temp=now; now=now->next; free(temp); } Head=NULL; End=NULL; } void insert(int pos,int num)//在第pos个位置增加一个节点 { node *now=Head; for(int i=0;i<pos-1;i++) now=now->next; node *temp=(struct node*)malloc(sizeof(struct node));//创建一个新节点保存数字num temp->x=num; temp->next=now->next; now->next=temp; } void del(int num)//在链表中删除数据域为num的节点 { node *now=Head; while(now->next!=NULL) { node *temp=now;//保存num所在节点的前一个节点 now=now->next; if(now->x==num) { temp->next=now->next; free(now); now=temp; } } }
完整代码
#include<iostream> #include<stdlib.h> using namespace std; struct node { int x; node* next;//指向结构体的一个指针 }; node *Head, *End; void add(int m) { node *temp = (struct node*)malloc(sizeof(struct node));//强制类型转换+分配地址空间 //节点赋值，m是一个整数型的值，要把它变成结构体类型才能放进链表里 temp->x = m; temp->next = NULL; if (Head== NULL)//头指针为空，说明链表为空，那么temp即是头指针，也是尾指针 { Head = temp; End = temp; } else { //链表不为空的情况，让尾指针指向当前节点，同时尾指针后移，为下一次添加节点准备 End->next = temp; End = temp; //上面的是尾插，即在链表尾部加入节点 //如果在链表头部加入节点，让头指针指向当前节点，同时头指针前移就可以 //Head->next=temp; //Head=temp; } } void clear()//清空链表 { node *now=Head; while(now!=NULL) { node *temp=now; now=now->next; free(temp); } Head=NULL; End=NULL; } void insert(int pos,int num)//在第pos个位置增加一个节点 { node *now=Head; for(int i=0;i<pos-1;i++) now=now->next; node *temp=(struct node*)malloc(sizeof(struct node));//创建一个新节点保存数字num temp->x=num; temp->next=now->next; now->next=temp; } void del(int num)//在链表中删除数据域为num的节点 { node *now=Head; while(now->next!=NULL) { node *temp=now;//保存num所在节点的前一个节点 now=now->next; if(now->x==num) { temp->next=now->next; free(now); now=temp; } } } int main() { Head = (struct node*)malloc(sizeof(struct node)); End = (struct node *)malloc(sizeof(struct node)); Head->next = NULL; End = Head; int n, m; cin>>n; for(int i=0;i<n;i++) { cin>>m; add(m); } del(2); del(3); node *temp = Head; while (temp->next!=NULL)//链表的遍历 { temp = temp->next; cout << temp->x << ' '; } cout<<endl; return 0; }