九国服智多星带你手撕单链表（C语言实现）_c语言手撕链表

前言：

在上一篇博客里，我们学习了顺序表这样的数据结构，我们发现顺序表虽然可以支持随机访问数据，但是在尾部之外的位置插入和删除数据需要挪动数据，效率很低。并且在顺序表扩容的时候难免会带来一些性能的消耗。为了解决顺序表的种种缺陷，链表这种数据结构就应运而生了！

目录

一.什么是链表

二.链表的结构

三.单链表的常见接口实现

---

一.什么是链表

链表是一种物理存储结构上非连续、非顺序的存储结构，而数据元素的逻辑顺序是通过链表中的指针实现的！如果用生活中的例子来举例的话，单链表的结构就和下面这种火车的结构是类似的

 我们可以形象的用一张图片来描述一个链表的结构：

 注意：在实际的物理结构中，并没有这样的箭头，能够找到下一个节点的原因是因为前一个节点存储了下一个节点的地址，从实际效果来看就好像有一个箭头指向了这个节点一样。

从这个案例我们就可以看出：

1.链式结构在逻辑上是连续的，在物理结构上并不一定是连续的。

2.链表的节点是通过动态内存函数malloc申请出来的

3.从堆上分配出来的空间，有自己的分配策略，可能在物理上连续，也可能不连续！

二.链表的结构

实际中，链表的类型有很多种，下面的情况组合起来就有8种情况：

1.单向或双向：

 2.带头节点和不带头节点：

 3.循环或者非循环：

 这几种情况组合起来就有8种链表的结构，但是在实际工作中，最常用的链表的结构只有两种：

一：不带头单项不循环链表：

  无头单向不循环链表：结构简单，一般不会用来单独存储数据，更多的时候是作为高阶数据结构的子结构，比如哈希桶、以及图的邻接表等等，另外在笔试和OJ中也更多以这种结构为主。

 二：带头双向循环链表

带头双向循环链表：结构复杂，一般单独存储数据，实际中使用的数据结构也都是这种结构为主，虽然结构复杂，但在使用代码实现的时候，这个结构会有很大的优势，C++STL中的list也是基于这种结构实现的。

三.单链表的增删查改

和顺序表一样，SList.h--------->存放函数的声明和结构体的定义

SList.c----->实现各个函数接口 

Test.c---->测试函数功能逻辑：

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;
 
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestory(SListNode* plist);

我们按顺序进行对函数的说明：因为我们需要进行插入节点的动作，所以申请节点这件事情我们需要重复完成，因此我们把申请节点实现成一个接口以便于提高复用性：

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode=(SListNode*)malloc(sizeof(SListNode));
	if (NULL == newnode)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	return newnode;
}

我们同样写一个Print函数来打印链表的元素：

