【数据结构】【版本1.1】【线性时代】——链式之力-阿里云开发者社区

引言

数据结构世界拥有了顺序表，就进阶来到了链表，本节内容为最简单的链表——单链表（Single Linked List）

数据结构世界有了顺序的力量基本运作，但是世界本源还是太弱小，世界随时容易破灭，所以链式的力量加入其中，带来了一种极其强大的神通——空间链接和跳跃

一、顺序表的问题及思考

让我们回顾一下顺序表：

1. 中间/头部的插⼊删除，时间复杂度为O(N)

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

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

思考：如何解决以上问题呢？

二、链表的概念与结构

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

链表的结构跟火车车厢相似，将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是 独立存在 的。

车厢是独立存在的，且每节车厢都有车门。想象⼀下这样的场景，假设每节车厢的车门都是锁上的状态，需要 不同的钥匙 才能解锁， 每次只能携带⼀把 钥匙的情况下如何从车头走到车尾？

最简单的做法：每节车厢里都放⼀把下⼀节车厢的钥匙。

在链表里，每节“车厢”是怎样的呢？

与 顺序表 不同的是，链表⾥的每节"车厢"都是 独立申请 下来的空间，我们称之为 “结点/节点”

节点的组成主要有两个部分：当前节点要保存的数据和保存下⼀个节点的地址（指针变量）。

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

为什么还需要指针变量来保存下⼀个节点的位置？

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

三、单链表的实现

3.1 定义

这里注意，在结构体内嵌套结构体，一定要表明struct，而不能直接使用typedef后的名称（要不然你可能会像我一样，一脸懵得看着n个错误提示）

3.2 打印

先来看看怎么实现链表的打印，这样更有助于我们理解它的结果

先用cur指针接受头部地址，当cur不为NULL时，则打印当前节点的数据，并将该节点存储的下一节点的地址赋值给cur ，这样cur指针就能一直访问整个链表，直到最后一个节点（该节点存储地址为NULL）

3.3 头插

链表插入数据，则要生成一个新节点（malloc动态开辟内存），再将数据放入新节点中，初始地址为NULL。然后再将之前的头部地址赋值给新节点的next指针，最后把新节点的地址赋值给头部地址（也就是外部传进来的链表指针）。

可能很多人有疑惑，为什么要用二级指针呢？请看接下来的测试

与顺序表不同的是，我们不再创建结构体，而是创建结构体指针，初始指向NULL。那么，我们要在函数内改变外部指针指向的地址，就要使用二级指针。

改后版本（后面有介绍原因）

3.4 创建新节点

我们发现，进行尾插时，同样要生成新节点，申请空间……一系列操作 ，所以我们可以把它该过程写成一个函数，以增强函数的复用性

3.5 尾插

同样，先申请新节点，再用循环一直向后访问，找到最后一个节点的地址，解引用操作将新节点的地址赋值给节点内的next指针变量

易错提醒： 要找的是最后一个节点的地址，而不是节点内部的next中的地址（NULL），所以千万不要写成以下形式，不然不仅链接不上，还会造成内存泄漏！

此时你可能会有疑惑，这里好像也不用二级指针也可以呀？实际上，并不可以。因为没有考虑到空链表的存在（你可以试试直接尾插会发生什么后果）

如果为NULL，则直接将新节点的地址传给外部的链表指针

运行结果

3.6 尾删

尾部删除的实现思路，主要是找到倒数第二个节点，解引用将其next指针指向的空间（最后一个节点）释放，再赋值为NULL

方法一

除了tail指针，再创建一个prev指针，每次先将tail中的地址赋值给prev，tail再指向下一个节点。当tail指向最后一个节点时，prev则指向倒数第二个节点

方法二

tail指针解引用当前节点的next后，继续找到下一个节点进行第二层解引用 （相当于探测范围往后移了一个节点），最终停止时，tail也指向倒数第二个节点

有了之前的经验，在调试中我们发现，以上方法只适用于多个节点，但是单个节点与空链表并未处理

对于一个节点，我们直接释放空间，并赋值为NULL；而对于空链表，我们直接断言assert，保证其不为空（暴力检查）

运行结果

这样，我们就实现了特殊到一般的思路，也是正常程序调试和优化的思路

3.7 头删

那么此时，我们有了经验，直接按空链表，一个节点和多个节点的思路实现

头部删除的实现思路，就是将链表指针的地址改成第二个节点的，并将第一个节点的空间释放

仅靠一个指针无法完成操作，因为链表指针指向第二个节点后，无法对第一个节点操作，所以再创建一个cur指针，记录第一个节点的地址，方便释放

但是此时，我们又发现，其实对多个节点的操作，对一个节点同样有效，所以我们可以简化代码

运行结果

所以，我们不仅要有分类的思想，也要有整合的思想，化一为多，化多为一。

3.8 查找与修改

链表的查找实现就比较简单了，找到返回对应节点的地址，找不到返回NULL

