数据结构-单链表

引言

在顺序表的实现中，我们可以发现，顺序表结构存在一定的不足
1.头插/指定位置插入 的复杂度为O（n）
2.增容需要申请新的空间，我们一般采用二倍增容的方式，但这不可避免的会造成空间浪费
3.在每次的realloc增容时，都会需要一定时间消耗，降低程序运行效率

那么有没有一种的数据结构，可以解决上述问题呢？
由此，链表结构应运而生。

一、概念与结构

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

下图用一个很形象的例子来模拟单链表的结构

         单链表的就犹如一辆火车，每个车厢通过中间的工具链接起来，因此，每个车厢都是独立存在的，可以自由的控制车厢节数的多少，充分的利用空间。

那么在链表⾥，每节“⻋厢”是什么样的呢？？

1.1 结点

        与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/结点”
而通过上图，可以得出，结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址。

        图中的plist中贮存的是链表第一个节点的地址，我们称plist此时“指向”第⼀个结点，也称其为链表的头指针。

1.2 单链表的结构

         单链表的结点因包含这个节点的数据，并且我们需要通过利用结构体的自引用，在结构体中创建一个结构体指针指向下一个结构体，即指向下一个节点。
        由此，我们可以构造出链表中的结点对应的结构体及其成员。

假设当前保存的结点为整型：

        当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数据，也需要保存下⼀个结点的地址（当下⼀个结点为空时保存的地址为空）。

        而当我们想要从第⼀个结点⾛到最后⼀个结点时，只需要在当前结点拿上下⼀个结点的地址就可以了。

二、单链表的实现

实现动态顺序表过程中大致分为以下三个部分

2.1 SList.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLDatatype;

typedef struct SList
{
	SLDatatype data;
	struct SList* next;
}SLTNode;

//打印
void SLPrint(SLTNode* sl);

//封装申请新节点函数
SLTNode* SLCreat(SLDatatype data);

//尾插头插
void SLTPushBack(SLTNode** pphead, SLDatatype data);
void SLTPushFront(SLTNode** pphead, SLDatatype data);

//尾删头删
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode* phead, SLDatatype* x);

//指定位置之前/之后插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDatatype* data);
void SLTInsertAfter(SLTNode* pos, SLDatatype* data);

//指定位置/指定位置之后删除
void SLTErase(SLTNode** pphead, SLTNode* pos);
void SLTEraseAfter(SLTNode* pos);

//链表的销毁
void SLTDestory(SLTNode** pphead);

注意第一行的灵魂操作——typedef int SLDatatype：
        链表只是一种数据结构，这也就意味着其并不像数组一样只能存储单一的元素，因此我们使用SLDataType来取代int，这样在未来如果需要改变其储存的类型时候，只需要改上这一行就好了。这些结构体成员在后续论述中经常用到，所以这里单独再截个图。

2.2 SList.c

2.2.1 打印函数

SLTPrint函数有助于我们在对后续函数实现的过程中更加清晰明了的反应链表中元素，可以帮助我们免去一些调试的过程，所以我们首先实现这个函数。

这个函数的参数是一个结构体指针，我们只需要接受这个指针的值，创建while循环，并利用
phead=phead- >next实现节点的遍历并打印，由于我们最后一个结点指向的是空，因此while循环的结束条件即是phead ！=NULL，在这里我们简写为phead，在最后不要忘记printf（“NULL \n”）

void SLTPrint(SLTNode* phead)
{
	while (phead)
	{
		printf("%d->", phead->data);
		phead = phead->next;
	}
	printf("NULL\n");
}

2.2.2 申请新结点

在实现头插尾插等操作时，我们都会使用到申请空间的操作，那么我们便直接将其封装成一个函数来使用，提高写代码的效率.、

单链表的物理结构不一定连续，我们只需要创建一个节点就申请一块空间即可，因此我们使用malloc函数独⽴申请的（即需要插⼊数据时才去申请⼀块结点的空间），比realloc动态增容消耗更低，也不会造成空间浪费。

