【数据结构】——单链表超详细介绍（独家介绍，小白必看！！！）

被滑走别滑走，我这一万字的文章，写的真的很痛苦的，希望能得到一点点支持！！！

重点内容和易错点都用彩笔标注了，干货满满，耐心看完，我真的真的有在认真更新o(╥﹏╥)o

上一篇文章介绍完顺序表后，我们就要开始学习链表了，链表的种类有很多，比如说单链表、双向链表、循环或者非循环链表以及带头或者不带头链表等，那么链表和顺序表有哪些不同呢，相较于顺序表，链表做了哪些改变呢，有什么优势呢？今天我就带大家先了解最简单的链表——单链表。

目录

1、链表的概念及结构

1.1链表的概念

1.2 链表的结构

2、链表的实现

2.1 定义结点

2.2 链表的功能

2.3 链表功能的实现

2.3.1 打印单链表

2.3.2 创建一个新结点

2.3.3 单链表尾插

2.2.4 单链表尾删

2.2.5  顺序表头删

 2.2.6 顺序表头插

2.2.7 查找某个结点

2.2.8 删除某个结点

2.2.9 单链表结点修改

2.2.10 单链表前插入结点

2.2.11 单链表后插入结点

2.2.12 这里是对2.2.7—2.2.11的应用教学（⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄）：

2.2.13 销毁链表

3、总代码

3.1 SLT.h

3.2 SLT.c

3.3 test.c

1、链表的概念及结构

1.1链表的概念

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，但链表在逻辑上是连续的，顺序的，而数据元素的逻辑顺序是通过链表中的指针连接次序实现的。

1.2 链表的结构

链表是由一个个结点组成的，结点如下图所示：

注意：链表中的最后一个结点的next指向空，next=NULL。

一个个结点串成了链表，如下图所示：

 有人可能会有疑问，不是说链表只是在逻辑结构上是连续的，在物理存储结构上是不连续的，那为什么上图中一个个结点明明是挨在一起的，那么它在物理存储结构上肯定是连续的呀，其实不然，上图是为了方便大家理解，才用线条连接了结点，实际上在内存中，每个结点可能会隔得很远，仔细观察每个结点上面的红色文字，那就是这个结点的地址，而蓝色文字是下一个结点的地址，很明显能看到这两个结点并不是相邻的，因此也验证了顺序表在逻辑结构上确实是连续的，但在物理存储结构上确实是不连续的。

2、链表的实现

2.1 定义结点

介绍一下单链表的英文名——single linked list，我们简写成SL（区别于顺序表的SeqList或者SQL）。

注意：next指针的类型是SListNode*，千万不要写成SLTDateType*（呜呜呜呜o(╥﹏╥)o，我就写错过，好悲伤，我觉得出这个问题还是因为没有完全理解链表）

typedef int SLTDateType;
typedef  struct SListNode
{
	SLTDateType Date;
	SListNode* next;
}SListNode;

2.2 链表的功能

链表要实现那些功能呢？其实这些功能我们都很熟悉，数据结构无非是对数据进行管理，要实现数据的增删查改，因此链表的基本功能也都是围绕着数据的增删查改展开。

注意：链表是不需要进行初始化的。（看后面结点的创建就明白了）

//创建一个结点
SLTNode* BuyListNode(SLTDateType x);
//销毁单链表
void SLTDestory(SLTNode** pphead);
//单链表头插
void SLTPushFront(SLTNode** pphead, SLTDateType x);
//单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x);
//单链表头删
void SLTPopFront(SLTNode** pphead);
//单链表尾删
void SLTPopBack(SLTNode** pphead);
//单链表结点查找
SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x);
//单链表结点删除(删除pos位置的结点)
void SLTErase(SLTNode** pphead, SLTNode* pos);
//单链表结点插入(在pos之前插入)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
// 单链表结点插入(在pos之后插入)
void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x);
// 单链表结点修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x);
//打印单链表
void PrintSLT(SLTNode * phead);

2.3 链表功能的实现

2.3.1 打印单链表

