目录
前言
一、什么是链表
二、链表的分类
三、单链表
四、单链表的实现
五、SList.c文件完整代码
六、使用演示
总结
前言
本文讲述了什么是链表,以及实现了完整的单链表。
❤️感谢支持,点赞关注不迷路❤️
一、什么是链表
1.概念
概念:链表是⼀种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
简单来说,链表属于线性表的一种,在逻辑结构上是连续的,物理结构上不一定是连续的,通过指针连接。
2.节点
与顺序表不同的是,链表里的每个节点都是独立申请下来的空间,我们称之为“结点/结点”
结点的组成主要有两个部分:当前结点要保存的数据和保存下⼀个结点的地址(指针变量)。也可以说成数据域和指针域两部分
特点:链表中每个结点都是独立申请的(即需要插入数据时才去申请一块结点的空间),我们需要通过指针变量来保存下一个结点位置,才能从当前结点找到下⼀个结点。
3.链表的性质
- 链式结构在逻辑上是连续的,在物理结构上不⼀定连续
- 结点一般是从堆上申请的
- 从堆上申请来的空间,是按照⼀定策略分配出来的,每次申请的空间可能连续,可能不连续
4.与顺序表的对比
- 顺序表的 中间/头部 插入删除数据的时间复杂度为O(n),而链表相同功能时间复杂度为O(1)
- 顺序表增容需要申请请新空间,拷贝数据,释放旧空间。会有不小的消耗。链表每次申请一个节点,不存在拷贝,释放旧空间。
- 顺序表增容一般是呈2倍的增长,势必会有⼀定的空间浪费。例如当前容量为100,满了以后增容到200, 我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。链表不存在空间浪费
以上是链表相对与顺序表的优点,但不代表顺序表一定不如链表,顺序表在有些场景下效率还是非常高,因此选择使用什么数据结构是看场景的要求
二、链表的分类
链表的结构非常多样,有带头不带头,单向或者双向,循环不循环,这三种属性情况组合起来就有8种(2x2x2)链表结构:
虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构:单链表和双向带头循环链表:
- 无头单向非循环链表(单链表):结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现该结构会带来很多优势,后面我们代码实现了就知道了。
本文主要讲述单链表
三、单链表
单链表的结构如下图:
单链表的结构声明:
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;//节点数据
struct SListNode* next;//指向下一节点的指针变量
}SLTNode;
以下单链表同样由3个文件组成:
- SList.h:单链表的结构声明,各种函数声明
- SList.c:用于函数的具体实现
- test.c:用于测试单链表(自行测试)
四、单链表的实现
1.SList.h文件
以下是该文件中的代码:
#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);//尾插
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);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除指定位置pos的数据
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos之后的数据
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SListDestroy(SLTNode** pphead);
2.SList.c文件
1.SLTPrint函数
//打印
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;//循环打印while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
解析:该函数用于打印链表数据,使用一个pcur指针,只要不为空指针,就循环遍历下一个节点
2.SLTBuyNode函数
//申请节点
SLTNode* SLTBuyNode(SLTDataType x)
{//申请一个节点SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));if (node == NULL){perror("malloc fail!");exit(1);}//赋值node->data = x;node->next = NULL;return node;
}
解析:
- 该函数用于申请新节点,一个参数,其为新节点存储的数据
- 使用malloc函数申请,申请成功后将其数据域赋值为参数值,指针域赋值为空指针NULL
- 因为该函数主要为其他功能函数服务,因此只需写在 SList.c 文件中即可,无需在头文件SList.h 中声明
3.SLTPushBack函数
//尾插
//因为要修改plist本身,因此需要二级指针来接收
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{//断言pphead不能为空指针assert(pphead);//申请新节点SLTNode* newnode = SLTBuyNode(x);//如果pphead指向的第一个节点就是空指针if (*pphead == NULL){*pphead = newnode;}else{//找尾结点SLTNode* pcur = *pphead;while (pcur->next){pcur = pcur->next;}pcur->next = newnode;}
}
解析:
- 该函数功能为:在链表尾部插入一个数据。因此需要链表的头部指针和需要插入的数据x
- 为什么头节点参数是二级指针?答:因为需要修改原指针变量本身,我们知道函数传参分为传值传参和传址传参(&),想要修改原变量内容就需要传址传参,而这里原变量就是一个指向链表头节点的指针变量,因此原变量通过&传参,就需要二级指针来接收一级指针变量的地址。所以这里就是用二级指针,下面其他的函数同理。
- 申请完新节点,插入到链表尾部时要分2种情况,1链表为空,2链表不为空。
- 链表为空则直接将新节点插入链表即可,也就是将指向头结点的指针指向新节点。链表不为空就需要寻找尾结点,尾节点的特点就是next指针指向空。循环之后将尾节点的next指针修改为新节点即可。
4.SLTPushFront函数
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);//直接申请节点,然后修改新节点指向即可SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}
解析:
- 功能:在链表头部插入一个新节点。参数同样是一个二级指针和新节点的数据
- 头插比较简单,只需将新申请的节点的 next 指针指向链表头结点,然后让指向链表头结点的指针指向新节点即可。
5.SLTPopBack函数
//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);//只有一个节点的情况if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//两个及以上节点的情况//申请两个节点用于指向尾节点和倒数第二个节点SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}//销毁尾结点,然后让倒数第二个节点next指向空free(ptail);ptail = NULL;prev->next = NULL;}
}
解析:
- 功能:删除链表的最后一个节点,参数为一个二级指针
- 首先断言,不能传空指针并且链表不能为空
- 尾删也要分两种情况,因为如果只要一个节点,那么就不需要找倒数第二个节点。所以分为链表只有一个节点的情况和有多个节点的情况
- 只有一个节点,那么我们直接 free 掉该节点,然后让指向头结点的指针置空。多个节点,那么我们就需要找到最后一个节点 ptail 以及倒数第二个节点 prev,使用while循环即可,只要ptail 的下一个节点为空就跳出循环,此时 prev 为倒数第二个节点,然后释放掉最后一个节点,修改倒数第二个节点的next指针即可。
6.SLTPopFront函数
//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}
解析:
- 功能:删除链表的头部节点
- 因为参数 *pphead 就是指向链表的头结点,因此删除简单,先创建一个next指针保存头结点的下一个节点,然后释放掉头节点,更改 *pphead 的指向即可
7.SLTFind函数
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur = phead;while (pcur){//找到了if (pcur->data == x){return pcur;}pcur = pcur->next;}//没找到return NULL;
}
解析:
- 功能:查找数据为 x 的节点,返回该节点的地址。
- 因为查找操作不会影响头指针 phead,因此参数为一级指针即可
- 查找很简单,循环遍历链表,让 pcur 一直往后走,直到找到存储 x 的节点,返回该节点,没找到就返回空指针
8.SLTInsert函数
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//如果指定位置是头结点if (*pphead == pos){//头插SLTPushFront(pphead, x);}else{//新节点SLTNode* newnode = SLTBuyNode(x);//prev用于找到pos前一个节点SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;}
}
解析:
- 功能:在指定位置之前插入数据,参数为头指针地址、指定位置(用SLTFind函数确定)、需插入的数据x。
- 首先断言,头指针和pos指针都不能为空,也就是链表不能为空
- 然后,也分两种情况,因为如果指定位置刚好是头结点,那么只需要使用头插函数即可。如果指定位置不是头结点,我们就需要找到 pos 指向的结点的前一个节点。定义一个指针变量 prev,让它从头往后找,只要它的 next 指针不是 pos,那么就继续往下个节点走,直到找到pos的前一个节点。
- 找到之后,让 prev 的 next 指针指向新节点,再让新节点的 next 指针指向pos就完成了在指定位置前插入数据。
7.SLTInsertAfter函数
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);//先让newnode的next指向下一个节点newnode->next = pos->next;//再修改pos的next指针pos->next = newnode;
}
解析:
- 功能:在指定位置之后插入数据。
- 因为受影响的节点只有pos指向的节点,所以只需要传pos指针和需要增加的数据 x 即可。
- pos指针使用SLTFind函数指定即可
- 实现简单,注意顺序即可,将新节点的next指针指向pos节点的下一个节点,然后让pos指针的next指针指向新节点即可。
8.SLTErase函数
//删除指定位置pos的数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);//如果pos位置是第一个位置if (*pphead == pos){//头删SLTPopFront(pphead);}else{//找到pos前一个节点SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//释放prev->next = pos->next;free(pos);pos = NULL;}
}
解析:
- 功能:删除指定位置的节点。
- 参数需用到头节点和pos指向节点
- 也要分两种情况,因为如果需删除节点刚好是头结点,直接头删即可,如果不是头结点,则需要找到指定位置的前一个节点,老套路,找到之后,先修改 prev 的next指针,然后释放pos指向的节点。
9.SLTEraseAfter函数
//删除pos之后的数据
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;//让pos指向它之后的之后的数据pos->next = pos->next->next;free(del);del = NULL;
}
解析:
- 功能:删除pos位置后一个节点
- 只需要pos指针即可
- 实现简单,先保存需删除的节点地址,然后改变pos的next指针指向,最后释放掉 del 即可。
10.SListDestroy函数
//销毁链表
void SListDestroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;//循环销毁链表while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}//记得将头指针指置空*pphead = NULL;
}
解析:
- 功能:销毁整个链表
- 断言确保链表不为空
- 创建pcur循环遍历链表,只要pcur不为空,释放该空间。
- 最后记得将头指针置空
五、SList.c文件完整代码
#include "SList.h"//打印
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;//循环打印while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}//申请节点
SLTNode* SLTBuyNode(SLTDataType x)
{//申请一个节点SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));if (node == NULL){perror("malloc fail!");exit(1);}//赋值node->data = x;node->next = NULL;return node;
}//尾插
//因为要修改plist本身,因此需要二级指针来接收
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{//断言pphead不能为空指针assert(pphead);//申请新节点SLTNode* newnode = SLTBuyNode(x);//如果pphead指向的第一个节点就是空指针if (*pphead == NULL){*pphead = newnode;}else{//找尾结点SLTNode* pcur = *pphead;while (pcur->next){pcur = pcur->next;}pcur->next = newnode;}
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);//直接申请节点,然后修改新节点指向即可SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);//只有一个节点的情况if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//两个及以上节点的情况//申请两个节点用于指向尾节点和倒数第二个节点SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}//销毁尾结点,然后让倒数第二个节点next指向空free(ptail);ptail = NULL;prev->next = NULL;}
}//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur = phead;while (pcur){//找到了if (pcur->data == x){return pcur;}pcur = pcur->next;}//没找到return NULL;
}//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//如果指定位置是头结点if (*pphead == pos){//头插SLTPushFront(pphead, x);}else{//新节点SLTNode* newnode = SLTBuyNode(x);//prev用于找到pos前一个节点SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;}
}//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);//先让newnode的next指向下一个节点newnode->next = pos->next;//再修改pos的next指针pos->next = newnode;
}//删除指定位置pos的数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);//如果pos位置是第一个位置if (*pphead == pos){//头删SLTPopFront(pphead);}else{//找到pos前一个节点SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//释放prev->next = pos->next;free(pos);pos = NULL;}
}//删除pos之后的数据
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;//让pos指向它之后的之后的数据pos->next = pos->next->next;free(del);del = NULL;
}//销毁链表
void SListDestroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;//循环销毁链表while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}//记得将头指针指置空*pphead = NULL;
}
六、使用演示
不完全演示:
#include "SList.h"void SListTest1()
{//指针要初始化为空SLTNode* plist = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);printf("尾插:");SLTPrint(plist);//头插SLTPushFront(&plist, 11);SLTPushFront(&plist, 12);SLTPushFront(&plist, 13);SLTPushFront(&plist, 14);SLTPushFront(&plist, 15);printf("头插:");SLTPrint(plist);//尾删SLTPopBack(&plist);printf("尾删:");SLTPrint(plist);//头删SLTPopFront(&plist);printf("头删:");SLTPrint(plist);//指定位置之前插入数据SLTInsert(&plist, SLTFind(plist, 2), 66);printf("在2的前面插入66:");SLTPrint(plist);//删除指定位置数据SLTErase(&plist, SLTFind(plist, 66));printf("删除66:");SLTPrint(plist);//销毁链表SListDestroy(&plist);printf("销毁:");SLTPrint(plist);
}int main()
{SListTest1();return 0;
}
运行结果:
总结
以上就是本文的全部内容,感谢支持。