数据结构之单链表及其实现！
目录
编辑
悟已往之不谏，知来者犹可追
创作不易，宝子们！如果这篇文章对你们有帮助的话，别忘了给个免费的赞哟
1. 顺序表的问题及思考
问题：
1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考：如何解决以上问题呢？下面给出了链表的结构来看看。
2.链表的概念结构和分类
2.1 概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。
编辑
2.2 分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1. 单项或者双向
编辑
2. 带头或者不带头
编辑
3. 循环或者非循环
编辑
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
编辑
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了，后面我们代码实现了就知道了。
下面我就来实现一下无头单向非循环链表~
3. 单链表的实现
这里我就具体实现一下接口~（SList.h)
#define _CRT_SECURE_NO_WARNINGS
#pragma once//避免头文件被多次引用
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SListDataType;//便于改变数据类型
//定义一个结构体类型的节点
typedef struct SListNode
{
SListDataType data;
struct SListNode* next;//存储下一个节点的地址
}SListNode;
//1. 新节点的创建
SListNode* SListCreatNode(SListDataType x);
//2. 打印单链表
void PrintSList(SListNode* phead);
//3. 头插
void SListPushFront(SListNode** phead, SListDataType x);
//4. 头删
void SListPopFront(SListNode** phead);
//5. 尾差
void SListPushBack(SListNode** phead, SListDataType x);
//6. 尾删
void SListPopBack(SListNode** phead);
//7. 查找元素X
SListNode* SListFind(SListNode* phead, SListDataType x);
//8. 在pos位置修改
void SListModify(SListNode* pos, SListDataType x);
//9. 在任意位置之前插入
void SListInsert(SListNode** phead, SListNode* pos, SListDataType x);
//10. 在任意位置删除
void SListErase(SListNode** phead, SListNode* pos);
//11. 销毁单链表
void SListDestroy(SListNode** phead);
3.1 新节点的创建
(1)代码实现
//1. 新节点的创建
SListNode* SListCreatNode(SListDataType x)
{
SListNode* NewNode= (SListNode*)malloc(sizeof(SListNode));//开辟空间
if (NewNode == NULL)//判断空间是否开辟成功
{
perror("malloc fail");
return NULL;
}
NewNode->data = x;//赋值
NewNode->next = NULL;//置空
return NewNode;
}
3.2 打印单链表
(1)代码实现
//2. 打印单链表
void PrintSList(SListNode* phead)
{
if (phead == NULL)
{
printf("NULL");//如果链表没有元素就打印NULL
return;
}
SListNode* cur = phead;
//循环单链表打印
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
(2) 复杂度分析
• 时间复杂度：因为需要遍历整个链表，显然时间复杂度为O(N)。
• 空间复杂度：打印链表不需要格外的空间，所以空间复杂度为O(1).
3.3 头插
(1)代码实现
//3. 头插
void SListPushFront(SListNode** phead, SListDataType x)
{
assert(phead);
SListNode* newnode =SListCreatNode(x);//创建一个新节点
newnode->next =*phead;
*phead = newnode;
}
(2) 复杂度分析
• 时间复杂度：不需要额外时间的消耗，时间复杂度为O(1)。
• 空间复杂度：固定创造一个节点，空间复杂度为O(1)。
3.4 头删
(1)代码实现
//4. 头删
void SListPopFront(SListNode** phead)
{
assert(phead);
assert(*phead);//如果没有数据就不用头删，并报错
SListNode* cur = (*phead)->next;
free(*phead);
*phead = cur;
}
(2) 复杂度分析
• 时间复杂度：不需要额外时间的消耗，时间复杂度为O(1)。
• 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。
3.5 尾插
(1)代码实现
//5. 尾插
void SListPushBack(SListNode** phead, SListDataType x)
{
assert(phead);
if (*phead == NULL)
{
*phead = SListCreatNode(x);//创建新节点并插入
}
else
{
SListNode* tail = *phead;
while (tail->next != NULL)//找到尾节点
{
tail = tail->next;
}
tail->next = SListCreatNode(x);//创建新节点并插入
}
}
(2) 复杂度分析
• 时间复杂度：需要遍历整个链表，时间复杂度为O(N)。
• 空间复杂度：固定创造一个节点，空间复杂度为O(1)。
3.6 尾删
(1)代码实现
//6. 尾删
void SListPopBack(SListNode** phead)
{
assert(phead);
assert(*phead);//链表为空就不进行尾删
SListNode* tail = *phead;
if (tail->next == NULL)//如果链表就只有一个元素就进行头删
{
SListPopFront(phead);
}
else
{
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
(2) 复杂度分析
• 时间复杂度：需要遍历整个链表，时间复杂度为O(N)。
• 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。
3.7 查找元素X
(1)代码实现
//7. 查找元素X
SListNode* SListFind(SListNode* phead, SListDataType x)
{
assert(phead);
while (phead->next!=NULL)//注意最后一个节点是没有查找的
{
if (phead->data == x)
return phead;
phead = phead->next;
}
if (phead->data == x)
return phead;//最后一个节点没有查找
else
return NULL;//没找到
}
(2) 时间复杂度
• 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
• 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。
3.8 在pos位置修改
(1)代码实现
//8. 在pos位置修改
void SListModify( SListNode* pos, SListDataType x)
{
assert(pos);
pos->data = x;
}
(2) 时间复杂度
• 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
• 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。
3.9 在任意位置之前插入
(1)代码实现
//9. 在任意位置之前插入
void SListInsert(SListNode** phead, SListNode* pos, SListDataType x)
{
assert(phead);
assert(*phead);
if (pos==*phead)//如果pos位置刚好是第一个节点就进行头插
{
SListPushFront( phead,x);
}
else
{
SListNode* newnode = SListCreatNode(x);
SListNode* cur = *phead;
while (cur->next != pos)//找到pos前一个节点
{
cur = cur->next;
}
cur->next = newnode;
newnode->next = pos;
}
}
(2) 复杂度分析
• 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
• 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。
3.10 在任意位置删除
(1)代码实现
//10. 在任意位置删除
void SListErase(SListNode** phead, SListNode* pos)
{
assert(phead && *phead && pos);
if (pos==*phead)//如果pos位置就是第一个节点就进行头删
{
SListPopFront(phead);
}
else
{
SListNode* cur = *phead;
while (cur->next != pos)//找到pos前一个节点
{
cur = cur->next;
}
cur->next = pos->next;
free(pos);
}
}
(2) 复杂度分析
• 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
• 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。
3.11 单链表的销毁
(1)代码实现
//11. 销毁单链表
void SListDestroy(SListNode** phead)
{
assert(*phead && phead);
SListNode* cur = *phead;
while (cur!= NULL)
{
SListNode* tmp = cur->next;
free(cur);
cur = tmp;
}
*phead = NULL;
}
(2) 复杂度分析
• 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
• 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。
4. 完整代码
SList.c
#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"
//1. 新节点的创建
SListNode* SListCreatNode(SListDataType x)
{
SListNode* NewNode= (SListNode*)malloc(sizeof(SListNode));//开辟空间
if (NewNode == NULL)//判断空间是否开辟成功
{
perror("malloc fail");
return NULL;
}
NewNode->data = x;//赋值
NewNode->next = NULL;//置空
return NewNode;
}
//2. 打印单链表
void PrintSList(SListNode* phead)
{
if (phead == NULL)
{
printf("NULL");//如果链表没有元素就打印NULL
return;
}
SListNode* cur = phead;
//循环单链表打印
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
//3. 头插
void SListPushFront(SListNode** phead, SListDataType x)
{
assert(phead);
SListNode* newnode =SListCreatNode(x);//创建一个新节点
newnode->next =*phead;
*phead = newnode;
}
//4. 头删
void SListPopFront(SListNode** phead)
{
assert(phead);
assert(*phead);//如果没有数据就不用头删，并报错
SListNode* cur = (*phead)->next;
free(*phead);
*phead = cur;
}
//5. 尾插
void SListPushBack(SListNode** phead, SListDataType x)
{
assert(phead);
if (*phead == NULL)
{
*phead = SListCreatNode(x);//创建新节点并插入
}
else
{
SListNode* tail = *phead;
while (tail->next != NULL)//找到尾节点
{
tail = tail->next;
}
tail->next = SListCreatNode(x);//创建新节点并插入
}
}
//6. 尾删
void SListPopBack(SListNode** phead)
{
assert(phead);
assert(*phead);//链表为空就不进行尾删
SListNode* tail = *phead;
if (tail->next == NULL)//如果链表就只有一个元素就进行头删
{
SListPopFront(phead);
}
else
{
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
//7. 查找元素X
SListNode* SListFind(SListNode* phead, SListDataType x)
{
assert(phead);
while (phead->next!=NULL)//注意最后一个节点是没有查找的
{
if (phead->data == x)
return phead;
phead = phead->next;
}
if (phead->data == x)
return phead;//最后一个节点没有查找
else
return NULL;//没找到
}
//8. 在pos位置修改
void SListModify( SListNode* pos, SListDataType x)
{
assert(pos);
pos->data = x;
}
//9. 在任意位置之前插入
void SListInsert(SListNode** phead, SListNode* pos, SListDataType x)
{
assert(phead);
assert(*phead);
if (pos==*phead)//如果pos位置刚好是第一个节点就进行头插
{
SListPushFront( phead,x);
}
else
{
SListNode* newnode = SListCreatNode(x);
SListNode* cur = *phead;
while (cur->next != pos)//找到pos前一个节点
{
cur = cur->next;
}
cur->next = newnode;
newnode->next = pos;
}
}
//10. 在任意位置删除
void SListErase(SListNode** phead, SListNode* pos)
{
assert(phead && *phead && pos);
if (pos==*phead)//如果pos位置就是第一个节点就进行头删
{
SListPopFront(phead);
}
else
{
SListNode* cur = *phead;
while (cur->next != pos)//找到pos前一个节点
{
cur = cur->next;
}
cur->next = pos->next;
free(pos);
}
}
//11. 销毁单链表
void SListDestroy(SListNode** phead)
{
assert(*phead && phead);
SListNode* cur = *phead;
while (cur!= NULL)
{
SListNode* tmp = cur->next;
free(cur);
cur = tmp;
}
*phead = NULL;
}
5. 完结散花
好了，这期的分享到这里就结束了~
如果这篇博客对你有帮助的话，可以用你们的小手指点一个免费的赞并收藏起来哟~
如果期待博主下期内容的话，可以点点关注，避免找不到我了呢~
我们下期不见不散~~
编辑
编辑
辑
- 点赞
- 收藏
- 关注作者
评论（0）