链表修炼指南-阿里云开发者社区

链表修炼指南

注：想要对链表有较为深入地掌握，那么就必须要对C语言关于结构体、指针的知识烂熟于心，如果读者觉得对于这方面的知识还有所欠缺，不妨先看看：

1. 链表的基本概念及结构

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

举个形象的例子：

链表就像现实生活中的火车的车厢，一节车厢通过一个“链条”链接这另一节车厢，而在链表中，这个“链条”就是指针。

1.1 链表的物理结构

物理结构指的是存储设备上数据的实际排列方式。它关注数据在硬件上的存储方式

我们知道链表是用来存储数据的，因此有一个存放数据的数据域，而为了实现逻辑的连续性，就需要一个指针来指向下一个节点的地址，因此我们需要一个存放指针的指针域。

链表的物理结构如图所示：

1.2 链表的逻辑结构

逻辑结构指的是数据的组织方式和相互关系，与数据在存储设备上的实际排列无关。它关注数据在逻辑上的组织、访问和操作方式。

实际上，我们将链表比做成现实生活中的火车就是说明它的逻辑结构。

链表的逻辑结构如图所示：

1.3 总结

从上图中我们可以看出，链式结构在逻辑上是连续的，但在物理结构上是不一定连续的
现实生活中节点一般都是从堆上申请的。
从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

2. 链表的分类

在讨论链表的类别之前，我们有必要知道何为链表的节点：

如果我们将链表比作为火车的话，那么链表的节点就可以说是火车的车厢。
火车的车厢盛放的是货物、乘客。链表的节点放的就是上面所说的数据域和指针域。
火车的车厢也可以不存放货物。同样，链表的节点也可以不存放实际有效的数据。通常情况下，我们会将不存放有效数据的节点放在链表的头，因此这个节点又可以叫哨兵位。

链表的结构非常多样，以下情况组合起来就有8中链表结构：

单向或者双向

带头（哨兵位）和不带头

循环或者非循环

那么这8种链表结构我们都要学习掌握吗？当然不是，我们只要掌握以下两种最常用的结构，那么其他的6中结构自然也就水到渠成，很容易掌握了。

3. 无头单向非循环链表（单链表）

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

3.1 结构的定义

typedef int SLDataType; //链表存储数据的类型
typedef struct SListNode
{
  SLDataType data;
  struct SListNode* next; //指向下一个节点的指针域
}SLNode;

3.2 打印链表数据

void SListPrint(const SLNode* phead);

通过链表结构的指针域，可以很方便的找到下一个节点，从而实现对整个链表数据的打印

void SListPrint(const SLNode* phead)
{
  SLNode* cur = phead;
  while (cur)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}

3.3 尾插

void SListPushBack(SLNode** phead, SLDataType val);

要在原链表的尾部插入节点，首先就需要先新建一个节点

3.3.1 新建节点

SLNode* BuyListNode(SLDataType val)
{
  SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
  if (NULL == newNode)
  {
    perror("malloc");
    exit(-1);
  }
  newNode->next = NULL;
  newNode->data = val;
  return newNode;
}

新建完节点后，就要实现插入了。而要实现尾插，就先要通过循环找到链表的尾tail。

找到tail之后，可能有许多小伙伴会想当然地认为，直接tail->next = newNode不就实现尾插了吗？

实际上，我们还要**考虑一种情况：如果链表的第一个节点就是空呢？**那么这个时候，我们就要将newNode直接赋值给头pHead，即pHead = newNode

注：我们知道，形参的改变不会影响实参，如果我们要改变实参指针pList，那么我们就要传入它的地址&pHead。始终记住：

要通过函数改变一个变量，那么就要传入这个变量的地址。

要改变结构体指针本身，就要传入这个指针的指针，即二级指着

要改变结构体成员，则只需要传入这个结构体的地址就可以。

3.3.2 尾插

void SListPushBack(SLNode** phead, SLDataType val)  //一定要传入二级指针
{
  SLNode* newNode = BuyListNode(val); //创建新节点
    //如果头为空，那么直接赋值
  if (*phead == NULL)
  {
    *phead = newNode;
    return;
  }
    //否则，先通过循环找到尾
  SLNode* tail = *phead;
  while (tail->next)
    tail = tail->next;
    //最后实现链接
  tail->next = newNode;
}

3.3.3 错误示例

没有传入二级指针

void SListPushBack(SLNode* phead, SLDataType val);

这会导致当头结点为空时，不能成功实现插入。

找尾并实现链接的代码错误

一部分小伙伴会这样写：

SLNode* tail = *phead;
while (tail)
    tail = tail->next;
tail = newNOde;

