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

用户11036582

发布于 2024-04-10 08:26:28

1300

发布于 2024-04-10 08:26:28

文章被收录于专栏：跟我一起学编程跟我一起学编程

链表的概念：

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

链表的结构：

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

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

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

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

链表的实现：

1.1定义节点

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

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

1.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.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.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 单链表尾插

注意：在创建结点时，已经让结点.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.4顺序表头删

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

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

2.5顺序表头插

现在是不是觉得头插很简单了啊！

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

2.6查找某个结点

这个函数返回值不再是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.7删除某个结点

//删除某个结点
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);
	}
}

注意：

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

2.8单链表结点修改

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

2.9单链表前插入结点

//单链表前插入结点
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.10单链表后插入结点

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

//单链表后插入结点
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.11销毁链表

销毁链表这一块，咱可不敢直接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.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

#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();
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-04-07，如有侵权请联系 cloudcommunity@tencent.com 删除

指针