注意：链表和顺序不同的是，顺序表传过来的指针是肯定不会为空的，而链表传过来的指针是可能为空的，比如说当链表中没有元素时，头指针所指向的就是NULL，如果在第一行写上断言就会有问题。

当cur指向空的时候就可以停止打印了。

void PrintSLT(SListNode*phead)
{
	//注意：不需要断言assert(psl)；
	SListNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->date);
		cur = cur->next;
	}
	printf("NULL");
	printf("\n");
	//最后打印出来的效果就是 1->2->3->4->NULL
}

2.3.2 创建一个新结点

后面我们要在单链表中进行头插和尾插，此时插入的不再是像顺序表一样简单的SLDateType数据了，而是一个结点，这个结点是包括SLTDateType数据以及SLTDateType*的指针，因此，为了方便和减少代码的重复度，我们另写一个函数用来专门创建新结点。

//创建一个新结点
SListNode* BuySLTNode(SLDateType x)
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	if (newNode == NULL)
	{
		perror("malloc:");
		return;
	}
	newNode->date = x;
	newNode->next = NULL;
	return newNode;
}

2.3.3 单链表尾插

注意：在创建结点时，已经让 结点.next=NULL，所以不需要在插入完结点后，再让新结点的next指针为NULL。

有人可能会有疑问，为什么之前打印链表的时候不用断言指针，而在尾插时就要断言指针，以及为什么函数的形参是二级指针，而不使用一级指针。

因为，尾插分为两种情况（下面有写），当链表为空时，头指针phead指向NULL，尾插相当于头插，此时要改变phead的指向，让phead指向这个新结点，此时就需要二级指针来改变一级指针的值（如果我们用一级指针做形参，形参的改变不会影响实参，那么一级指针phead就不会被改变）。

至于这个什么时候要断言指针，什么时候不用断言指针：一级指针也就是phead，当链表为空的时候，phead就是为NULL，而二级指针永远指向phead，phead的地址是永远存在的，那么pphead就一定不可能为空，所以需要断言pphead。

