数据结构-链表-单链表（3）

目录

1. 顺序表的缺陷

2. 单链表

2.1 单链表的基本结构与接口函数

2.2 重要接口

创建新节点的函数：

2.2.1 尾插

2.2.2 头插

2.2.3 尾删

2.2.4 头删

2.2.5 查找

2.2.6 插入

2.2.7 删除

2.2.8 从pos后面插入

2.2.9 从pos后面删除

3. 链表的缺陷与优势：

4. 链表与顺序表比较

写在最后：

---

1. 顺序表的缺陷

为什么会有链表？

我们都有顺序表来存储数据了，

因为顺序表是有缺陷的：

1. 中间头部插入删除数据，需要挪动数据，效率低下。

2. 空间不够需要扩容，扩容会有一定的消耗，也可能会造成空间的浪费。

这时候，我们就要用到链表。

2. 单链表

链表是一种物理存储结构上非连续、非顺序的存储结构，

数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

如下图： 

2.1 单链表的基本结构与接口函数

基本结构：

#pragma once
 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef int SLDataType;
 
typedef struct SListNode
{
	SLDataType data;
	struct SListNode* next;
}SLNode;
 
//打印链表
void SLPrint(SLNode* phead);
 
//尾插
void SLPushBack(SLNode** pphead, SLDataType x);
 
//头插
void SLPushFront(SLNode** pphead, SLDataType x);
 
//尾删
void SLPopBack(SLNode** ppheadx);
 
//头删
void SLPopFront(SLNode** pphead);
 
//查找
SLNode* SLFind(SLNode* phead, SLDataType x);
 
//插入
void SLInsert(SLNode** phead, SLNode* pos, SLDataType x);
 
//删除
void SLErase(SLNode** phead, SLNode* pos);
 
//从pos后面插入
void SLInsertAfter(SLNode* pos, SLDataType x);
 
//从pos后面删除
void SLEraseAfter(SLNode* pos);

2.2 重要接口

创建新节点的函数：

//建立一个新节点（重复操作写成函数复用）
SLNode* BuyNewNode(SLDataType x)
{
	//malloc一个链表节点大小的空间
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
 
	//检查
	if (newnode == NULL)
	{
		perror("malloc::fail");
		return;
	}
 
	//赋值
	newnode->data = x;
	newnode->next = NULL;
 
	return newnode;
}

2.2.1 尾插

//尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{
	//检查二级指针pphead地址是否为空	
	//方便检查是否传空指针了
	assert(pphead);
 
	//创建节点
	SLNode* newnode = BuyNewNode(x);
 
	//如果链表为空
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else//如果链表不为空
	{
		//找尾
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
 
		//尾插
		tail->next = newnode;
	}
}

2.2.2 头插

//头插
void SLPushFront(SLNode** pphead, SLDataType x)
{
	//检查二级指针pphead地址是否为空	
	//方便检查是否传空指针了
	assert(pphead);
 
	//创建节点
	SLNode* newnode = BuyNewNode(x);
 
	//头插
	newnode->next = *pphead;
	*pphead = newnode;
}

2.2.3 尾删

//尾删
void SLPopBack(SLNode** pphead)
{
	//检查二级指针pphead地址是否为空	
	//方便检查是否传空指针了
	assert(pphead);
	//检查链表是否为空
	assert(*pphead);
	
	//头删的情况（链表只有一个数据）
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找尾
		SLNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
 
		//尾删
		free(tail->next);
		tail->next = NULL;
	}
}

2.2.4 头删

//头删
void SLPopFront(SLNode** pphead)
{
	//检查二级指针pphead地址是否为空	
	//方便检查是否传空指针了
	assert(pphead);
	//检查链表是否为空
	assert(*pphead);
 
	//头删
	SLNode* cur = (*pphead)->next;
	free(*pphead);
	*pphead = NULL;
	*pphead = cur;
}

2.2.5 查找

//查找
SLNode* SLFind(SLNode* phead, SLDataType x)
{
	//创建指针遍历链表
	SLNode* cur = phead;
 
	//查找
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
 
	return NULL;
}

2.2.6 插入

//插入
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{
	//检查查找的地址是否为空
	assert(pos);
 
	//pos的位置
	if (pos == *pphead)
	{
		SLPushFront(pphead, x);
	}
	else//在链表中间
	{
		SLNode* prev = *pphead;
 
		//查找pos对应位置
		while (prev->next != pos)
		{
			prev = prev->next;
		}
 
		//插入
		SLNode* newnode = BuyNewNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

2.2.7 删除

//删除
void SLErase(SLNode** pphead, SLNode* pos)
{
	//检查二级指针pphead地址是否为空	
	//方便检查是否传空指针了
	assert(pphead);
 
	//检查查找的地址是否为空
	assert(pos);
 
	//检查链表是否为空（这里其实不断言也可以）
	assert(*pphead);
 
	//头删的情况
	if (*pphead == pos)
	{
		SLPopFront(pphead);
	}
	else
	{
		//查找
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
 
		//删除
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

2.2.8 从pos后面插入

//从pos后面插入
void SLInsertAfter(SLNode* pos, SLDataType x)
{
	//检查查找的地址是否为空
	assert(pos);
 
	//创建节点
	SLNode* newnode = BuyNewNode(x);
 
	//再pos后面插入
	newnode->next = pos->next;
	pos->next = newnode;
}

2.2.9 从pos后面删除

//从pos后面删除
void SLEraseAfter(SLNode* pos)
{
	//检查查找的地址和要删除的地址是否为空
	assert(pos);
	assert(pos->next);
 
	//在pos后面删除，prev记住要删除的节点，然后free
	SLNode* prev = pos->next;
	pos->next = prev->next;
	free(pos->next);
	prev = NULL;
}

这就是单链表的基本框架和接口了，

如果感兴趣，你也可以使用接口函数玩一玩。

3. 链表的缺陷与优势：

但是链表是有缺陷的，

我们可以看到，

1. 链表想要访问一个节点，就得遍历链表，

2. 链表的尾删也需要遍历链表，

3. 而链表的优势是头删很方便是O(1)。

4. 链表与顺序表比较

我们就能跟顺序表比较一下，

1. 顺序表头插需要挪动数据是O(N)，

2. 但是顺序表能随机访问。

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。