所以实现这个函数，我们在在创建节点时使用malloc函数开辟一个内存单元,接着将传递过来的参数放在newnode里。然后为newnode结点赋值：newnode->data=x,newnode->next=NULL;最后将创建好的结点返回

SLTNode* SLTCreat(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTDataType));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

注：实现这个函数需要注意以下几点：
1.在申请内存时候，注意由于我们顺序表的内部贮存的类型为我们自定义的SLDatatype，所以申请的内存大小应为(sizeof(SLDatatype)),并且将返回类型强制转换为SLDataType*,并使用对应类型的指针newnode接收。
2.malloc的扩容用概率会失败,如果失败则会返回NULL,所以在使用之前需要写一个判断条件,判断newnode是否等于空指针
3.对新结点赋值完之后我们要返回这个这个结点，因此我们的函数返回类型为SLTNode*

2.2.3 尾插与头插

有了创建结点的函数，接下来自然就是实现结点的插入，插入又分为尾插与头插。

在编写插入函数时，需要注意：结点的插入有可能会对头指针造成改变。
又因为头指针plist本身就是一个一级指针，所以我们应使用二级指针pphead去接受一级指针plist的地址，这样才能在函数内部对其进行修改操作，之后的一些函数也是如此，便不再过多赘述。
以下为一张指针辨析图方便更好的理解

而由于我们在函数实现的时候使用的是二级指针，因此在函数调用的时候传递的参数应当是一级指针的地址
 

void test()
{
	SL* plist = NULL;
	SLPushFront(&plist, 1);
}

 在实现尾插时候，首先创建一个新结点，而后通过链表的遍历找到最后一个结点，再使最后一个结点指向创建好的新结点

但是要注意，尾插需要实现链表的遍历，但如果我们使用(*pphead)=(*pphead)->next进行遍历，则会导致头节点发生改变，所以我们需要使用创建一个新变量pcur将*pphead赋给pcur，再利用pcur进行链表的遍历并找到尾结点。

并且，由于我们使用了pcur=pcur->next的方式进行了遍历，但如果这个链表中并没有结点，此时*pphead指向NULL，那我们再将其赋给pcur遍历就造成空指针的解引用，因此，我们还需要对*pphead进行判断，如果*pphead为NULL，即这个链表没有元素时，我们只需要将吧newnode赋值给*pphead即可。之后的一些函数也是如此，便不再过多赘述。

//尾插
void SLTPushBack(SLTNode** pphead, SLDatatype data)
{
	assert(pphead);
	SLTNode* newnode = SLCreat(data);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* pcur = *pphead;
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		pcur->next = newnode;
	}
}

 而头插则相对方便一些，只需创建一个新结点，再将新结点指向原链表的头结点，再让链表的头指针指向新的头结点。

但是需要注意的是，后两布的操作不可颠倒，若先将头指针指向新结点，则会导致无法找到原来的头结点，就无法将链表连接起来。

以下是示例图 

//头插
void SLTPushFront(SLTNode** pphead, SLDatatype data)
{
	assert(pphead);
	SLTNode* newnode = SLCreat(data);
	newnode->next = *pphead;
	*pphead = newnode;
}

 2.2.4 尾删与头删

首先再进行删除操作之前，要注意，当链表结点为NULL即*pphead==NULL时，不能进行删除操作，并且，如果链表不存在即pphead==NULL时都不能进行删除结点操作，所以亚奥进行断言
assert（*pphead && pphead);并且注意链表此时是否只有一个结点。

尾删时，需要遍历到尾结点，并将这个结点申请的内存释放，并让尾节点的前一结点作为新的尾结点指向空。由于需要定义遍历尾结点的指针pcur以及尾节点的前一结点指针prev，在每一次的遍历时先吧pcur的值给prev，再使得pcur=pcur->next，这样当pcur指向尾结点时，prev刚好指向尾结点前一结点。

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead && pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* pcur = *pphead;
		SLTNode* prev = pcur;
		while (pcur->next)
		{
			prev = pcur;
			pcur = pcur->next;
		}
		free(pcur);
		pcur = NULL;
		prev->next = NULL;
	}
}