//单链表尾插
void SLTPushBack(SListNode**pphead, SLDateType x)
{
	assert(pphead);
	SListNode* newnode = BuySLTNode(x);
	//1.链表为空
	//2.链表不为空
	if (*pphead == NULL)
	{
		*pphead = newnode;
        //不需要让newnode->next=NULL,在BuySLTNode中我们就已经进行过这个操作了
	}
	else
	{
		//找到链表的尾巴tail
		SListNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

2.2.4 单链表尾删

要想删除链表中的元素，就必须保证原链表就有元素，因此要断言assert(*pphead)。

尾删需要分情况去讨论

//尾删
void SListPopBack(SListNode**pphead)
{
	assert(pphead);
	assert(*pphead);
	//1.链表只有一个元素
	//2.链表有两个及两个以上的元素
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* tail = *pphead;
		SListNode* prev = NULL;
		//找尾
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
		tail = NULL;
·       另一种方法
		//SListNode* tail = *pphead;
		//while (tail->next->next)
		//{
		//	tail = tail->next;
		//}
		//free(tail->next);
		//tail->next = NULL;
	}
}

推荐使用上述代码中的另一种方法，更简洁！ 

2.2.5  顺序表头删

头删没什么好说的，记住要断言*pphead，保证链表内容不为空。

//头删
void SListPopFront(SListNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SListNode* cur = *pphead;
	*pphead = (*pphead)->next;
	free(cur);
	cur = NULL;
}

 2.2.6 顺序表头插

现在是不是觉得头插很简单了啊！(#^.^#)

//头插
void SListPushFront(SListNode** pphead,SLDateType x)
{
	assert(pphead);
	SListNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

2.2.7 查找某个结点

这个函数返回值不再是void，而是SListNode*，把找到的结点的地址返回去，这个函数一般会跟结点修改之类的函数一起使用。

//单链表结点的查找
SListNode* SListNodeFind(SListNode* phead,SLDateType x)
{
	SListNode* cur = phead;
	while (cur)
	{
		if (cur->date == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

2.2.8 删除某个结点

//删除某个结点
void SListNodeErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(pos);
	//头删
	//非头删
	if (*pphead == pos)
	{
		SListNode* cur = *pphead;
		*pphead = (*pphead)->next;
		free(cur);
		cur = NULL;
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
			assert(prev->next);
			//这里为什么要加个断言?
		}
		prev->next = pos->next;
		free(pos);
	}
}

注意：

1. pos也要断言，pos可不能为空呀！
2. cur->next也要断言，因为当cur->next为NULL时，说明整个链表的结点都排查完了，最后还是没有找到地址为pos的结点，证明pos传值有误。

2.2.9 单链表结点修改

// 单链表结点修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x)
{
	SLTNode* cur = phead;
	while (cur != pos)
	{
		cur = cur->next;
		assert(cur);
	}
	pos->data = x;
}

2.2.10 单链表前插入结点

注意分情况讨论。

//单链表前插入结点
void SLTInsertFront(SListNode** pphead, SListNode* pos,SLDateType x)
{
	assert(pphead);
	assert(pos);
	//头插
	//非头插
	SListNode* newnode = BuySLTNode(x);
	if ((*pphead)->next == pos)
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
			assert(prev->next);
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}

2.2.11 单链表后插入结点

这里我要提醒一下，千万不要忘记判断pos是否正确，不要只单单断言pos是否为NULL，还要判断能不能在链表中找到pos这个地址（我第一次写链表就忘记检查了，第二次写还是忘记了，非常容易忘记o(╥﹏╥)o）

//单链表后插入结点
void SLTInsertBack(SListNode* phead, SListNode* pos, SLDateType x)
{
	assert(pos);
	SListNode* cur = phead;
	//防止pos传错了
	while (cur != pos)
	{
		cur = cur->next;
		assert(pos);
	}
	SListNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

2.2.12 这里是对2.2.7—2.2.11的应用教学（⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄）：

我们如何把这几个函数使用起来呢，在初始完链表后，我们可以用SLTNodeFInd函数去找到一个结点（比如说找到某个数据值是4的结点的地址），得到函数返回值——目标结点的地址后，我们可以把它的地址作为pos传给函数，比如说SLTNodeModify函数，或者SLTNodeInsertBack函数，去修改顺序表。

如下所示（下面的代码是在初始化链表后才进行这些操作）：

    SLTNode* pos = SLTNodeFind(plist, 0);
	SLTInsert(&plist, pos, -2);
	PrintSLT(plist);
	SLTInsert(&plist, pos, -1);
	PrintSLT(plist);
	SLTInsertBack(&plist, pos, 3);
	PrintSLT(plist);
	SLTModify(plist, pos, 4);
	PrintSLT(plist);

2.2.13 销毁链表

销毁链表这一块，咱可不敢直接free(phead)，因为链表在物理结构上是不连续存储的，销毁链表必须要一个结点一个结点去销毁！！！！最后不要忘记把phead置为NULL。

//销毁链表
void SLTDestory(SListNode** pphead)
{
	assert(pphead);
	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

3、总代码

3.1 SLT.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLTDateType;
typedef struct SLTNode
{
	SLTDateType data;
	struct SLTNode* next;
}SLTNode;
//创建一个结点
SLTNode* BuyListNode(SLTDateType x);
//销毁单链表
void SLTDestory(SLTNode** pphead);
//单链表头插
void SLTPushFront(SLTNode** pphead, SLTDateType x);
//单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x);
//单链表头删
void SLTPopFront(SLTNode** pphead);
//单链表尾删
void SLTPopBack(SLTNode** pphead);
//单链表结点查找
SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x);
//单链表结点删除(删除pos位置的结点)
void SLTErase(SLTNode** pphead, SLTNode* pos);
//单链表结点插入(在pos之前插入)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
// 单链表结点插入(在pos之后插入)
void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x);
// 单链表结点修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x);
//打印单链表
void PrintSLT(SLTNode * phead);

3.2 SLT.c

#include"SLT.h"

//建立一个新的结点
//这是链表的缺点：经常需要使用malloc为newnode开辟空间
SLTNode* BuyListNode(SLTDateType x)
{
	//为什么要用malloc，是因为，如果在BuyListNode函数中SLTNode newnode，出了这个函数，newnode就被销毁了，
	//用malloc开辟空间，只要我们不主动释放这个空间，这个空间的数据一直存在，
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	//static SLTNode newnode；
	if (newnode == NULL)
	{
		perror("malloc:");
		exit(0);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//头插
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);//phead可能为NULL，但是pphead指向phead，不可能为空
	SLTNode* newnode = BuyListNode(x);
	//这里可不是newnode->next = (*pphead)->next;
	newnode->next = *pphead;
	*pphead = newnode;
}


//尾插
//尾插特别容易出错，当链表中没有数据，即phead=NULL时，尾插就相当于头插了，此时需要改变phead的值
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
	SLTNode* newnode = BuyListNode(x);
	//1、空
	//2、非空
	if (*pphead == NULL)
	{
		*pphead = newnode;
		//newnode->next = NULL;这一步是不需要的，newnode在建立的时候就默认newnode->next=NULL；
	}
	else
	{
		SLTNode* cur = *pphead;
		//这是单向链表的缺点，需要去找尾
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	//温柔的检查
	if (*pphead == NULL)
		return;
	//暴力的检查
	assert(*pphead);
	SLTNode* head = *pphead;
	*pphead = (*pphead)->next;
	free(head);
	head = NULL;
}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	//1、一个结点
	//2、两个结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next->next)
		{
			cur = cur->next;
		}
		free(cur->next);
		cur->next = NULL;
	}
}
//打印单向链表
void PrintSLT(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL");
	printf("\n");
}

//单链表查找某个结点
SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x)
{
	SLTNode* find = phead;
	//别忘记分析找不到结点的情况
	while (find)
	{
		if (find->data == x)
		{
			return find;
		}
		find = find->next;
	}
	return NULL;
}

//删除pos位置的结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
			//如果prev->next已经为空了，说明链表已经查完了，还没有查到pos
			//证明pos传入有误
			assert(prev->next);
		}
		prev->next = pos->next;
		free(pos);
		//pos = NULL;这个没必要，改变不了pos
	}
}
//单链表结点前插
//一般插入结点都是在pos之前插入，但单链表在实现前插是比较困难的
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(pphead);
	//头插
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	//非头插
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
			assert(prev->next);
		}
		SLTNode* newnode = BuyListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