大家有没有发现，其实能查找，也意味着能修改，因为我们获取了该节点的地址，自然能在外部解引用修改数据，这样，一个函数就有两个功能 ——查找和修改

运行结果

3.9 指针断言

这里说一下关于assert断言的情况，并不是所有函数参数的指针都需要断言，而是要根据实际情况分析而定。

打印与查找，则不需要断言，因为空链表也可以打印，也可以查找，就比如你的银行账户没有钱，就不能显示出来看看，不能查询吗？

头插与尾插，对于其二级指针需要断言，一级指针不用，因为pphead指向链表指针plist，所以不能为空，而链表指针可为空（即为空链表）

头删与尾删，其二级指针与一级指针都要断言，除了pphead不能为空，*pphead也不能为空，因为空链表就不能进行删除操作

3.10 指定插入

这里有两种插入方式，在pos前插入和在pos后插入

在pos前插入

首先断言pphead和pos，再找到pos前一个节点的地址（方法与尾删相同，创建prev指针），然后创建新节点，最后将它们链接起来

其次，再考虑特殊情况，如果pos为头部地址时，即为头插，可复用头插函数

在pos后插入

相比于在pos前插入，单链表其实更适合在pos后插入，直接创建新节点，进行链接即可

注意：链接的过程有顺序问题，不能写反了，要不然会环状链接

运行结果

3.11 指定删除

这里也有两种删除方式，在pos删除和在pos后删除

在pos删除

实现思路与指定插入大致相同

运行结果

在pos后删除

同样，相比于在pos位置删除，单链表其实更适合在pos后删除，这里用一个next指针，保存pos下一个节点的地址，在pos链接往后第二个节点后，方便对pos后节点空间释放

运行结果

3.12 销毁

链表的销毁也比较简单，在每次循环内临时创建一个新指针next，记录下一个节点的地址，让cur释放所指空间后，还可以找到下一个节点，最后把链表指针解引用置空

当然，这里你也可以传一级指针，不在函数内部把外部的链表指针置为NULL，而在外部手动置空，跟free函数的用法一样，实现半自动

这样我们就完成了对单链表的增删查改等功能的实现

四、单链表oj题

仅仅了解单链表的知识是不够的，让我们来刷刷题吧！

876.链表的中间结点（LeetCode）-CSDN博客

21.合并两个有序链表（LeetCode）-CSDN博客

19.删除链表的倒数第N个结点（LeetCode）-CSDN博客

206.反转链表（LeetCode）-CSDN博客

234.回文链表（LeetCode）-CSDN博客

面试题 02.04. 分割链表（LeetCode）-CSDN博客

160.相交链表（LeetCode）-CSDN博客

看到这里了还不给博主扣个：
⛳️ 点赞☀️收藏 ⭐️ 关注！

💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖

拜托拜托这个真的很重要！

你们的点赞就是博主更新最大的动力！

有问题可以评论或者私信呢秒回哦。

源代码

slist.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
//单链表
typedef int SLDataType;
typedef struct SListNode
{
  SLDataType data;
  struct SListNode* next;
}SLNode;
 
//打印
void SLPrint(SLNode* phead);
 
//头插
void SLPushFront(SLNode** pphead, SLDataType x);
//尾插
void SLPushBack(SLNode** pphead, SLDataType x);
//头删
void SLPopFront(SLNode** pphead);
//尾删
void SLPopBack(SLNode** pphead);
 
//查找
SLNode* SLFind(SLNode* phead, SLDataType x);
 
//在pos前指定插入
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x);
//在pos后指定插入
void SLInsertAfter(SLNode* pos, SLDataType x);
 
//在pos指定删除
void SLErase(SLNode** pphead, SLNode* pos);
//在pos后指定删除
void SLEraseAfter(SLNode* pos);
 
//销毁
void SLDestroy(SLNode* phead);

slist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"slist.h"
 