头删时，只需要将头结点指向下一节点，并释放掉旧的头节点，并且要注意链表此时是否只有一个结点。

需要注意的是，将头指针指向下一节点时，我们便无法找到旧的头节点，所以我们应先创建一个指针prev指向旧的的头结点，在头结点指向下一节点之后利用prev指针释放掉旧的头节点。

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead && pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev =*pphead;
		*pphead = (*pphead)->next;
		free(prev);
		prev = NULL;
	}
}

2.2.5 查找函数

在实现指定位置插入/删除函数时，我们我们都会需要找到指定的结点，所以干脆将其封装成一个函数实现。

由于查找数据不涉及链表的修改，因此只需要一级指针便可，但是由于我们实现的插入、删除、销毁操作都需要传递二级指针，因此这为了保证函数接口的一致性，使用二级指针也可，这里以一级指针作参数为例子

实现查找函数，我们只需要在while循环里遍历链表，若找到了对应的结点便返回当前结点，若走出了循环则说明遍历完了也未找到，此时便返回NULL即可

//查找
SLTNode* SLTFind(SLTNode* phead, SLDatatype* x)
{
	assert(phead);
	SLTNode* temp = phead;
	while (temp)
	{
		if (temp->data == x)
		{
			return temp;
		}
		temp = temp->next;
	}
	return NULL;
}

2.2.6 指定位置插入

有了查询函数之后，接着就可以实现指定位置的插入前后插入函数了

指点位置之前插入：

在创建一个新结点之后，由于插入元素在指定位置之前，因此我们不仅需要指定位置pos，还需要一个指针pre遍历链表来找到指定位置之前的结点，再让新结点指向pos指向的结点，而后让prev指向的结点指向新结点，与之前的头插操作类似，这两步不可颠倒。

并且我们要注意如果链表中只有一个结点，那么根本没有头结点这一说，因此我们要用分支判断语句区分出这种情况，如果链表中只有一个结点即 *pphead)->next == NULL 那我们只需要调用头插函数即可，但还有一点注意事项是我们的头插函数的参数是一个二级指针，因此我们传递的应该是一级指针的地址，也就是pphead而非*pphead。
以下为一个示意图

