1. 链表的引入
❤️ 由于顺序表存在以下缺陷：
- 中间/头部的插入删除，时间复杂度为O(N)
- 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
为了解决以上问题，使得头部的插入删除的效率更高、空间不被浪费，我们引入了链表这一数据结构。
2. 链表的概念及结构
💛 概念：
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
现实的数据结构中：这些箭头实际上是不存在的为了让我们更容易理解链表，在这里形象的引入了结点和结点之间用箭头所连接。
💕 注意：
- 从上图可看出，链式结构在逻辑上是连续的，但在物理上不一定连续。
- 现实中的结点一般都是从堆上申请出来的。
- 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。
🧡 链表的分类：
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1. 单向或者双向：
2. 带头或者不带头：
3. 循环或者非循环：
虽然链表有这么多种结构，但我们实际中最常用的还是两种结构：
- 无头单向非循环链表：
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 带头双向循环链表：
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
3. 链表的实现
这里我们是以无头单向非循环链表为例，来实现并测试其各个接口函数，这里我们还是分为三个文件来实现这个链表。
SList.h : 头文件的包含、各个接口函数的声明和结构体类型的定义。
SList.c : 所有接口函数的实现。
Test.c : 测试各个接口函数的功能。
SList.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode {
SLTDataType data;//数据域
struct SListNode* next;//指针域
}SLTNode;
//开辟一个新的节点
SLTNode* BuySLTNode(SLTDataType x);
//打印链表
void SLTPrint(SLTNode* phead);
//链表尾插
void SLTPushBack(SLTNode** pphead,SLTDataType x);
//链表尾删
void SLTPopBack(SLTNode** pphead);
//链表头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//链表头删
void SLTPopFront(SLTNode** pphead);
//查找并返回指定结点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在pos节点之后插入数据
void STLInsertAfter(SLTNode* pos, SLTDataType x);
//在pos节点之前插入数据
void STLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点之后的结点
void STLEraseAfter(SLTNode* pos);
//删除pos节点
void STLEarse(SLTNode** pphead, SLTNode* pos);
//销毁单链表
void SLTDestroy(SLTNode** pphead);
SList.c
❤️ 开辟一个新节点
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (!newnode) {
perror("malloc::");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
🧡 打印链表
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
💝 销毁单链表
void SLTDestroy(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
SLTNode* nextnode = *pphead;
while (cur)
{
nextnode = cur->next;
free(cur);
cur = nextnode;
}
*pphead = NULL;//头节点一定要置为空，防止对已销毁的链表进行非法操作
}
💘 链表的尾插尾删
//链表尾插
void SLTPushBack(SLTNode** pphead,SLTDataType x)
{
SLTNode* cur = NULL;
SLTNode* prev = NULL;
if (*pphead == NULL)
{
*pphead = BuySLTNode(x);
}
else
{
cur = *pphead;
while (cur->next)
{
cur = cur->next;
}
cur->next = BuySLTNode(x);
}
}
//链表尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
SLTNode* prev = NULL;
if ((*pphead)->next==NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
while (cur->next)
{
prev = cur;
cur = cur->next;
}
free(cur);
prev->next = NULL;
}
}
💖 链表的头插头删
//链表头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* cur = BuySLTNode(x);
if (!*pphead)
{
*pphead = cur;
}
else
{
cur->next = *pphead;
*pphead = cur;
}
}
//链表头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
*pphead = cur->next;
free(cur);
}
💗 查找并返回指定节点
//查找并返回指定节点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
💓 在pos节点之后插入节点
//在pos节点之后插入节点
void STLInsertAfter(SLTNode* pos, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
💞 在pos节点之前插入节点
//在pos节点之前插入节点
void STLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pos);
if (pos == *pphead)
{
SLTPushFront(pphead, x);
return;
}
//找到指定节点的前一个结点
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//插入
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos;
prev->next = newnode;
}
💕 删除pos节点之后的一个节点
//删除pos节点之后的一个节点
void STLEraseAfter(SLTNode* pos)
{
if (pos->next == NULL)
return;
SLTNode* tmp = pos->next;
pos->next = tmp->next;
free(tmp);
}
❣️ 删除pos节点
//删除pos节点
void STLEarse(SLTNode** pphead, SLTNode* pos)
{
assert(pos);
assert(*pphead);
if (pos == *pphead)
{
SLTPopFront(pphead);
return;
}
SLTNode* prev = *pphead;
while (prev->next!=pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SLIst.h"
void SLTNodeTest1()//链表的尾插尾删
{
SLTNode* sl = NULL;
SLTPushBack(&sl, 1);
SLTPushBack(&sl, 2);
SLTPushBack(&sl, 3);
SLTPushBack(&sl, 4);
SLTPrint(sl);
SLTPopBack(&sl);
SLTPopBack(&sl);
SLTPopBack(&sl);
SLTPopBack(&sl);
SLTPopBack(&sl);
SLTPrint(sl);
}
void SLTNodeTest2()//链表的头插头删
{
SLTNode* sl = NULL;
SLTPushFront(&sl, 1);
SLTPushFront(&sl, 2);
SLTPushFront(&sl, 3);
SLTPushFront(&sl, 4);
SLTPushFront(&sl, 5);
SLTPrint(sl);
SLTPopFront(&sl);
SLTPopFront(&sl);
SLTPopFront(&sl);
SLTPopFront(&sl);
SLTPopFront(&sl);
SLTPrint(sl);
}
void SLTNodeTest3()//链表的指定结点之后、指定结点之前插入数据
{
SLTNode* sl = NULL;
SLTPushBack(&sl, 1);
SLTPushBack(&sl, 2);
SLTPushBack(&sl, 3);
SLTPushBack(&sl, 4);
SLTPushBack(&sl, 5);
SLTNode* p = SLTFind(sl , 2);
STLInsertAfter(p, 200);//指定节点之后插入节点
SLTPrint(sl);
p = SLTFind(sl, 5);
STLInsert(&sl, p, 500);//指定节点之前插入节点
SLTPrint(sl);
p = SLTFind(sl, 1);
STLInsert(&sl, p, 100);
SLTPrint(sl);
}
void SLTNodeTest4()//删除指定结点之前的节点或者删除此结点
{
SLTNode* sl = NULL;
SLTPushBack(&sl, 1);
SLTPushBack(&sl, 2);
SLTPushBack(&sl, 3);
SLTPushBack(&sl, 4);
SLTPushBack(&sl, 5);
SLTPrint(sl);
SLTNode* p = SLTFind(sl, 2);
STLEraseAfter(p);//删除指定结点之前结点
SLTPrint(sl);
p = SLTFind(sl, 4);
STLEraseAfter(p);
SLTPrint(sl);
p = SLTFind(sl, 4);
STLEarse(&sl, p);//删除指定节点
SLTPrint(sl);
p = SLTFind(sl, 1);
STLEarse(&sl, p);//删除指定节点
SLTPrint(sl);
}
void SLTNodeTest5()//单链表的销毁
{
SLTNode* sl = NULL;
SLTPushBack(&sl, 1);
SLTPushBack(&sl, 2);
SLTPushBack(&sl, 3);
SLTPushBack(&sl, 4);
SLTPushBack(&sl, 5);
SLTPrint(sl);
SLTDestroy(&sl);
SLTPrint(sl);
}
int main()
{
SLTNodeTest5();
return 0;
}
4. 总结
本篇博客主要介绍了链表这种数据结构，并进行了单链表的增删查改的实现，让我们对链表这一数据结构有了一个初步的认识，后面还会介绍其他链表的实现
