一、链表的概念
◆ 线性表的优点
A、无需为表示结点间的逻辑关系而增加额外的存储空间；
B、可方便地随机存取表中的任一元素。
◆ 线性表的缺点
A、插入或删除平均需要移动一半的结点；
B、顺序表要求占用连续的存储空间。
⚪ 注意：链表结构并不一定占用连续的内存空间，其占用的内存空间可以不连续！
◆ 链表的基本概念
A. 结点(Node)组成：数据域，指针域
B. 数据域：存储数据元素本身
C. 指针域：存储邻接元素的存储地址(位置)
D. 链接方式：单链表：每个结点只有一个指针域。双向链表：每个结点有两个指针域。循环链表：是一个首尾相接的链表。
E. 头指针：指向链表头结点的指针。
⚪ 链表的存储方式：链表可以通过指针来链接节点，因此不需要把数据存储在连续的空间上，所以删除和增加数据都很方便。
二、单向链表
◆ 指针是单向的，只能从左向右单向遍历数据。
◆ 循环链表：首尾相接，尾巴tail的next指针指向头部head的data。
◆ 有时场景比较简单，不需要循环，可以让第一个节点始终是头。
三、双向链表
有两个指针，pre指针指向前一节点，next指针指向后一节点。
循环：最后节点的next指针指向第一个节点，第一个节点的pre指针指向最后的节点。
四、链表的缺点
和数组相比，链表的缺点是查找慢
例如查找data等于某个值，需要遍历整个链表才能找到，计算量O(n)；而数组中通过下标可以直接访问到任意一个元素。
五、用数组模拟链表（静态链表）：“逻辑上是链表，物理上是数组”。
const int N = 10000; //按需要定义静态链表的空间大小
struct node{ //单向链表
int id; //这个节点的id
int data; //数据
int nextid; //指向下一个节点的id
}nodes[N]; //静态分配需要定义在全局
//为单链表的next指针赋初值，例如：
nodes[0].nextid=1;
for(int i=1;i<=n;i++){
nodes[i].id=i; //把第i个节点的id就赋值为i
nodes[i].nextid=i+1;//next指针指向下一个节点
}
nodes[n].nextid=1;//循环链表：尾指向头即可
//遍历链表：沿着nextid访问节点即可
//删除节点：比如删除now节点，找到now的前一个节点
nodes[preid].nextid = nodes[now].nextid;//跳过节点now，即删除now
now = nodes[preid].nextid; //更新now
//插入节点，略六、用指针实现链表
//单链表：头插法
#include <iostream>
using namespace std;
int n,x;
struct Node{ //结构体
int val; //值
Node *next; //下一个结点
}*head;
int main(){
cin>>n;
for(int i=1;i<=n;i++){ //生成n个结点的链表
cin>>x;
Node *p=new Node(); //定义一个新的结点
p->val=x;
p->next=head;
head=p;
}
for(Node *p=head;p;p=p->next){//从头开始输出
cout<<p->val<<' ';
}
cout<<endl;
return 0;
}单链表的插入和删除
1、插入
(1)在链表中间的p节点后面插入节点s【注意顺序不能交换)
☆ s->next=p->next
☆ p->next=s
(2)在链表的表头 head 后面插入节点 s【注意顺序不能交换)
☆ s->next=head
☆ head=s
2、删除:删除p节点后面的节点
☆ p->next=p->next->next
//双链表
#include <iostream>
using namespace std;
int n,x;
struct Node{ //结构体
int val; //值
Node *next,*pre;//next下一个结点,pre下一个结点
}*head,*tail;
int main(){
cin>>n;
for(int i=1;i<=n;i++){ //生成n个结点的链表
cin>>x;
Node *p=new Node(); //定义一个新的结点
p->val=x;
p->next=head;
if(p->next) p->next->pre=p;
head=p;
if(i==1) tail=p;
}
for(Node *p=head;p;p=p->next){//从头开始输出
cout<<p->val<<' ';
}
cout<<endl;
for(Node *p=tail;p;p=p->pre){//从尾开始输出
cout<<p->val<<' ';
}
cout<<endl;
return 0;
}双链表的插入和删除
1、插入
(1)在p节点后面插入节点s
☆ s->pre=p
☆ s->next=p->next
☆ p->next->pre=s
☆ p->next=s【必须放在最后】
(2)在p节点前面插入节点s
☆ s->pre=p->pre
☆ s->next=p
☆ p->pre->next=s
☆ p->pre=s【必须放在最后】
2、删除
(1)删除p节点后面的节点
☆ p->next->next->pre=p
☆ p->next=p->next->next
(2)删除p节点前面的节点
☆ p->pre->pre->next=p
☆ p->pre=p->pre->pre
(3)删除p节点
☆ p->pre=p->next
☆ p->next=p->pre
//循环链表
#include <iostream>
using namespace std;
int n,x;
struct Node{ //结构体
int val; //值
Node *next,*pre;//next下一个结点,pre下一个结点
}*head,*tail;
int main(){
cin>>n;
for(int i=1;i<=n;i++){ //生成n个结点的链表
cin>>x;
Node *p=new Node(); //定义一个新的结点
p->val=x;
p->next=head;
if(p->next) p->next->pre=p;
head=p;
if(i==1) tail=p;
}
tail->next=head;
head->pre=tail;
int m=2*n;//准备输出2圈
for(Node *p=head;m;p=p->next,m--){//从头开始输出
cout<<p->val<<' ';
}
cout<<endl;
int k=3*n;//准备输出3圈
for(Node *p=tail;k;p=p->pre,k--){//从尾开始输出
cout<<p->val<<' ';
}
cout<<endl;
return 0;
}七、在编写程序时，链表还可以直接使用C++的STL list
| 操作 | 说明 |
| size() | 链表元素个数 |
| empty() | 链表是否为空 |
| push_front() | 在链表头添加元素 |
| push_back() | 在链表末尾添加元素 |
| unique() | 将链表中相邻的重复元素去除，如果重复元素不相邻，则无效 |
| sort() | 升序排序 |
| pop_back() | 删除链表尾 |
| pop_front() | 删除链表头 |
| front() | 读队头 |
| back() | 读队尾 |
| reverse() | 反转链表 |
| insert(it) | 在it位置插入元素 |
在信息学竞赛中，我们经常使用数组模拟链表，比如邻接表。