// 单链表打印
void SListPrint(SListNode* plist)
{    
	SListNode* cur = plist;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

接下来我们创建一个链表名为plist,开始的时候plist是NULL，接下来我们要尾插一些节点到这个链表并遍历打印

尾插的核心思想：使用一个尾指针tail记录尾节点，接下来将尾节点的下一个连接到新节点上，完成尾插，具体图解如下：

 开始的时候，链表为空，这时候直接把新节点的值赋给tail和newnode即可

 当tail不为空的时候，就把tail的下一个链接到新节点上：

 那么通过图片我们就可以写出如下代码：

//这里形参是用phead，和plist和一样
void SListNodePushBack(SListNode* phead, SLTDateType x)
{
	SListNode* tail = phead;
	SListNode* newnode = BuySListNode(x);
	if (NULL == phead)
	{
		phead = tail = newnode;
	}
	else
	{
		tail->next = newnode;
	}
 }

接下来我们测试一下我们的代码逻辑：

void TestSList()
{
	SListNode* plist=NULL;
    SListPushBack(plist,1);
    SListPushBack(plist, 2);
    SListPrint(plist);
}
int main()
{
	TestSList();
	return 0;
}

程序运行结果如下：

 奇怪，我们明明插入了两个节点，为什么打印出来链表是空呢？当你不知道为什么程序出问题的时候，这时候调试是帮助你分析这个程序的最好办法。

调用完第二次尾插接口以后，调试信息反馈如下：

 我们发现，在调用两次尾插以后，plist并没有发生实际的改变！因为我们传递的是plist的拷贝，对拷贝的改变永远不会影响实际的plist，画个图帮助理解：

 所以我们在对phead的修改并不会影响plist，而我们第一次尾插会修改plist，所以为了修改plist，我们需要传plist的地址，所以改造代码如下：

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newnode = BuySListNode(x);
	//空链表的时候要单独处理
	if (NULL == *pplist)
	{
		*pplist = newnode;
	}
	else
	{
		SListNode* tail = *pplist;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

接下来我们测试一下改造代码是否能够达到预期效果：

 我们看到，这份改造的代码确实达到了尾插的效果！

2.单链表头插：

相比于尾插需要找尾节点，头插相对于来说比较简单，我们也可以通过画图的方式帮助理解：

 实现代码如下：

 
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newnode = BuySListNode(x);
	//空链表要单独处理
	if (NULL == *pplist)
	{
 
		*pplist = newnode;
	}
	else
	{
		newnode->next = *pplist;
		*pplist = newnode;
	}
}

运行测试结果如下：

 实现了头插和尾插，接下来我们接着实现尾删和头删。我们先来实现较为简单的头删。

头删就是从头部删除数据，但在删除节点之前我们要先保存下一个节点，否则我们一旦删除以后，如果没有保存下一节点的地址，整个链表就找不到了！，对于头删保存下一个节点，释放当前节点，把头节点更新成保存的下一个节点就可以了，所以说头删的复杂度是O(1)。

// 单链表头删
void SListPopFront(SListNode** pplist)
{
	//pplist不能为空
	assert(pplist);
	//链表为空就不能删除
	assert(*pplist);
	//处理只有一个节点的情况
	if (NULL == (*pplist)->next)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* next = (*pplist)->next;//->优先级高于*，注意运算逻辑
		free(*pplist);
		*pplist = next;
	}
}

 经过我们前面的插入操作，现在链表存储的元素是-1->0->1->2

那么我们接下来调用一次头删，这个操作会把元素-1删除，最终打印出：0->1->2->NULL

调用完头删以后，程序打印结果如下：

 可以看出，我们写出的头删函数完美地完成了这一个任务。

接下来我们处理尾删的问题，和头删的方便快捷不同，尾删需要找尾节点，而由于我们这个链表是单项的，所以只能通过逐一遍历的方式才能找到尾节点，所以单链表的尾插时间复杂度是O(n)！

 我们需要两个指针：prev、tail

prev用来记录tail的前一个节点，tail用来寻找尾节点，找到尾节点后，由于prev已经保存了tail的前一个节点，所以我们直接释放tail。

 只有一个节点的时候，直接释放plist,并且把plist置空就可以了，根据图我们就可以写出代码：

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{//pplist不能为空
	assert(pplist);
	//链表为空就不能删除
	assert(*pplist);
	//处理只有一个节点的情况
	if (NULL == (*pplist)->next)
	{
		free(*pplist);
		*pplist = NULL;
	}
	
	//非空且节点数多于一个的情况
	else
	{
		SListNode* prev = NULL;
		SListNode* tail = *pplist;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = prev;
		prev->next = NULL;
	}
}

接下来我们尾删一个节点，尾删完成后，链表的元素应该是0->1,运行程序观察结果：

 程序和我们预期的结果一致，说明我们尾插的函数逻辑没有出错！

接下来我们就要实现InsertAfter方法和EraseAfter函数，这两个函数的功能是删除指定位置的下一个位置指向的节点，为什么是下一个节点而不是当前节点？理由和尾删一样，单链表只能找到后继，如果删除当前指向的节点，还是需要遍历链表寻找前驱节点，时间复杂度还是O(n)，没有达到快速插入和删除的目的！

