前言

在上一节中我们提到了顺序表有如下缺陷：

在头部/中间的插入与删除需要挪动数据，时间复杂度为O(N)，效率低；

增容需要申请新空间，可能会拷贝数据，释放旧空间，会有不小的消耗；

增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，如果我们再继续插入了5个数据，后面没有数据插入了，那么会浪费95个数据空间；

基于顺序表的这些不足，我们设计出了链表。

一、链表

1、链表的概念及结构

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

链表和顺序表的不同之处在于：顺序表不仅要求逻辑结构上也连续，还要求物理结构上连续；而链表只要求逻辑结构上连续，物理结构上可以不连续；

所谓的逻辑结构指的是数据在逻辑上是如何存储的，这是由人们主观想象出来的；而物理结构则是数据在物理内存中实际存储的方式，不随人们的主观意志而改变。

链表的结构图示如下：

从上面的图中我们也可以看出：链表在逻辑结构上连续指的是链表的每一个节点都记录着下一个节点的地址，我们可以根据此地址来找到链表的下一个节点，就好像它们被一根线连起来了一样；

而实际上链表的每一个节点都是在堆区上随机申请的，前一个节点的地址可能比后一个节点大，也可能比后一个节点小，二者之前其实并没有物理结构上的关系。

2、链表的分类

在实际应用中，链表根据带头/不带头、循环/不循环、双向/单向这三种选择一共可以组合出8种结构。

单向或者双向：双向链表对比单向链表来说，其结构体中会多一个结构体指针变量，用来指向前一个节点的地址。

带头或者不带头：带头与不带头其实区别就是链表最开始的时候会有一个节点，这个节点不用来存储数据，仅仅作为链表的头部使用，还是一个节点都没有。

循环或者非循环：非循环链表的最后一个节点的next指向NULL，而循环链表的最后一个节点的next指向链表的第一个节点。

3、最常用的两种链表

虽然链表有这么多中结构，但是我们实际中最常用还是以下两种结构：无头单向非循环链表和双向带头循环链表。

无头单向非循环链表

无头单向非循环链表结构最简单，一般不会单独用来存数据，实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等；另外这种结构在笔试面试中出现很多；其实如果不做特殊声明，一般情况下无头单向非循环链表指的就是我们的单链表；

带头双向循环链表

带头双向循环链表结构最复杂，一般用于单独存储数据；实际中我们使用的链表数据结构，都是带头双向循环链表；另外它虽然结构复杂，但是使用代码实现后会有很多优势，所以反而是链表中使用起来最简单的。

二、单链表的实现

由于单链表是其他结构链表学习的基础，且经常被用做其他数据结构的子结构，在笔试题中也最常被考到，所以下面我们用C原因来手动实现一个单链表，以此来加强我们对单链表的理解。

1、结构的定义

实现，与顺序表一样，单链表也需要一个变量来data来记录数据，且我们应该对data的类型重命名，使得我们的链表可以管理不同类型的数据；其次，由于单链表中需要存储下一个节点的地址，所以我们应该有一个指向结构体的指针。

//符号和结构的声明
typedef int SLTDataType;  //数据类型重命名
typedef struct SListNode   //链表的一个节点
{
  SLTDataType data;
  struct SListNode* next;  //存放下一个节点的地址
}SLTNode;

2、创建新节点

由于单链表的每一个节点都需要单独开辟，所以我们可以把创建节点封装成一个函数，避免在头插、尾插、任意位置插入这些位置重复实现。

需要注意的是，由于我们这里实现的单链表是不带头的，即单链表一开始就是空的，所以我们并不需要对其进行初始化操作，只需要定义一个指向NULL的节点指针 plist 即可。

//创建新节点
SLTNode* BuySLTNode(SLTDataType x)
{
  SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newNode == NULL)
  {
    perror("malloc fail");
    return NULL;  //如果malloc失败，返回NULL
  }
  newNode->data = x;
  newNode->next = NULL;
  return newNode;
}

3、在头部插入数据

