一.链表的基础知识

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

• 概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
• 链表链表，表如其名，链表的结构就如同被连接起来了，只不过在中间连接链表的“绳索”是指针。
  
• 从基本结构图中我们可以看出：

• 1.链式结构在逻辑上是连续的，但与顺序表不同，在物理上链表是不一定连续的
  2.现实中，链表的节点一般都是从堆上申请出来的。
  3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

2.链表的分类

• 在实际中链表的结构非常多样，下面就简单的介绍几种
  
  
  

• 虽然链表有多种结构，但是最常用的还是这两种
  

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

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

二.无头单链表的实现

• 由于我们是初阶数据结构，且这是有关链表的第一篇博客，我们就先从最简单的无头单链表开始实现。
• 首先我们先把需要的几个功能的接口列出来然后咱们来一个一个介绍。

说明：以下包括后面的所有代码的函数名称等都是我根据该函数的功能编的，也就是说这些函数名等不唯一，你也可以起别的名字，不影响链表的使用，但就像给孩子取名一样，我们都不希望我们的孩子的名字叫狗蛋，二狗子什么的，实际上，在函数的命名中你瞎起名字就和这些差不多，因此我建议无论是现在还是以后的函数的命名最好都按照功能来命名，这样既增加了代码的可读性，也让人一看便知各个函数的功能。

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
    SLTDataType Data;
    struct SListNode * next;
}SLTNode;
//打印链表
void SLTPrint(SLTNode* phead);
//初始化链表
SLTNode* BuySListNode(SLTDataType x);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
// 找某个数
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);
//修改pos位置的值
void SLTModify(SLTNode**pphead, SLTNode* pos, SLTDataType x);
// 单链表的销毁
void SListDestroy(SLTNode** pphead);

• 注意：对接口的声明都包含在头文件中
• 先讲一下这里面需要注意的几个地方：
• 1.第一处的 typedef 实际是为了方便我们的使用，因为我们也不知道我们的链表是用来存储什么类型的数据的，因此我们这里就定义一个SLDataType，下面的代码中统一把数据类型用它来代替，这样一来，

• 我们以后想要改变存储的数据类型，只需要改动这里即可，比如我们现在想要存储double类型的数据

typedef double SLDataType;

• 2.关于我们的链表的结构体

typedef struct SListNode
{
    SLTDataType Data;
    struct SListNode * next;
}SLTNode;

1.初始化链表 BuySListNode

• 当我们想使用我们的链表时，首先就像变量一样需要先把它初始化一下

//初始化链表
SLTNode* BuySListNode(SLTDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
        perror("malloc failed:");
        exit(-1);
    }
    newnode->Data = x;
    newnode->next = NULL;
    return newnode;
}

• 我们首先通过malloc为我们链表的一个节点开辟了空间，然后通过perror判断了我们的malloc是否成功，如果成功，我们就把该链表的值置为我们输入的x，由于此时只有它一个节点，因此next置空，这样我们的一个节点就初始化好了。

2.打印链表 SLTPrint

• 当我们初始化成功后，我们就想把我们的链表打印一下，看看我们的链表是否成功初始化了，因此我们继续来写打印链表的函数

//打印链表
void SLTPrint(SLTNode* phead)
{
    SLTNode* cur = phead;
    while (cur)
    {
        printf("%d->", cur->Data);
        cur = cur->next;
    }
    printf("NULL\n");
}

• 我们定义了一个结构体指针cur指向传入的链表的表头，当cur不为空时，我们就打印一下此时该节点中的Data，并通过next找到下一个节点

• 由于我们链表的最后一个元素是NULL，因此我们最后把链表中所有节点都打印完后，在最后再补上一个NULL。

• 效果如上图

3.头插 SLTPushFront与头删 SLTPopFront

• 头插与头删顾名思义，就是在链表表头插入节点或者删除链表表头的节点

头插

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
    SLTNode* newnode = BuySListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

• 头插的逻辑图是这样的
  
  

头删

//头删
void SLTPopFront(SLTNode** pphead)
{
    //空
    assert(*pphead);
    //非空；
    SLTNode* newhead = (*pphead)->next;//保存一下下一个节点的地址
    free(*pphead);
    *pphead = newhead;
}

• 头删的逻辑图
• 首先先判断*pphead是否为空，如果为空，说明这个链表压根不存在
  
  

4.尾插SLTPushBack和尾删 SLTPopBack

• 与前面同理，尾插和尾删是作用于链表的最后的

尾插

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
    SLTNode* newnode = BuySListNode(x);
    SLTNode* tail = *pphead;
    //链表中没有节点时
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        //不为空时
        while (tail->next)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

• 我们知道链表的最后一个节点的next存放的地址为空，我们来通过逻辑图分析一下
• 首先还是特殊情况，当我们的链表中没有节点时，那我们就把头指针直接指向需要插入的节点就行。
  
  

尾删

//尾删
void SLTPopBack(SLTNode** pphead)
{
    //为空
    assert(*pphead);
    //只有一个节点
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    //不为空且有多个节点
    else
    {
        SLTNode* tail = *pphead;
        while (tail->next->next)
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;
    }
}

• 还是先来分析特殊情况，先通过assert断言来判断一下该链表是否为空，其次，如果这个链表只有一个节点时，我们指向把该节点free释放掉再置空即可，不需要其他操作。
• 一般情况的逻辑图
  
  

总结

• 由于篇幅有限，今天的内容到这里就结束了，之后我们会把剩下没讲的接口讲完然后再带大家做几道oj题让大家更加熟悉链表的使用。相信如果你能一直跟着坚持下去那么你链表这一块的初阶知识就一定没什么问题啦！切记要自己上手敲敲代码哦！
  
• 好了，如果你有任何疑问欢迎在评论区或者私信我提出，大家下次再见啦！