此时，tail指向的就是NULL，这些同学想当然地以为tail = newNode这一操作就相当于使newNode成为新的尾。

但显然，这个想法是错误的，尽管tail和链表的最后一个节点指向的都是NULL，但tail = newNode这一操作只是改变了tail的指向，使tail指向了newNode而没有实际变链表的结构

如图：

3.4 尾删

void SListPopBack(SLNode** phead);

要删除尾部节点，首先就先要判断链表是否为空，如果链表为空，自然就不能尾删了。

要删除最后一个节点，一种方法是找到倒数第二个节点，然后free最后一个节点，最后令倒数第二个节点指向NULL即可。

此外，仍然要考虑一种特殊情况：如果此链表只有一个有效节点（phead->next == NULL），那么要删除这个节点，就相当于要改变头结点，由上面的分析可以得出，必须要传入二级指针才可以实现头部的删除。另外，删除头部的节点的操作也和其他节点的不一样

void SListPopBack(SLNode** phead)
{
  assert(*phead); //链表不能为空
    //如果要删除头结点
  if ((*phead)->next == NULL)
  {
    free(*phead);
    *phead = NULL;  //一定要置空，否则再进行插入操作时就会出错
    return;
  }
    //找到倒数第二个节点
  SLNode* tail = *phead;
  while (tail->next->next)
    tail = tail->next;
    //释放最后一个节点
  free(tail->next);
  tail->next = NULL;
}

3.4.1 错误示例

第一个错误仍是没有传入二级指针导致无法正确删除第一个节点
有些小伙伴的代码可能会这样写：

SLNode* tail = *phead;
while (tail->next)
    tail = tail->next;
tail = NULL;

这个错误也和尾删的第二个错误一样，这仅仅只是改变了tail的指向，而没有改变链表结构

3.5 头插

void SListPushFront(SLNode** phead, SLDataType val);

由于这是没有哨兵位的链表，因此每一次头插，都会使新节点newHead成为新的头，所以要传入二级指针确保插入正确

void SListPushFront(SLNode** phead, SLDataType val)
{
  SLNode* newNode = BuyListNode(val);
    //如果链表为空，直接让newHead成为新的头
  if (*phead == NULL)
  {
    *phead = newNode;
    return;
  }
  newNode->next = *phead;
  *phead = newNode;
}

3.6 头删

void SListPopFront(SLNode** phead);

同样，首先要判断链表是否为空。

每一次头删都会改变原有的头，因此要传入二级指针

void SListPopFront(SLNode** phead)
{
  assert(*phead); //链表不能为空
  SLNode* temp = *phead;  //先保存原有的头
  *phead = (*phead)->next;  //改变头
  free(temp); //释放原有的头
}

3.7 查找

SLNode* SListFind(const SLNode* phead, SLDataType val)
{
  SLNode* cur = phead;
  while (cur)
  {
    if (cur->data == val) //如果找到，就返回该节点
      return cur;
    cur = cur->next;
  }
  return NULL;  //没找到就返回空
}

3.8 在pos节点的后面插入

void SListInsertAfter(SLNode* pos, SLDataType val);

显然，当pos为空时就不要插入了

void SListInsertAfter(SLNode* pos, SLDataType val)
{
  assert(pos);
  SLNode* newNode = BuyListNode(val);
    //注意，下面两条代码的顺序不能改变
    //如果改变，那么链接关系就会错误
  newNode->next = pos->next;
  pos->next = newNode;
}

为什么不在pos之前插入？

如果要在pos之前插入，那么就必须先要找到原来pos前的节点。那么就要传入链表头pList，同时要通过循环来找到pos前的位置，相较于在pos后插入，在pos前插入的效率显然就低了很多

3.9 删除pos节点后的节点

void SListEraseAfter(SLNode* pos);

显然，当pos为空或者pos->next == NULL，就不需要删除了。

void SListEraseAfter(SLNode* pos)
{
  assert(pos);
  assert(pos->next);
    SLNode* temp = pos->next;
  pos->next = pos->next->next;
    free(temp);
}

为什么不删除pos前的节点？

如果删除pos前的节点，那么就必须先要找到原来pos前的节点。那么就要传入链表头pList，同时要通过循环来找到pos前的位置，相较于删除pos后的节点，删除pos前节点的效率显然就低了很多

3.10 链表的销毁

void SListDestory(SLNode** phead)
{
  SLNode* temp = *phead;
  while (temp)
  {
    *phead = (*phead)->next;
    free(temp);
    temp = *phead;
  }
}

4. 练习