在完成Insert函数和Erase函数实现之前，我们可以先写一个Find函数来查找节点：

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur)
	{
		if (x == cur->data)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

Insert函数的图解如下：

根据图片写出代码：

void SListInsertAfter(SListNode* pos, SLTDateType x)
{  
	assert(pos);
//只使用pos和newnode指针要注意连接顺序！
	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

 画出图来分析Erase函数：

Erase的代码如下：

oid SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	//保存pos->next的下一个节点
	SListNode* Next = pos->next->next;
	free(pos->next);
	pos->next = Next;
}

我们接下来来测试代码：

void TestSList()
{
	SListNode* plist = NULL;
	SListPushBack(&plist, 0);
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListNode* pos1 = SListFind(plist, 2);
	SListNode* pos2 = SListFind(plist, 3);
	if (pos1)
	{
		printf("插入值是5的新节点\n");
		SListInsertAfter(pos1, 5);
		SListPrint(plist);
	}
	if (pos2)
	{
		printf("删除值是3的节点的下一个节点\n");
		SListEraseAfter(pos2);
		SListPrint(plist);
	}
}

 可以看到，我们写的Insert和Erase代码完美达到了预期的要求！

最后，因为节点是动态申请的，所以我们需要写一个释放的函数：

// 单链表的销毁
void SListDestory(SListNode* plist)
{
	SListNode* cur = plist;
	SListNode* Next = NULL;
	while (cur)
	{
		Next = cur->next;
		free(cur);
		cur = Next;
	}
}

完整代码如下：

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;
 
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestory(SListNode* plist);

SList.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode=(SListNode*)malloc(sizeof(SListNode));
	if (NULL == newnode)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	return newnode;
}
// 单链表打印
void SListPrint(SListNode* plist)
{    
	SListNode* cur = plist;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newnode = BuySListNode(x);
	//空链表的时候要单独处理
	if (NULL == *pplist)
	{
		*pplist = newnode;
	}
	else
	{
		SListNode* tail = *pplist;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
 
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newnode = BuySListNode(x);
	//空链表要单独处理
	if (NULL == *pplist)
	{
 
		*pplist = newnode;
	}
	else
	{
		newnode->next = *pplist;
		*pplist = newnode;
	}
}
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{//pplist不能为空
	assert(pplist);
	//链表为空就不能删除
	assert(*pplist);
	//处理只有一个节点的情况
	if (NULL == (*pplist)->next)
	{
		free(*pplist);
		*pplist = NULL;
	}
	
	//非空且节点数多于一个的情况
	else
	{
		SListNode* prev = NULL;
		SListNode* tail = *pplist;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = prev;
		prev->next = NULL;
	}
}
// 单链表头删
void SListPopFront(SListNode** pplist)
{
	//pplist不能为空
	assert(pplist);
	//链表为空就不能删除
	assert(*pplist);
	//处理只有一个节点的情况
	if (NULL == (*pplist)->next)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* next = (*pplist)->next;
		free(*pplist);
		*pplist = next;
	}
}
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur)
	{
		if (x == cur->data)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？---->需要遍历找到前驱，时间复杂度是o(n)
void SListInsertAfter(SListNode* pos, SLTDateType x)
{  //保存原有的节点
 
	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？---->需要遍历找到前驱，时间复杂度是o(n)
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	SListNode* Next = pos->next->next;
	free(pos->next);
	pos->next = Next;
}
// 单链表的销毁
void SListDestory(SListNode* plist)
{
	SListNode* cur = plist;
	SListNode* Next = NULL;
	while (cur)
	{
		Next = cur->next;
		free(cur);
		cur = Next;
	}
}

test.c:

#define  _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void TestSList()
{
	SListNode* plist = NULL;
	SListPushBack(&plist, 0);
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListNode* pos1 = SListFind(plist, 2);
	SListNode* pos2 = SListFind(plist, 3);
	if (pos1)
	{
		printf("插入值是5的新节点\n");
		SListInsertAfter(pos1, 5);
		SListPrint(plist);
	}
	if (pos2)
	{
		printf("删除值是3的节点的下一个节点\n");
		SListEraseAfter(pos2);
		SListPrint(plist);
	}
 
	SListDestory(plist);
}
 
int main()
{
	TestSList();
	return 0;
}

下期预告：

本篇文章实现了单链表的增删查改，这是单链表的基础，下一篇博客将会介绍中常见的关于链表的OJ题和曾经作为面经的链表成环追逐问题，敬请期待！！！