链表是一种用于存储数据的数据结构，通过如链条一般的指针来连接元素。它的特点是插入与删除数据十分方便，但查找与读取数据的表现欠佳。

1、单链表(只有一个指向后继元素的指针)

2、双链表(既有指向后继元素的指针，也有指向前驱元素的指针)

3、循环链表(最后一个元素的指针指向第一个元素，形成一个环)

为什么需要链表

数组就是一块连续的内存空间，有了这块内存空间的首地址，就能直接通过下标计算出任意位置的元素地址。

链表不一样，链表并不需要一整块连续的内存空间存储元素。链表的元素可以分散在内存空间的天涯海角，通过每个节点上的 next, pre 指针，将零散的内存块串联起来形成一个链式结构。

这样做的好处很明显，首先就是可以提高内存的利用效率，链表的节点不需要挨在一起，给点内存 new 出来一个节点就能用，操作系统会觉得这娃好养活。

另外一个好处，它的节点要用的时候就能接上，不用的时候拆掉就行了，从来不需要考虑扩缩容和数据搬移的问题，理论上讲，链表是没有容量限制的（除非把所有内存都占满，这不太可能）。

当然，不可能只有好处没有局限性。数组最大的优势是支持通过索引快速访问元素，而链表就不支持。

单链表

链表由一系列的结点组成（链表中的每个元素都可称为结点），对于单链表而言，它的结点包含两部分： 数据域：存储当前结点的数据 指针域：存储当前结点的下一个结点（后继结点）的地址

struct node{
    int data; //存数据
    node *next;//存下一个数据点的地址
};

在使用之前，首先要定义一个空链表(NULL),并用一个指针head(通常称为头指针)指向该链表；

node *p,*head=NULL;//定义节点p和链表头结点，NULL是常量，代表空
p=new node();//向系统申请内存空间
p->data=10;//指针的成员变量访问符为->
//(*p).data=x;//指针的另外一种写法 
delete p;//使用完结点，需要释放该结点占用的空间

使用单链表存储 n 个数据

#include<bits/stdc++.h>
using namespace std;
struct node{
    int data; //存数据
    node *next;//存下一个数据点的地址
};
//输入n个数据，存储在一个单链表中
node *p,*head=NULL; 
void create(){
    int n,x;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        p=new node();
        p->data=x;
        p->next=head;
        head=p;
    }
} 
void print(){
    node *q=head;
    while(q!=NULL){
        cout<<q->data<<" ";
        q=q->next;
    }
}
int main() { 
    create();
    print();
    return 0;
}

每次新输入的数据都插入在头结点，简称头插法。在CSP中，一般不会考察如何构建一个单链表，重点考察如何在链表中插入和删除元素，这是每年的重要考点。

插入

如果已知单链表中 P 和 Q 是前后相邻的两个结点，现在需要在 P 和 Q 结点之间，插入新结点 R ，需要完成的操作是什么？

可以将问题分为几个步骤:

1、首先明确P和Q的关系，如图所示：P->next为Q。

​

2、要在P和Q结点之间插入新结点R,则需要完成两步操作：先把R的next指针指向Q,然后将P的next指针指向R。

​

R->next=P->next;//将新结点R的next指针指向Q结点，即原来p->next就是Q
//R->next=Q;//Q本身就是指针变量，这样也可以
P->next=R;//再将P结点的next指针指向R结点

删除

单链表结点P、Q、R是相邻的三个结点，要求删除Q结点。

分为两步：

1、将P结点的next指针指向R结点

2、释放Q结点的内存(delete操作)

p->next=Q->next;
delete Q;

双链表

单链表的数据之间的连接是单向的，而双链表数据元素之间的连接是双向的，可以前后互相寻址，因此双链表相邻数据之间的逻辑关系是如下图所示。

双链表的每一个结点，包含三个部分：

1、数据项，存储这个结点的数据。

2、前驱指针，这个指针指向前一个结点的地址。

3、后去指针，这个指针指向下一个结点的地址。

struct dnode{
    int data;//数据项
    dnode *prev;//前驱指针
    dnode *next;//后继指针
};

手写双链表很少考核，重点还是双链表的结点插入和删除操作。

插入

双链表的结点插入：在相邻的两个结点P和Q之间插入结点R,需要完成的操作步骤。