特别注意：不管我们在什么地方插入数据，我们都需要传递二级指针，因为链表一开始是空的，所以我们在插入第一个数据的时候需要让 plist 指向我们新开辟的这一个节点，即头结点；而我们知道，要改变 int，需要传递 int*，要改变 int*，需要传递 int**，类比过来，这里的 plist 是一个结构体指针变量，我们想要改变它，让它从 NULL 变为第一个节点的地址，就需要传递结构体指针的地址，即二级指针才能实现。

其次，我们在改变节点中的next指针的时候使用的是结构体指针，即一级指针，而并没有用到二级指针，这是因为我们修改节点中的next是对结构体进行操作，而要改变结构体我们只需要使用结构体指针即可，而不用像上面修改结构体指针一样使用二级指针。

同时，结构体指针的地址是一定不为空的，因为即使是链表为空即 plis == NULL 的时候，&plist 也不等于空，所以我们需要对 pphead 进行断言，来保证代码的鲁棒性；而链表又是可能为空的，所以我们不需要对 *pphead (即 plist) 进行断言。

如果我们使用带头节点的单链表就不需要传递二级指针，因为不管我们如何对链表进行操作，头结点都始终不会改变。

//在头部插入数据
void SListPushFront(SLTNode** pphead, SLTDataType x)  //要改变plist，所以用二级指针来接收plist的地址
{
  assert(pphead);  //pphead为plist的地址，一定不为空
  //assert(*pphead);  //error：*pphead得到plist，而链表可能没有节点，所以plist可以为空，不用断言
  SLTNode* newNode = BuySLTNode(x);  //开辟新节点
  newNode->next = *pphead;
  *pphead = newNode;
}

4、在尾部插入数据

在尾部插入数据我们需要先找到的尾结点的前一个节点，因为我们需要让前一个节点的next指针指向新开辟的节点，然后让新开辟的节点的next指向尾结点，这样才能让我们的链表链接起来。

而我们的单链表只能找到下一个节点的地址，想要找到前一个节点需要从头开始遍历，所以单链表尾插的效率是比较低的，时间复杂度为O(N)，我们可以通过设计双向链表来解决这个问题。

//在尾部插入数据
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);  //plist的地址一定不为空
  SLTNode* newNode = BuySLTNode(x);
  if (*pphead == NULL)  //如果链表为空
  {
    newNode->next = *pphead;
    *pphead = newNode;
    return;
  }
  //如果链表不为空，我们需要找到链表的尾
  SLTNode* tail = *pphead;
  while (tail->next != NULL)
  {
    tail = tail->next;
  }
  tail->next = newNode;
}

5、查找数据

查找数据不会改变头结点，所以我们只需要传递一级指针。

//查找数据
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
  assert(phead);  //链表为空查找直接报错
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    if (cur->data == x)
      return cur;  //找到返回节点地址
    cur = cur->next;
  }
  return NULL;  //找不到返回空
}

6、在pos位置前插入数据

和尾插一样，我们需要从头遍历链表，找到 pos 节点的前一个节点，让该节点的next指向新开辟的节点，使得链表成功链接。

//在pos位置前插入数据
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pphead);
  assert(pos);
  if (pos == *pphead)  //如果pos等于*pphead，相当于头插
  {
    SListPushFront(pphead, x);
    return;
  }
  SLTNode* newNode = BuySLTNode(x);
  //找到pos位置的前一个节点
  SLTNode* prev = *pphead;
  while (prev->next != pos)
  {
    assert(prev);  //如果prev为空循环还没停止，说明在链表中找不到pos，直接报错
    prev = prev->next;
  }
  prev->next = newNode;
  newNode->next = pos;
}

7、在pos位置后插入数据

由于单链表在某一节点的前面插入数据时需要从头遍历寻找该节点的前一个节点，导致时间复杂度为O(N)，所以人们为了提高单链表的效率，为单链表单独设计了在pos位置后插入数据的函数；除了单链表，其他数据结构插入数据都是在前面插入。

//在pos位置之后插入数据
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pphead && pos);
  SLTNode* next = pos->next;
  SLTNode* newNode = BuySLTNode(x);
  pos->next = newNode;
  newNode->next = next;
}