学习完单链表的基本操作，我们可以通过这一题来巩固：设计单链表👉 题目解析
如果对于链表的增删查改都有了较深的掌握，那就必须学会链表的常用经典操作：反转链表👉题目解析
学会了反转链表，那么我们就可以利用反转链表来做这一题：回文链表👉题目解析
还有一项必须掌握的技能：合并两个有序链表👉题目解析
做完上面几题，想必你已经对单链表有了较为深入的认知，如果你还学有余力，不妨做做下面几题，来提高能力：

环形链表——I👉题目解析

环形链表——II👉题目解析

复杂链表的复制👉题目解析

如果大家做的还不过瘾，也可以去看看👉leetcode链表合集

5. 有头双向循环链表

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了

5.1 结构的定义

typedef int LTDataType; //存储数据的类型
typedef struct ListNode
{
  LTDataType _data; //数据域
  struct ListNode* _next; //后继指针域
  struct ListNode* _prev; //前驱指针域
}ListNode;

5.2 打印链表数据

void ListPrint(ListNode* pHead);

和单链表类似，都是通过循环遍历链表，逐个打印。

注：由于存在哨兵位，因此第一个打印的节点是pHead->next而不是pHead

void ListPrint(ListNode* pHead)
{
  assert(pHead);
  ListNode* cur = pHead->_next; //从哨兵位后开始打印
    //如果回到了哨兵位，就说明遍历完成
  while (cur != pHead)
  {
    printf("%d->", cur->_data);
    cur = cur->_next;
  }
  printf("NULL\n");
}

5.3 初始化哨兵位

ListNode* ListCreate()
{
  ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
  if (NULL == newNode)
  {
    perror("malloc");
    exit(-1);
  }
    //由于还没有插入数据，因此前驱指针和后继指针都指向自己
  newNode->_prev = newNode;
  newNode->_next = newNode;
  return newNode;
}

5.4 尾插

void ListPushBack(ListNode* pHead, LTDataType x);

创建新节点的操作在前文已经讲过，故不再赘述。

相较于单链表，由头循环双向链表的尾插操作便简单许多。链表的尾就是pHead->_prev，用时间复杂度为O(1)的操作便可以解决。

void ListPushBack(ListNode* pHead, LTDataType x)
{
  assert(pHead);
  ListNode* newNode = BuyListNode(x); //新节点
  ListNode* tail = pHead->_prev;  //尾部节点
    //实现链接
  tail->_next = newNode;
  newNode->_prev = tail;
  newNode->_next = pHead;
  pHead->_prev = newNode;
}

5.5. 尾删

void ListPopBack(ListNode* pHead);

同样，先要对链表进行判空操作，如果链表为空，就不需要删除了。

由于链表双向和循环的性质，也可以用时间复杂度为O(1)的操作很快实现尾删：

void ListPopBack(ListNode* pHead)
{
  assert(pHead);
  assert(pHead->_next != pHead);  //链表不为空
  ListNode* tail = pHead->_prev;  //最后一个节点
  ListNode* tailPrev = tail->_prev; //倒数第二个节点
    //实现链接
  free(tail);
  tailPrev->_next = pHead;
  pHead->_prev = tailPrev;
}

5.6 头插

void ListPushFront(ListNode* pHead, LTDataType x)
{
  assert(pHead);
  ListNode* newNode = BuyListNode(x);
  newNode->_next = pHead->_next;
  pHead->_next->_prev = newNode;
  newNode->_prev = pHead;
  pHead->_next = newNode;
}

5.6 头删

void ListPopFront(ListNode* pHead)
{
  assert(pHead);
  assert(pHead->_next != pHead);  //除哨兵位外，链表不能为空
  ListNode* pNext = pHead->_next; //记录要删除的节点
    //实现删除
  pHead->_next = pNext->_next;
  pNext->_next->_prev = pHead;
  free(pNext);
}

5.7 查找

ListNode* ListFind(ListNode* pHead, LTDataType x)
{
  assert(pHead);
  ListNode* cur = pHead->_next; //哨兵位不存放有效数据，故从哨兵位的后一个开始找
    //如果回到了哨兵位，就说明遍历完成
  while (cur != pHead)
  {
    if (cur->_data == x)
    {
      return cur;
    }
    cur = cur->_next;
  }
  //没找到就返回空
  return NULL;
}

6. 练习

了解了有头双向循环链表的基本操作，可以做这一题来进行巩固：实现双向链表👉题目解析

7. 链表和顺序表的比较

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，物理上不一定连续
随机访问	支持	不支持
任意位置插入或者删除元素	可能需要搬移元素，效率低，O(N)	只需要修改指针指向，O(1)
插入	动态顺序表，空间不够需要扩容	没有容量概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低

链表修炼指南