由于双链表每个结点都有前驱指针和后继指针，因此操作比单链表复杂一些，相邻两结点之间插入新结点前后如何所示：

​

​ 插入结点后(虚线为新的指针指向示意)

在双向链表中插入结点需要修改三个指针：前驱结点的后继指针，新结点的前驱指针、新结点的后继指针。具体步骤：

1、找到插入位置的前驱结点P和后继结点Q

2、创建新结点R,将R的前驱指针指向P,后继指针指向Q

3、修改P的后继指针为R,Q的前驱指针为R

R->next=P->next;//将原来P的next指针赋值给R的next,相当于把R->next指向Q
R->prev=Q->prev;//将原来Q的prev指针赋值给R的prev,相当于把R->prev指向P
P->next=R;//把P的next指针指向新结点R
Q.prev=R;//把Q的prev指针指向新结点R

删除

双链表的结点删除：在相邻的三个结点P、Q、R，删除Q结点需要完成的操作步骤。

双链表的结点删除操作比插入操作要简单一些，在双向链表中删除结点需要修改三个指针：前驱结点的后继指针、后继结点的前驱指针、待删除结点。具体步骤：

1、找到待删除结点Q的前驱结点P和后继结点R

2、修改前驱结点P的后继指针为Q的后继结点

3、修改后继结点R的前驱指针为Q前驱结点P

4、删除结点Q,释放内存空间

P->next=Q->next;//修改前驱结点P的后继指针为Q的后继结点
R->prev=Q->prev;//修改后继结点R的前驱指针为Q的前驱结点P
delete Q;//释放空间

循环链表

1、单向循环链表

2、双向循环链表

单向循环链表的数据结点插入、删除操作与单链表一致。

双向循环链表的数据结点插入、删除操作与双链表一致。

​ ​ 单向循环链表 ​ ​ 双向循环链表

STL 中的list

STL中的list是一种双向链表，可高效进行插入和删除元素。需要在机试题中使用链表，一般可以使用list。

list<node> lst;//node指的是数据元素的类型，lst是双链表的名称

list中还有多个函数课供调用：

#include<bits/stdc++.h>
using namespace std;
list<int> lst;
list<int>::iterator it;//定义迭代器 it,含义与指针类似
int n,x; 
int main() { 
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        lst.push_back(x);
    }
    for(it=lst.begin();it!=lst.end();it++){
        //需要注意的是循环条件it!=lst.end(),不能用大于小于来判断，必须用不等于
        cout<<*it<<" ";  //it是指针 
    }
    return 0;
}

历年初赛真题回顾

1、（CSP-J2019） 链表不具有的特点是（）

​ A. 插入删除不需要移动元素

​ B.不必事先估计存储空间

​ C.所需空间与线性表长度成正比

​ D.可随机访问任一元素

2、（CSP-J2020）链表不具有的特点是（）。

​ A.可随机访问任一元素

​ B.不必事先估计存储空间

​ C.插入删除不需要移动元素

​ D.所需空间与线性表长度成正比

3、（CSP-J2022）运行以下代码片段的行为是（ ）。

int x = 101;
int y = 201;
int *p = &x;
int *q = &y;
p = q;

​ A.将 $x$ 的值赋为 $201$

​ B.将 $y$ 的值赋为 $101$

​ C.将 $q$ 指向 $x$ 的地址

​ D.将 $p$ 指向 $y$ 的地址

4、链表和数组的区别包括（ ）。

A.数组不能排序，链表可以

B.链表比数组能存储更多的信息

​ C.数组大小固定，链表大小可动态调整

​ D.以上均正确

5、以下哪组操作能完成在双向循环链表结点 $p$ 之后插入结点 $s$ 的效果（其中，next 域为结点的直接后继，prev 域为结点的直接前驱）：（ ）。

A. p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;
B. p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
C. s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
D. s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

6、假设有一个链表的节点定义如下：

struct Node { int data; Node* next; }

现在有一个指向链表头部的指针：Node* head。如果想要在链表中插入一个新节点，其成员 data 的值为 42，并使新节点成为链表的第一个节点，下面哪个操作是正确的？

A. Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;
B. Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;
C. Node* newNode = new Node; newNode->data = 42; head->next = newNode;
D. Node* newNode = new Node; newNode->data = 42; newNode->next =head;