//单链表结点后插
void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	SLTNode* cur = *pphead;
	while (cur != pos)
	{
		cur = cur->next;
		//防止pos传错了
		assert(cur);
	}
	SLTNode* newnode = BuyListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

// 单链表结点修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x)
{
	SLTNode* cur = phead;
	while (cur != pos)
	{
		cur = cur->next;
		assert(cur);
	}
	pos->data = x;
}
//销毁链表
void SLTDestory(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	//比cur->next!=NULL更好一些
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

3.3 test.c

这个test文件我就写的有点简陋，大家可以多去试试函数，找出我没有找到的bug（但是我觉得我的程序应该没什么问题了哈哈哈哈）。

#include"SLT.h"
void test1()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 0);
	SLTPushFront(&plist, -1);
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	PrintSLT(plist);
	SLTPopFront(&plist);
	SLTPopBack(&plist);
	PrintSLT(plist);
	SLTNode* pos = SLTNodeFind(plist, 0);
	SLTInsert(&plist, pos, -2);
	PrintSLT(plist);
	SLTInsert(&plist, pos, -1);
	PrintSLT(plist);
	SLTInsertBack(&plist, pos, 3);
	PrintSLT(plist);
	SLTModify(plist, pos, 4);
	PrintSLT(plist);
}
int main()
{
	test1();
}

谢谢你看完我的文章，喜欢我的文章的话就给我点个赞再走吧！

下次见！拜拜┏(＾0＾)┛