文章目录

• 前言
• 一、链表的概念及结构
• 二、无头单向非循环链表
• • 链表的实现
  • 1.结构体声明
  • 2.单链表打印
  • 3.尾插
  • 4.头插
  • 5.尾删
  • 6.头删
  • 7.单链表查找
  • 8.插入（在pos之前插入）
  • 9.删除（在pos之前删除）
  • 10.插入（在pos之后插入）
  • 11.删除（在pos之后删除）
  • 12.销毁
• 总结

前言

链表是数据结构中常用的结构，它可以在任意内存上申请适合的空间，极大的提高了内存的利用率，有效的解决了内存浪费的问题，那么就让我们了了解一下单链表吧。

一、链表的概念及结构

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

注意：
1.从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续；
2.现实中的结点一般都是从堆上申请的；
3.从堆上申请的空间，是按照一定的策略来分配的，两次分配的空间可能连续也可能不连续，所以需要使用指针去连接；

二、无头单向非循环链表

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。

链表的实现

1.结构体声明

typedef int SLTDataType;  typedef struct SListNode   { 	SLTDataType data; 	struct SListNode* next; }SLTNode; 

2.单链表打印

空链表也可以打印所以不需要在开头断言

void SLTPrint(SLTNode* phead) { 	//不可以断言 	SLTNode* cur = phead;  	while (cur != NULL) 	{ 		printf("%d->", cur->data); 		cur = cur->next; 	} 	printf("NULL\n"); } 

3.尾插

空链表也可以尾插，此处不用断言；
单链表的尾插比较麻烦，需要先找尾，然后插入数据。

void SLTPushBack(SLTNode** pphead, SLTDataType x) { 		SLTNode* newnode = BuySLTNode(x);  	if (*pphead == NULL) 	{ 		*pphead = newnode; 	} 	else 	{ 		//找尾 		SLTNode* tail = *pphead; 		while (tail->next != NULL) 		{ 			tail = tail->next; 		} 		tail->next = newnode; 	} } 

4.头插

链表的头插非常方便，可以直接在开头进行插入；
需要注意的是要将头指针的位置传出去，所以需要使用二级指针传参，或者返回指针。

void SLTPushFront(SLTNode** pphead, SLTDataType x) { 	SLTNode* newnode = BuySLTNode(x);  	newnode->next = *pphead; 	*pphead = newnode; } 

5.尾删

空链表不可删除，所以需要断言；
只有一个结点时需要单独处理，将空间释放；
多个结点时再进行删除。

void SLTPopBack(SLTNode** pphead) { 	assert(pphead); 	assert(*pphead);//空链表不能删除，但可以插入，要注意  	//1.只有一个结点 	//2.多个结点 	if ((*pphead)->next == NULL) 	{ 		free(*pphead); 		*pphead = NULL; 	 } 	else 	{ 		//SLTNode* prev = NULL; 		SLTNode* tail = *pphead; 		//找尾 		while (tail->next->next != NULL)//找倒数第二个 		{ 			//prev = tail; 			tail = tail->next; 		}  		free(tail->next); 		tail->next = NULL; 		//prev->next = NULL; 	}	 } 

6.头删

头删也需要进行断言，防止链表为空；
但是头删不需要找尾，也不需要单独处理单个结点的情况。

void SLTPopFront(SLTNode** pphead) { 	assert(pphead); 	assert(*pphead);  	SLTNode* first = *pphead; 	*pphead = first->next;  	free(first); 	first = NULL; } 

7.单链表查找

从头开始，依次进行查找，并返回地址。

SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { 	SLTNode* cur = phead;  	while (cur != NULL) 	{ 		if (cur->data == x) 		{ 			return cur; 		}  		//遍历链表 		cur = cur->next; 	}  	return NULL; } 

8.插入（在pos之前插入）

插入前需要申请新结点

SLTNode* BuySLTNode(SLTDataType x) { 	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); 	if (newnode == NULL) 	{ 		perror("malloc fali"); 		return NULL; 	} 	newnode->data = x; 	newnode->next = NULL;  	return newnode; } 

在链表结点之前插入不是很方便，这是因为之前的结点没有记录，所以需要记录好前一个结点。

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { 	//断言 pos 不能为空  	assert(pos);   	if (pos == *pphead) 	{ 		SLTPushFront(&pos, x); 	} 	else 	{ 		SLTNode* prev = *pphead; 		//寻找pos的前一个结点 		while (prev->next != pos) 		{ 			prev = prev->next; 		}  		SLTNode* newnode = BuySLTNode(x); 		prev->next = newnode; 		newnode->next = pos; 	} } 

9.删除（在pos之前删除）

删除时需要判断链表是否为空；
对于头删的情况需要特殊处理；
删除链表之后要及时释放内存。

void SLTErase(SLTNode** pphead, SLTNode* pos) { 	assert(pphead); 	assert(pos); 	assert(*pphead);  	if (*pphead == pos) 	{ 		SLTPopFront(pphead); 	} 	else 	{ 		SLTNode* prev = *pphead; 		while (prev->next != pos) 		{ 			prev = prev->next; 		}  		prev->next = pos->next;  		free(pos); 		//这里直接置空pos没用 		//也可以传入二级指针ppos直接在这里释放 	} } 

10.插入（在pos之后插入）

结点之后插入比较方便

void SLTInsertAfter(SLTNode* pos, SLTDataType x) { 	assert(pos);  	SLTNode* newnode = BuySLTNode(x); 	newnode->next = pos->next; 	pos->next = newnode; } 

11.删除（在pos之后删除）

void SLTEraseAfter(SLTNode* pos) { 	assert(pos); 	assert(pos->next);  	//为了不丢失pos->next，记录它 	SLTNode* del = pos->next; 	pos->next = del->next;  	free(del); 	del = NULL; } 

12.销毁

链表使用结束后需要及时销毁，防止内存泄漏。

void SLTDestroy(SLTNode* phead) {  	SLTNode* cur = phead; 	while (cur) 	{ 		SLTNode* tmp = cur->next; 		free(cur); 		cur = tmp; 	} 	//phead 置空是没用的，可以在使用时置空 } 

总结

单链表的结构有很大的弊端，比如：不好使用前面的结点。所以在实际中中有很大的不便，它也不作为主要使用的链表类型，但是它对于“头”的操作很方便，因此也作为很多结构的子结构。

请各位多多支持，不要忘记三连哦！