链表
单链表
单链表的整表创建
静态链表
循环链表
双向链表
双向循环链表
顺序存储与链式存储对比
扩展：缓存
操作技巧

链表

因为顺序存储结构相邻两元素的存储位置也具有邻居关系，所以无法快速接入，而删除后，当中就会在流出空袭，自然需要弥补。

链表（线性表的链式存储结构）：用一组任意存储单元存储线性表的数据元素，这组存储单元可以存在内存中未被占用的任意位置。

比起顺序存储结构每个数据元素只需要存储一个位置就可以了。现在链式存储结构中，除了要存储元素信息外，还要存储它的后继元素的存储地址（指针）。

数据域：存储数据元素信息的域
指针域：存储直接后继位置的域，存储的信息称为指针或链

这两部分信息组成数据元素称为存储映像，称为结点（Node）。

头指针
- 头指针是指链表指向第一个结点的指针，若链表有头节点，则是指向头结点的指针
- 头指针具有标识作用，所以常用头指针冠以链表的名字
- 无论链表是否为空，头指针均不为空
- 头指针是链表的必要元素
头结点
- 数据域可以不存储任何信息
- 也可以存储如线性表的长度等附加信息
- 头节点的指针域（也就是头指针）指向第一个结点的指针
- 头结点不一定是链表的必须要素

typedef struct Node
{
    ElemType data;
    struct Node* Next;
} Node;
typedef struct Node* LinkList;

单链表

获取操作

获得第 i 个数据的算法思路：

声明一个结点 p 指向链表第一个结点，初始化 j 从 1 开始
当 j<1 时，就遍历链表，让 p 的指针向后移动，不断指向下一个结点，j 累加 1
若到链表末尾 p 为空，则说明第 i 个元素不存在
否则查找成功，返回结点 p 的数据

插入操作

s->next = p-> next
p->next = s

删除操作

实现对链表中单个结点的删除操作，只需要将该结点的前继结点的指针绕过指向后继结点即可。

p->next = p->next->next
q = p->next; p->next = q->next

算法思路：

声明结点 p 指向链表第一个结点，初始化 j=1
当 j<1 时，就遍历链表，让 p 的指针向后移动，不断指向下一个结点，j 累加 1
若到链表末尾 p 为空，则说明第 i 个元素不存在
否则查找成功，将欲删除结点 p->next 赋值给 q
单链表的删除标准语句 p->next=q->next
将 q 结点中的数据赋值给 e，作为返回
释放 q 结点
返回成功

单链表的整表创建

单链表和顺序存储结构不一样，它不像顺序存储结构这么集中，它可以很散，是一种动态结构。对于每个链表来说，它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成。

创建单链表的过程是一个动态生成链表的过程，从“空表”的初始状态，依次建立各元素结点，并逐个插入链表。

头插法算法思路：

声明结点 p 和计数器变量 i
初始化空链表 L
让 L 的头结点的指针指向 Null，即建立一个带头结点的单链表
循环
1. 生成新结点赋值给 p（p 是中介结点）
2. 随机生成数字赋值给 p 的数据域名 p->data
3. 将 p 插入到头结点与前一各新结点之间

尾插法

void CreateListTail(LinkList *L, int n)
{
    LinkList p, r;
    int i;
    srand(time(0)); /* 初始化随机数种子 */
    *L = (LinkList)malloc(sizeof(Node)); /* 为整个线性表 */
    r = *L; /* r 为指向尾部的结点 */
    for (i = 0; i<n; i++)
    {
        p = (Node *)malloc( sizeof(Node) ); /* 生成新结点 */
        p->data = rand()%100+1; /* 随机生成100以内的数字 */
        r->next=p;    /* 将表尾终端结点的指针指向新结点 */
        r=p; /* 将当前的新结点定义为表尾终端结点 */
    }
    r->next = NULL; /* 表示当前链表结束 */
}

单链表的整表删除

不需要单链表，需要将它销毁，以便释放内存，留给其他程序使用。

算法思路：

声明结点 p 和 q
将第一个结点赋值给 p
循环
1. 将下个结点赋值给 q
2. 释放 p
3. 将 q 赋值给 p

Status ClearList(LinkList *L)
{
    LinkList p,q;
    p=(*L)->next; /* p 指向第一个结点 */
    while(p) /* 没到表尾 */
    {
        q=p->next;
        free(p);
        p=q;
    }
    (*L) -> next = NULL; /* 头结点指针域为空 */
    return OK;
}

单链表的整表创建

顺序存储结构创建 => 数组的初始化

头插法建新链表：

先让新节点的 next 指向头节点之后
然后让表头的 next 指向新节点

静态链表

使用静态链表存储数据，数据全部存储在数组中（和顺序表一样），但存储位置是随机的，数据之间”一对一”的逻辑关系通过一个整形变量（称为”游标“，和指针功能类似）维持（和链表类似）。

数据域：用于存储数据元素的值
游标：其实就是数组下标，表示直接后继元素所在数组中的位置

静态链表中，除了数据本身通过游标组成的链表外，还需要有一条连接各个空闲位置的链表，称为备用链表。

备用链表的作用是回收数组中未使用或之前使用过（目前未使用）的存储空间，留待后期使用。也就是说，静态链表使用数组申请的物理空间中，存有两个链表，一条连接数据，另一条连接数组中未使用的空间。

循环链表

循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中，你应该可以看出来，它像一个环一样首尾相连，所以叫作“循环”链表。

双向链表

单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。而双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，相比单链表，双向链表支持O(1)找到前驱节点，这样也带来了双向链表操作的灵活性。

双向循环链表

顺序存储与链式存储对比

数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。
数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常时。链表本身没有大小的限制，天然地支持动态扩容。

在实际项目开发中，如果我们对内存的使用非常苛刻，那数组就更适合你。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片。

实践案例：

游戏中，注册个人信息，除了注册插入数据，大部分情况都是读取，应考虑顺序存储结构
游戏中玩家的武器和装备列表，随着玩家的游戏过程，可能会随时增加或删除，此时应考虑单链表结构
当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构

扩展：缓存

缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。

缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。常见的策略有三种：

先进先出策略 FIFO（First In，First Out）
最少使用策略 LFU（Least Frequently Used）
最近最少使用策略 LRU（Least Recently Used）

操作技巧

链表操作的一些技巧：

哨兵

使用哨兵，在链表初始化的时候，就给链表头指针指向一个哨兵节点，这个哨兵节点是不存储数据的，有了这个哨兵，链表的删除，插入操作就不需要再判断链表是否为空。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。别小看一个判断，当代码运行成千上万次这个影响是很大的，当然我们开发中，也不能只追求性能，忽视了代码的可读性，可维护等。这种利用哨兵简化编程难度的技巧，在很多代码实现中都有用到，比如插入排序、归并排序、动态规划等。

快慢两个指针

在操作链表的时候，多考虑如果使用快慢两个指针，可以帮我们简化思维。