//指定位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDatatype* data)
{
	assert(pphead && *pphead && pos);
	if ((*pphead)->next == NULL)
	{
		SLTPushFront(pphead, data);//**********
	}
	else
	{
		SLTNode* newnode = SLCreat(data);
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}

 指定位置之后插入

指定位置之后插入只需要再创建新结点之后，让我们的新结点指向指定位置的下一个结点，在使指定位置指向我们的新结点即可，同样的，这两步不可调转。

//指定位置之后插入
void SLTInsertAfter(SLTNode* pos, SLDatatype* data)
{
	assert(pos);
	SLTNode* newnode = SLCreat(data);
	newnode->next = pos->next;
	pos->next = newnode;
}

2.2.7 指定位置删除 

删除指定位置的结点，首先要注意的是结点不能为空，并且链表不能为空，所以要对其进断言。
类似于指定位置之前插入的，我们需要一个指针prev遍历链表，找到指定位置的前一个结点，并使其指向指定位置的下一结点，并把指定位置申请的空间释放掉。

而当链表中只有一个元素时候，我们只需要使用尾删操作即可

以下为示例图

//指定位置删除
void SLTErase(SLTNode** pphead,SLTNode* pos)
{
	assert(*pphead && pphead);
	assert(pos);
	if ((*pphead)->next==NULL)
	{
		SLTPopBack(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

 2.2.8 链表的销毁

链表的销毁时，我们可以直接使用*pphead进行来进行链表的遍历，此时我们还需要定义一个指针prev，当我们遍历链表时候，prev随之将其前一个结点给释放掉，这样当*pphead最后指向空时，prev刚好指向最后一个结点，并将其释放

void SLTDestory(SLTNode** pphead)
{
	SLTNode* prev = *pphead;
	while (*pphead)
	{
		prev = *pphead;
		free(prev);
		prev = NULL;
		*pphead = (*pphead)->next;
	}
}

2.3 test.c

在测试文件里，我们每实现了一个功能之后都要勤调试，不然一股脑写完之后点击运行则会出现大量的报错，让人根本摸不着头脑。这里附上我自己的测试文件

#include"SList.h"
void SListTest01()
{
	SLTNode* sl=NULL;
	SLTPushFront(&sl, 1);
	//SLTPushFront(&sl, 2);
	//SLTPushFront(&sl, 3);
	//SLTPushFront(&sl, 4);
	//SLTPushFront(&sl, 5);
	SLPrint(sl);
	SLTInsertAfter(SLTFind(sl, 1), 99);
	SLPrint(sl);
	SLTDestory(&sl);
	SLPrint(sl);
}
int main()
{
	SListTest01();
	return 0;
}

三、源码

SList.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLDatatype;

typedef struct SList
{
	SLDatatype data;
	struct SList* next;
}SLTNode;

//打印
void SLPrint(SLTNode* sl);

//封装申请新节点函数
SLTNode* SLCreat(SLDatatype data);

//尾插头插
void SLTPushBack(SLTNode** pphead, SLDatatype data);
void SLTPushFront(SLTNode** pphead, SLDatatype data);

//尾删头删
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode* phead, SLDatatype* x);

//指定位置之前/之后插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDatatype* data);
void SLTInsertAfter(SLTNode* pos, SLDatatype* data);

//指定位置/指定位置之后删除
void SLTErase(SLTNode** pphead, SLTNode* pos);
void SLTEraseAfter(SLTNode* pos);

//链表的销毁
void SLTDestory(SLTNode** pphead);

SList.c 

#define _CRT_SECURE_NO_WARNINGS 1
//打印
#include "SList.h"
void SLPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
//
SLTNode* SLCreat(SLDatatype data)
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLDatatype));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	node->data = data;
	node->next = NULL;
	return node;
}
void SLTPushBack(SLTNode** pphead, SLDatatype data)
{
	assert(pphead);
	SLTNode* newnode = SLCreat(data);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* pcur = *pphead;
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		pcur->next = newnode;
	}
}
void SLTPushFront(SLTNode** pphead, SLDatatype data)
{
	assert(pphead);
	SLTNode* newnode = SLCreat(data);
	newnode->next = *pphead;
	*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead && pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* pcur = *pphead;
		SLTNode* prev = pcur;
		while (pcur->next)
		{
			prev = pcur;
			pcur = pcur->next;
		}
		free(pcur);
		pcur = NULL;
		prev->next = NULL;
	}
}
void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead && pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev =*pphead;
		*pphead = (*pphead)->next;
		free(prev);
		prev = NULL;
	}
}
SLTNode* SLTFind(SLTNode* phead, SLDatatype* x)
{
	assert(phead);
	SLTNode* temp = phead;
	while (temp)
	{
		if (temp->data == x)
		{
			return temp;
		}
		temp = temp->next;
	}
	return NULL;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDatatype* data)
{
	assert(pphead && *pphead && pos);
	if ((*pphead)->next == NULL)
	{
		SLTPushFront(pphead, data);//**********
	}
	else
	{
		SLTNode* newnode = SLCreat(data);
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}
void SLTInsertAfter(SLTNode* pos, SLDatatype* data)
{
	assert(pos);
	SLTNode* newnode = SLCreat(data);
	newnode->next = pos->next;
	pos->next = newnode;
}
void SLTErase(SLTNode** pphead,SLTNode* pos)
{
	assert(*pphead && pphead);
	assert(pos);
	if ((*pphead)->next==NULL)
	{
		SLTPopBack(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = prev->next->next;
		free(pos);
		pos = NULL;
	}
}
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}
void SLTDestory(SLTNode** pphead)
{
	SLTNode* prev = *pphead;
	while (*pphead)
	{
		prev = *pphead;
		free(prev);
		prev = NULL;
		*pphead = (*pphead)->next;
	}
}