void SLPrint(SLNode* phead)
{
  SLNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
 
SLNode* BuySLNode(SLDataType x)
{
  SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
 
  return newnode;
}
 
void SLPushFront(SLNode** pphead, SLDataType x)
{
  assert(pphead);
  SLNode* newnode = BuySLNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}
 
void SLPushBack(SLNode** pphead, SLDataType x)
{
  assert(pphead);
  //1.空链表
  //2.非空链表
  SLNode* newnode = BuySLNode(x);
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    SLNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
 
void SLPopFront(SLNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  SLNode* cur = *pphead;
  *pphead = (*pphead)->next;
  free(cur);
}
 
void SLPopBack(SLNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  //空链表
  //一个节点
  //多个节点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLNode* tail = *pphead;
    while (tail->next->next)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
 
    //SLNode* prev = NULL;
    //SLNode* tail = *pphead;
    //while (tail->next)
    //{
    //  prev = tail;
    //  tail = tail->next;
    //}
    //free(tail);
    //prev->next = NULL;
  }
}
 
SLNode* SLFind(SLNode* phead, SLDataType x)
{
  SLNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
 
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{
  assert(pphead);
  assert(pos);
  if (pos == *pphead)
  {
    SLPushFront(pphead, x);
  }
  else
  {
    SLNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLNode* newnode = BuySLNode(x);
    newnode->next = pos;
    prev->next = newnode;
  }
}
 
void SLInsertAfter(SLNode* pos, SLDataType x)
{
  assert(pos);
  SLNode* newnode = BuySLNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
 
void SLErase(SLNode** pphead, SLNode* pos)
{
  assert(pphead);
  assert(pos);
  if (pos == *pphead)
  {
    SLPopFront(pphead);
  }
  else
  {
    SLNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}
 
void SLEraseAfter(SLNode* pos)
{
  assert(pos);
  assert(pos->next);
  SLNode* next = pos->next;
  pos->next = pos->next->next;
  free(next);
}
 
//void SLDestroy(SLNode** pphead)
//{
//  assert(pphead);
//  SLNode* cur = *pphead;
//  while (cur)
//  {
//    SLNode* next = cur->next;
//    free(cur);
//    cur = next;
//  }
//  *pphead = NULL;
//}
 
void SLDestroy(SLNode* phead)
{
  SLNode* cur = phead;
  while (cur)
  {
    SLNode* next = cur->next;
    free(cur);
    cur = next;
  }
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"slist.h"
 
void TestSList1()
{
  SLNode* plist = NULL;
  //头插
  SLPushFront(&plist, 1);
  SLPushFront(&plist, 2);
  SLPushFront(&plist, 3);
  SLPushFront(&plist, 4);
  SLPushFront(&plist, 5);
  //尾删
  SLPopBack(&plist);
  SLPopBack(&plist);
  //打印
  SLPrint(plist);
}
 
void TestSList2()
{
  SLNode* plist = NULL;
  //尾插
  SLPushBack(&plist, 1);
  SLPushBack(&plist, 2);
  SLPushBack(&plist, 3);
  SLPushBack(&plist, 4);
  //打印
  SLPrint(plist);
}
 
void TestSList3()
{
  SLNode* plist = NULL;
  //尾插
  SLPushBack(&plist, 1);
  SLPushBack(&plist, 2);
  SLPushBack(&plist, 3);
  SLPushBack(&plist, 4);
  //尾删
  SLPopBack(&plist);
  SLPopBack(&plist);
  //SLPopBack(&plist);
  //SLPopBack(&plist);
  //SLPopBack(&plist);
  //打印
  SLPrint(plist);
}
 
void TestSList4()
{
  SLNode* plist = NULL;
  //尾插
  SLPushBack(&plist, 1);
  SLPushBack(&plist, 2);
  SLPushBack(&plist, 3);
  SLPushBack(&plist, 7);
  SLPushBack(&plist, 6);
  SLPushBack(&plist, 5);
  SLPushBack(&plist, 4);
  //头删
  SLPopFront(&plist);
  SLPopFront(&plist);
  SLPopFront(&plist);
  SLPopFront(&plist);
  //打印
  SLPrint(plist);
}
 
void TestSList5()
{
  SLNode* plist = NULL;
  //头插
  SLPushFront(&plist, 1);
  SLPushFront(&plist, 2);
  SLPushFront(&plist, 3);
  SLPushFront(&plist, 4);
  SLPushFront(&plist, 5);
  //查找
  SLNode* pos = SLFind(plist, 3);
  if (pos)
  {
    SLInsert(&plist, pos, 40);
    SLInsertAfter(pos, 50);
  }
  //打印
  SLPrint(plist);
}
 
void TestSList6()
{
  SLNode* plist = NULL;
  //头插
  SLPushFront(&plist, 1);
  SLPushFront(&plist, 2);
  SLPushFront(&plist, 3);
  SLPushFront(&plist, 4);
  SLPushFront(&plist, 5);
  //查找
  SLNode* pos = SLFind(plist, 3);
  if (pos)
  {
    SLErase(&plist, pos);
    SLEraseAfter(pos);
  }
  //打印
  SLPrint(plist);
}
 
void TestSList7()
{
  SLNode* plist = NULL;
  //尾插
  SLPushBack(&plist, 1);
  SLPushBack(&plist, 2);
  SLPushBack(&plist, 3);
  SLPushBack(&plist, 4);
  //打印
  SLPrint(plist);
  //销毁
  SLDestroy(plist);
  plist = NULL;
}
 
int main()
{
  TestSList7();
  return 0;
}

【数据结构】【版本1.1】【线性时代】——链式之力

引言

一、顺序表的问题及思考

二、链表的概念与结构

三、单链表的实现

3.1 定义

3.2 打印

3.3 头插

3.4 创建新节点

3.5 尾插

3.6 尾删

3.7 头删

3.8 查找与修改

3.9 指针断言

3.10 指定插入

3.11 指定删除

3.12 销毁

四、单链表oj题

源代码

slist.h

slist.c

test.c

热门文章

最新文章

相关课程

相关电子书