本文适合初级和中级学习：刚学过编程语言，正在学数据结构的编程新手；学过基础数据结构，但是对代码的掌握还不够熟练的读者。
链表的特点是用一组位于任意位置的存储单元存线性表的数据元素，这组存储单元可以是连续的，也可以不连续。链表是容易理解和操作的基本数据结构，它的操作有初始化、添加、遍历、插入、删除、查找、排序、释放等。有单向链表和双向链表，如图1.1所示，上面是单向链表，下面是双向链表。
■ 图1.1 单向链表和双向链表
链表的各结点首尾相接，最后的next指针指向第一个data，第一个的pre指针指向最后的data。单向链表只有一个遍历方向，双向链表有两个方向，比单向链表的访问方便一点，也快一点。在需要频繁访问前后几个结点的场合，可以使用双向链表。
使用链表时，可以直接用STL list，也可以自己写链表。如果自己写代码实现链表，有两种编码实现方法：动态链表、静态链表。在算法竞赛中为加快编码速度，一般用静态链表或者STL list。
下面以“例1-1. 洛谷P1996”为例题，在后面3个小节中分别给出动态链表、静态链表、STL链表等3种方案、5种代码。经过作者的精心整理，这5种代码的逻辑和流程完全一样，只有链表的实现不一样，方便读者学习，把关注点放在链表的实现上。
● 例1-1. 约瑟夫问题 洛谷P1996
题目描述：n个人，编号为1~n，按顺序围成一圈，从第一个人开始报数，数到 m 的人出列，再由下一个人重新从 1 开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈，请依次输出出圈人的编号。
输入：一行，2个整数n、m。
输出：一行n个整数，按顺序输出每个出圈人的编号。1 ≤ m, n ≤ 100。
输入样例：10 3
输出样例：3 6 9 2 7 1 8 5 10 4
01
展开全文
动态链表
动态链表需要临时分配链表结点、使用完毕后释放链表结点。优点是能及时释放空间，不使用多余内存；缺点是需要管理空间，容易出错。动态链表是“教科书式”的标准做法。
下面的代码用动态单向链表实现了例1.1。
02
静态链表
提示/
动态链表虽然“标准”，但是竞赛中一般不用。算法竞赛对内存管理要求不严格，为加快编码速度，一般就在题目允许的存储空间内静态分配，省去了动态分配和释放的麻烦。
静态链表使用预先分配的一段连续空间存储链表。从物理存储的意义上讲，“连续空间”并不符合链表的本义，因为链表的优点就是能克服连续存储的弊端。但是，用连续空间实现的链表，在逻辑上是成立的。具体有两种做法：
①定义链表结构体数组，和动态链表的结构差不多；
②使用一维数组，直接在数组上进行链表操作。
本节给出3段代码：用结构体数组实现单向静态链表、用结构体数组实现双向静态链表、用一维数组实现单向静态链表。
1. 用结构体数组实现单向静态链表
用结构体数组实现单向静态链表，注意静态分配应该定义在全局，不能定义在函数内部。
2. 用结构体数组实现双向静态链表
3. 用一维数组实现单向静态链表
这是最简单的实现方法。定义一个一维数组nodes［］，nodes［i］的i就是节点的值，而nodes［i］的值是下一个节点。它的使用环境很有限，因为它的节点只能存一个数据，就是i。
03
STL list
在算法竞赛或工程项目中常常使用C++ STL list。list 是双向链表，由标准模板库(Standard Template Library,STL)管理，通过指针访问节点数据，高效率地删除和插入。请读者自己熟悉list的初始化、插入、删除、遍历、查找、释放。下面是用list实现例1.1的代码。
《算法竞赛》系列推文正在连载中，欢迎持续关注！
扫码优惠购书
