【数据结构】单链表详解
前言
为了解决顺序表存在的一些问题，我们引入了单链表~
欢迎关注个人主页：逸狼
创造不易，可以点点赞吗~
如有错误，欢迎指出~
目录
前言
顺序表存在一定的问题
与顺序表的对比
认识链表
链表结构
打印节点
头文件SList.h
源文件SList.c
源文件test.c
尾插和头插
源文件SList.c
运行结果编辑
头删和尾删
源文件SList.c
运行结果
查找
源文件SList.c
运行结果
在指定位置之前和之后插入数据
源文件SList.c
运行结果
删除指定位置和其之后的数据
源文件SList.c
运行结果
顺序表存在一定的问题
- 顺序表的中间/头部的插入、删除需要挪动数据
- 扩容存在性能的消耗
- 会有空间的浪费
而链表可以规避这些问题~
与顺序表的对比
认识链表
链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
- 链表由一个个节点组成
- 每个节点的组成：当前节点要保存的数据 和 保存下⼀个节点的地址（指针变量）。
- 通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。
- 可以增加或减少节点
链表结构
typedef int SLTDataTpye;//链表由节点组成
typedef struct SListNode
{SLTDataTpye data;//存储当前节点的数据SLTNode* next;//存储下一节点的地址
}SLTNode;//将该链表命名为SLTNode//typedef struct SListNode SLTNode;打印节点
头文件SList.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>typedef int SLTData;
typedef struct SListNode SLTNode;//定义节点
struct SListNode {SLTData data;struct SListNode* next;
};//打印链表
void SLTPrint(SLTNode* phead);//销毁链表
void SLTDesTroy(SLTNode** pphead)；
源文件SList.c
#include"SList.h"//打印链表
void SLTPrint(SLTNode* phead)
{//用pcur遍历链表SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}//销毁链表
void SLTDesTroy(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;//循环删除节点while (pcur){SLTNode* next = pcur->next;//创建next节点保存pcur下一个节点free(pcur);pcur = next;}*pphead = NULL;
}源文件test.c
#include"SList.h"void SListTest01()
{//对第一个节点申请了空间SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));node2->data = 2;SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));node3->data = 3;SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));node4->data = 4;//将节点连接在一起node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;//创建链表plistSLTNode* plist = node1;//plist指针保存了第一个节点的地址SLTPrint(plist);
}int main()
{SListTest01();return 0;
}尾插和头插
尾插
头插
指针关系
源文件SList.c
//申请一个新节点的方法
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));newnode->data = x;newnode->next = NULL;return newnode;
}//链表的头插和尾插
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)//链表头节点的地址和要插入的数据
{//排查空指针assert(pphead);SLTNode* newnode = SLTBuyNode(x);//链表为空，新节点作为pheadif (*pphead == NULL){*pphead = newnode;return;}//链表不为空，找尾节点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//此时ptail就是尾节点ptail->next = newnode;
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}运行结果
头删和尾删
源文件SList.c
//链表的头删和尾删
//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}//有多个节点SLTNode* ptail = *pphead;SLTNode* prev = NULL;//让ptail走到尾节点while (ptail->next){prev = ptail;ptail = ptail->next;}//销毁尾节点prev->next = NULL;free(ptail);ptail = NULL;
}//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//让第二个节点成为新的头SLTNode* next = (*pphead)->next;//把旧节点释放掉free(*pphead);*pphead = next;
}
运行结果
查找
源文件SList.c
//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(pphead);//遍历链表SLTNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}运行结果
在指定位置之前和之后插入数据
指定位置之前
指定位置之后
源文件SList.c
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//要加上链表不能为空assert(*pphead);SLTNode* newnode = SLTBuyNode(x);//pos刚好是头节点if (pos == *pphead){//执行头插操作SLTPushFront(pphead, x);return;}//pos不是头节点的情况SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//将prev newnode pos 3者连接起来prev->next = newnode;newnode->next = pos;}//在指定位置之后插入数据
void SLTInsertAfert(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}运行结果
删除指定位置和其之后的数据
删除指定位置数据
删除指定位置之后
源文件SList.c
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos刚好是头节点时，没有前驱节点，执行头删if (*pphead == pos){//头删SLTPopFront(pphead);return;}//头节点没有前驱节点，所以要排除以上情况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是最后一个节点assert(pos->next);//先pos指向pos->next->next//再将pos->next释放//其中要先保存要删除的节点SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}运行结果
