文章目录

• 一、链表概念
• 二、链表的分类
• 三、单链表的实现（无头单向不循环）
• • • 1.SLT.c
    • • • 1.1创建新的结点
        • 1.2插入n个连续的数
        • 1.3数据打印
        • 1.4单链表尾插
        • 1.5单链表尾删
        • 1.6单链表头插
        • 1.7单链表头删
        • 1.8查找数据
        • 1.9在指定位置后面插入
        • 1.10指定位置删除
        • 1.11销毁数据
    • 2.SLT.h
    • 3.test.c
• 四、顺序表和链表的优缺点

一、链表概念

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

1️⃣从上图可以看出逻辑上是连续的，而物理上就并不一定是连续的了
2️⃣现实中结点都是从堆上申请的，（有的书上结点也可能为节点意思是相同的，在这里也顺便介绍一下什么是前驱结点，后驱结点。例如：1、2、3、n、n+1中n+1是n的后驱结点，而n是n+1的前驱结点）
3️⃣因为是在堆上申请的空间，所以可能会出现二次申请空间可能，所以也就导致在物理上不是连续的。

二、链表的分类

链表一共分为三种结构，带不带头，单向双向，循不循环。
由这三种结构可以组合八种，所以链表的分类为八种。

​🐬​：在下面就不全部介绍了，拿出两个经典也是最常用的来介绍一下无头单向非循环链表 带头双向循环链表，在下面的图看上去带头双向循环链表可能看起来比较复杂，但是在我们实现的过程中会发现便不难，对比无头单向非循环，还是前者写起来比较舒服。
1️⃣ 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2️⃣ 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了

三、单链表的实现（无头单向不循环）

这里把单链表分为三个大部分分别是
1️⃣test.c：头文件用来测试单链表的功能。
2️⃣SLT.c ：主要是用来单链表功能的实现
3️⃣SLT.h：用来放一些头文件，函数声明，结构体的创建。

1.SLT.c

1.1创建新的结点

创建新的节点，使用动态开辟空间，并对结点内的值进行初始化。

SLTNode* BuySLTNode(SLTDataType x)
{//创建新结点SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL)//判断是否空间开辟成功{perror("malloc");exit(-1);}newnode->data = x;newnode->next = NULL;//进行初始化return newnode;
}

1.2插入n个连续的数

该函数的目的是插入n个连续的数，并不需要一个一个的插入，提供了便捷。在这里每插入一个数就开辟一个空间，这样并不会造成空间浪费，在这里并不能直接尾插，因为这并不是带头的链表，所以需要判断一下。

