引入：

顺序表中间或者头部的插入/删除，时间复杂度为O（N）,增容需要申请新的空间，拷贝数据，释放旧空间，会有不少的消耗。而且增容一般都是程2倍的增长，势必会有一定的空间浪费。我们该如何解决这个问题呢？这时我们就要用到链表了。

链表：

概念：链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域，一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向NULL（空指针）。

链接的入口点称为链表的头节点，也就是head。

听着有些抽象，我们用火车来举例理解。

如图， 高铁的每节车厢就相当于链表中的一个节点，车厢内部（数据域）存放乘客和货物（实际数据）

车厢连接处（指针域）：挂钩等连接着下一节车厢（存储下一节点的地址）

火车头（head节点）：==整个列车的起点

最后一节车厢连接处是空的（NULL指针），表示列车结束。

了解完整体的结构之后，我们来看一下这列“火车”的内部长什么样子。

结点：

链表里的每节 "车厢" 都是独立申请下来的空间，我们称之为结点（节点）。

图中指针变量 plist 保存的是第一个结点的地址，我们称 plist 此时 “指向” 第一个结点；如果我们希望 plist“指向” 第二个结点，只需要修改 plist 保存的内容为 0x0012FFA0。

链表中每个结点都是独立申请的（即需要插入数据时才去申请一块结点的空间），我们需要通过指针变量来保存下一个结点位置，才能从当前结点找到下一个结点。

链表的性质

1. 链式结构在逻辑上是连续的，在物理结构上不一定连续
2. 结点一般是从堆上申请的
3. 从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续

结合前面学到的结构体知识，我们可以给出每个结点对应的结构体代码： 假设当前保存的结点为整型：

1  struct SListNode
2  {
3      int data;              // 结点数据
4      struct SListNode* next; // 指针变量用于保存下一个结点的地址
5  };

当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数据，也需要保存下一个结点的地址（当下一个结点为空时保存的地址为空）。

当我们想要从第一个结点走到最后一个结点时，只需要在当前结点拿上下一个结点的地址就可以了。

那在给定的链表结构中，如何实现结点从头到尾的打印？

链表的打印

执行步骤说明：

1.pcur 指针变量保存第一个节点的地址

2.对 pcur 解引用，拿到 next 指针变量中的地址（下一个节点的地址）

3.赋值给 pcur，此时 pcur 保存第二个节点的地址，即 pcur “指向了下一个节点”

4.循环执行，直到 pcur 为 NULL 时结束遍历

void SLTPrint(SLTNode* phead){
    SLTNode *pcur = phead;
    while(pcur){
        printf("%d ",pcur->data);
        pcur = pcur->next;
    }
    printf("\n");
}

实现单链表：

1  typedef int SLTDataType;
2  typedef struct SListNode
3  {
4      SLTDataType data;       // 结点数据
5      struct SListNode* next; // 指针保存下一个结点的地址
6  }SLTNode;
7
8  void SLTPrint(SLTNode* phead);
9
10
11 //头部插入删除/尾部插入删除
12 void SLTPushBack(SLTNode** pphead, SLTDataType x);
13 void SLTPushFront(SLTNode** pphead, SLTDataType x);
14 void SLTPopBack(SLTNode** pphead);
15 void SLTPopFront(SLTNode** pphead);
16
17 //查找
18 SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
19 //在指定位置之前插入数据
20 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
21 //删除pos结点
22 void SLTErase(SLTNode** pphead, SLTNode* pos);
23
24 //在指定位置之后插入数据
25 void SLTInsertAfter(SLTNode* pos, SLTDataType x);
26 //删除pos之后的结点
27 void SLTEraseAfter(SLTNode* pos);
28
29 //销毁链表
30 void SListDestroy(SLTNode** pphead);

3.3 链表的分类

链表的结构非常多样，以下情况组合起来就有 8 种（2 × 2 × 2）链表结构：

• 带头 / 不带头
• 单向 / 双向
• 循环 / 不循环
• 虽然有这么多的链表结构，但是我们实际中最常用的还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

双向链表

 概念与结构

带头双向循环链表

这里的 “带头” 跟前面我们说的 “头结点” 是两个概念。前面单链表阶段称呼不严谨，为了方便理解直接称为单链表的头结点；带头链表里的头结点实际为哨兵位，哨兵位结点不存储任何有效元素，仅作为链表的首尾边界标记。

实现双向链表

1  typedef int LTDataType;
2  typedef struct ListNode
3  {
4      struct ListNode* next; // 指针保存下一个结点的地址
5      struct ListNode* prev; // 指针保存前一个结点的地址
6      LTDataType data;
7  }LTNode;
8
9
10 //void LTInit(LTNode** pphead);
11 LTNode* LTInit();
12 void LTDestroy(LTNode* phead);
13 void LTPrint(LTNode* phead);
14
15 bool LTEmpty(LTNode* phead);
16
17 void LTPushBack(LTNode* phead, LTDataType x);
18 void LTPopBack(LTNode* phead);
19
20 void LTPushFront(LTNode* phead, LTDataType x);
21 void LTPopFront(LTNode* phead);
22
23 //在pos位置之后插入数据
24 void LTInsert(LTNode* pos, LTDataType x);
25
26 void LTErase(LTNode* pos);
27 LTNode* LTFind(LTNode* phead, LTDataType x);

顺序表与链表的分析

不同点	顺序表	链表 (单链表)
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持，时间复杂度 O (1)	不支持，遍历访问 O (N)
任意位置插入删除元素	可能需要搬移元素，效率低，时间复杂度 O (N)	需先遍历找到目标位置；已知前驱时仅需修改指针
空间特性	动态顺序表空间不够时需要扩容，存在空间浪费	无容量概念，按需申请释放，不存在空间浪费
应用场景	元素高效存储 + 频繁访问	任意位置高效插入和删除