SLTNode* CreateSList(int n)//插入n个连续的数
{SLTNode* phead = NULL;SLTNode* ptail = NULL;for (int i = 0; i < n; i++){SLTNode* newnode = BuySLTNode(i);if (phead == NULL){//SLTNode* newnode = BuySLTNode(i);phead = ptail = newnode;}else{ptail->next = newnode;ptail = newnode;}}return phead;
}

说一个我自己犯得错误，在创建新的结点的时候，因为上面是在循环当中创建的，我就认为BuySLTNode(i)中主要是i相同，就认为结点也就相同了，下面来看一下我当时错误的代码。❌❌❌❌❌❌❌❌❌❌❌❌❌❌❌❌❌

SLTNode* CreateSList(int n)//插入n个连续的数
{SLTNode* phead = NULL;SLTNode* ptail = NULL;for (int i = 0; i < n; i++){if (phead == NULL){//SLTNode* newnode = BuySLTNode(i);phead = ptail = BuySLTNode(i);}else{ptail->next = BuySLTNode(i);ptail = BuySLTNode(i);}}return phead;
}

1.3数据打印

在这里尽量养成一个好习惯，不要直接使用形式参数，最好在重新创建一个变量来接收形参，尽管后面不会用到，也要尽量创建新的变量。

void SLTPrint(SLTNode* phead)
{//打印数据SLTNode* cur = phead;while (cur != NULL){printf("%d", cur->data);cur = cur->next;}printf("NULL\n");
}

1.4单链表尾插

在这里看到用的是二级指针，因为将头结点设为NULL指针了，在传参的时候（形参是实参的一份临时拷贝），所以再传一级指针的时候，改变形参的时候，并不会对头结点（实参）造成影响。所以采用二级指针的方法，或者采用返回值的方法（这里并不提倡用，太麻烦）到后来用带头的链表时这些问题就都不在了。

void SLTPushBack(SLTNode** phead, SLTDataType x)
{//单链表尾插if (*phead == NULL)//判断头结点是否为NULL{*phead = BuySLTNode(x);}else{SLTNode* ptail = *phead;while (ptail->next){ptail = ptail->next;}ptail->next = BuySLTNode(x);}
}

1.5单链表尾删

在尾删的情况下就要判断一下该链表是否为NULL，在NULL的情况下在删除也会出现错误。还要判断一下是否就只有头结点一个结点，如果是就可以直接释放头结点就可以了，因为是动态开辟的空间所以需要释放。

void SLTPopBack(SLTNode** phead)
{//单链表尾删assert(*phead);if ((*phead)->next == NULL){free(*phead);*phead = NULL;}else{SLTNode* ptail = *phead;while (ptail->next->next){ptail = ptail->next;}free(ptail->next);ptail->next = NULL;}
}

1.6单链表头插

void SLTPushFront(SLTNode** phead, SLTDataType x)
{//单链表头插SLTNode* newnode = BuySLTNode(x);if (*phead == NULL){*phead = BuySLTNode(x);}else{SLTNode* ptail = *phead;*phead = newnode;(*phead)->next = ptail;ptail = NULL;}
}

1.7单链表头删

头删和尾删的过程是差不多的，记住要判断是否为NULL,为NULL就不能再删除了。

void SLTPopFront(SLTNode** phead)
{//单链表头删assert(*phead);if ((*phead)->next == NULL){free(*phead);*phead = NULL;}else{SLTNode* ptail = (*phead)->next;*phead = ptail;ptail = NULL;}
}

1.8查找数据

查找数据，再找到就返回它当前的结点地址，如果没有找到就返回NULL
这里就不需要判断是否为NULL了,因为空也是可以查找的，同样也是没找到所以也返回空。

SLTNode* SLTFind(SLTNode* plist, SLTDataType x)
{//查找数据SLTNode* cur = plist;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

1.9在指定位置后面插入

在这里指定的位置需要断言一下，不能为NULL，而在这段代码的下面是在指定位置插入的可以对比一下差别，当在当前位置插入时，指定位置为头结点时可以直接调用头插。

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{//指定当前位置后面删除assert(pos);SLTNode* newnode = BuySLTNode(x);if (pos->next == NULL){pos->next = newnode;}else{SLTNode* ptail = pos->next;pos->next = newnode;newnode->next = ptail;newnode->data = x;}
}

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{//指定位置插入assert(pos);if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* newnode = BuySLTNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;}
}

1.10指定位置删除

下面的两段代码分别是在指定位置后面删除，和删除指定位置。这里也是需要断言一下，并且释放被删除的空间，删除指定位置如果是删除头结点一样是可以调用头删。

void SLTEraseAfter(SLTNode* pos)//指定位置后面删除
{assert(pos);if ((pos->next) != NULL){SLTNode* ptail = pos->next->next;free(pos->next);pos->next = ptail;}
}

void SLTErase(SLTNode** pphead, SLTNode* pos)
{//指定位置删除assert(pos);if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}cur->next = pos->next;}free(pos);
}

1.11销毁数据

这里是将所有的数据都进行删除，全部释放，并且置为空，这里也是需要断言一下。

void SLTDestroy(SLTNode** pphead)
{assert(*pphead);if ((*pphead)->next ==NULL){free(*pphead);*pphead = NULL;}else{SLTNode* cur = *pphead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;}
}

在最后简单的说一下为什么有的时候用二级指针，有的时候用一级指针，简单理解就是当你认为需要改变数据的内容时就用二级指针，比如添加数据和删除数据都是需要改变数据所以用二级指针，而打印和查找就只是调用数据并不修改所以用一级指针。

2.SLT.h

SLT.h中是一些头文件，结构体的生成，还有对功能函数的实现，对类型的自定义，因为在这里自定义会对后来如果改数据类型的时候有很大的方便。

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include
#include
#includetypedef int SLTDataType;
//自定义
typedef struct SListNode
{SLTDataType data;struct SListNode* next;}SLTNode;
//创建结构体
SLTNode* BuySLTNode(SLTDataType x);
//创建新的结点
SLTNode* CreateSList(int n);
//创建连续数据的链表
void SLTPrint(SLTNode* phead);
//打印数据
void SLTPushBack(SLTNode** phead, SLTDataType x);
//尾插
void SLTPopBack(SLTNode** phead);
//尾删
void SLTPushFront(SLTNode** phead, SLTDataType x);
//头插
void SLTPopFront(SLTNode** phead);
//头删SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
// 单链表查找void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 单链表在pos位置之后插入x
void SLTEraseAfter(SLTNode* pos);
// 单链表删除pos位置之后的值void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 在pos之前插入xvoid SLTErase(SLTNode** pphead, SLTNode* pos);
// 删除pos位置
void SLTDestroy(SLTNode** pphead);
//销毁数据

3.test.c

下面就是对链表功能的一些测试。

#define _CRT_SECURE_NO_WARNINGS 1
#include"SLT.h"
int main()
{SLTNode* SLT = CreateSList(5);SLTPrint(SLT);SLTPushBack(&SLT, 6);SLTPrint(SLT);SLTPopBack(&SLT);SLTPrint(SLT);SLTPushFront(&SLT,9);SLTPrint(SLT);SLTPopFront(&SLT);SLTPrint(SLT);SLTNode* SLF=SLTFind(SLT, 4);if (SLF == NULL){printf("没找到\n");}else{printf("找到了！\n");}SLTPrint(SLF);SLTInsertAfter(SLF,9);SLTPrint(SLT);SLTNode* SLC = SLTFind(SLT, 9);SLTEraseAfter(SLC);SLTPrint(SLT);SLTInsert(&SLT,SLT, 8);SLTPrint(SLT);SLTErase(&SLT,SLF);SLTPrint(SLT);SLTDestroy(&SLT);SLTPrint(SLT);return 0;
}

四、顺序表和链表的优缺点

顺序表的优点
1️⃣ 顺序表的内存空间连续,物理上一定连续。
2️⃣ 支持随机访问，可以高效的按下标进行操作，时间复杂度是O(1)。
3️⃣尾插、尾删效率较高，时间复杂度是O(1)。
顺序表的缺点
1️⃣在任意位置和头结点插入删除，效率低，要将数据向后移时间复杂度为O(N)。
2️⃣顺序表长度固定，有时需要扩容，扩容可能还会在成空间浪费。
链表的优点
1️⃣不用担心扩容问题，也不会造成空间浪费。
2️⃣链表的插入和删除操作的效率较高，可以把通过地址直接改变节点的指向。
3️⃣逻辑上连续，但物理上不一定连续。
链表的缺点
1️⃣链表不支持随机访问，查找元素效率低，需要遍历节点，时间复杂度是O(n)。