【数据结构】初阶——单链表②

再睡一下就好

发布于 2025-06-10 17:13:22

8300

代码可运行

运行总次数：0

代码可运行

前言

什么是链表？

链表是一种在物理存储结构上非连续，但在逻辑结构上连续的一种存储结构，这种逻辑上的联系通过链表中的指针实现。

何为逻辑上的连续呢？我们可以将链表想象成一辆火车，车头连着车厢，车厢与车箱间连着。

注意：

1.链表是逻辑上相连，物理结构上不一定相连；

2.链表的节点一般都是在堆上申请出来的（即malloc或者new出来的）；

一、单链表

实际上链表有很多分类，主要包：

①括带头、不带头；

即链表前是否有head头节点：

②单向或者双向；

③循环、不循环

循环即链表最后一个节点的next指向头节点head：

通过不同的组合可以有不同类型的链表，但在生产生活中我们常用的有两种：

一钟是无头单向不循环链表；

还有一种是带头双向循环链表。

本文主要讨论第一种即单链表，若读者对第二种链表感兴趣，可以到笔者数据结构分组中查看：【数据结构】带头双向循环链表

那么单链表的结构体代码如下：

typedef int DateType;
typedef struct SeqList
{
	DateType _val;//存储数据
	struct SeqList* _next;//存储下一个节点的位置信息
}ListNode;

值得注意的是这里用DateType重命名了int，当后续想变更数据类型时仅改变DateType的的类型即可，无需全篇都去更改，方便了后续更改与维护。

二、增删查改

数据结构无外乎增、删、查、改四个主要功能，以下给出他们对应的函数。

值得注意的是链表一般是在堆中存储的，故为求方便这里使用了二级指针，若有不懂得读者可到评论区中提出疑问，笔者看到立马回复。

1.增

增加，即在链表最前方或最后方生成一个新节点，将数据填充后链接上之前得链表即可，由此思路两步：

1.创造新节点并填充数据；

2.链接上原有链表

头增函数Push_front:

//头插
void Push_front(ListNode**lt,DateType x)
{
	if (!*lt)
		return;

	ListNode* Newnode = BuyNode(x);
	Newnode->_next = *lt;
	(*lt) = Newnode;
}

尾增函数Push_back:

//尾插
void Push_back(ListNode**lt ,DateType x)
{
	if (!*lt)
		return;

	ListNode* tail = *lt;
	ListNode* cur = (*lt)->_next;
	while (cur!=NULL)
	{
		tail = cur;
		cur = cur->_next;
	}

	tail->_next= BuyNode(x);

}

2.删

删出节点，别忘了释放空间！！！

头删函数Pop_front:

//头删
void Pop_front(ListNode**lt)
{
	if (!*lt)
		return;

	ListNode* Newhead = (*lt)->_next;
	free(*lt);
	*lt = Newhead;
}

尾删函数Pop_back:

//尾删
void Pop_back(ListNode**lt)
{
	if (!*lt)
		return;

	ListNode* prve = *lt;
	ListNode* cur = *lt;
	while (cur->_next != NULL)
	{
		prve = cur;
		cur = cur->_next;
	}

	//当删到第一个
	if (cur == prve)
	{
		free(cur);
		//第一个节点释放后，双重指针指向得地方不存在了，置为空
		*lt = NULL;
	}
	else
	{
		prve->_next = NULL;
		free(cur);
	}

}

有效位置任意删除函数Erase：

//单链表删除是删后边的位置
void Erase(ListNode** pos)
{
	if (!pos || !*pos)
		return;

	if ((*pos)->_next->_next != NULL)
	{
		ListNode* next = (*pos)->_next->_next;
		free((*pos)->_next);
		next->_next = next;
	}
	else
	{
		free((*pos)->_next);
		(*pos)->_next = NULL;
	}
}

3.查

通过给出得数据在链表中查找，若找到则返回其指针坐标，若没有找到则返回NULL。

查找函数Find：

//查找
ListNode* Find(ListNode** lt, DateType x)
{
	if (!*lt)
		return NULL;

	ListNode* cur = *lt;
	while (cur != NULL && cur->_val != x)
	{
		cur = cur->_next;
	}
	return cur;
}

4.改

通过查找得到目标位置，我们可在其后插入想要得数据。

若想更改目标节点中的数据？可以先将其删除后再在这个位置插入一个节点填充上想要的数据，有思路，读者看到这不妨自己尝试能不能写出这个函数。

插入函数Insert：

//插入
void Insert(ListNode**pos,DateType x)
{
	if (!pos||!*pos)
		return;

	//单链表插入一定是往后插
	ListNode* next = (*pos)->_next;
	ListNode* NewNode = BuyNode(x);
	(*pos)->_next = NewNode;
	NewNode->_next = next;
}

5.初始化和销毁

出了上述主要功能函数外，还应有初始化和销毁函数，切记用完销毁不需要的链表以防内存泄漏！

初始化函数InitList：

//初始化
void InitList(ListNode** lt,DateType x)
{
	if (!lt)
		return;
		
	*lt = BuyNode(x);
}

销毁函数Destory：

//销毁
void Destory(ListNode**lt)
{
	if (!lt)
		return;

	ListNode* cur = *lt;
	while (cur != NULL)
	{
		ListNode* next = cur->_next;
		free(cur);
		cur = next;
	}
	*lt = NULL;
}

6.打印和创造新节点BuyNode

函数Print_List:

//打印链表
void Print_List(ListNode** lt)
{
	if (!*lt)
		return;

	ListNode* cur = *lt;
	while (cur != NULL)
	{
		printf("%d ", cur->_val);
		cur = cur->_next;
	}
	printf("\n");
}

创造函数BuyNode：

//生成节点
ListNode* BuyNode(DateType x)
{
	ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
	if (!NewNode)
		exit(-1);

	NewNode->_val = x;
	NewNode->_next = NULL;
	return NewNode;
}

三、完整代码

#include<stdio.h>
#include<stdlib.h>

typedef int DateType;
typedef struct SeqList
{
	DateType _val;
	struct SeqList* _next;
}ListNode;

//声明
void Erase(ListNode** pos);
void Insert(ListNode** pos, DateType x);


//生成节点
ListNode* BuyNode(DateType x)
{
	ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
	if (!NewNode)
		exit(-1);

	NewNode->_val = x;
	NewNode->_next = NULL;
	return NewNode;
}

//初始化
void InitList(ListNode** lt,DateType x)
{
	if (!lt)
		return;
		
	*lt = BuyNode(x);
}

//尾插
void Push_back(ListNode**lt ,DateType x)
{
	if (!*lt)
		return;

	ListNode* tail = *lt;
	ListNode* cur = (*lt)->_next;
	while (cur!=NULL)
	{
		tail = cur;
		cur = cur->_next;
	}

	tail->_next= BuyNode(x);

}

//打印链表
void Print_List(ListNode** lt)
{
	if (!*lt)
		return;

	ListNode* cur = *lt;
	while (cur != NULL)
	{
		printf("%d ", cur->_val);
		cur = cur->_next;
	}
	printf("\n");
}

//尾删
void Pop_back(ListNode**lt)
{
	if (!*lt)
		return;

	ListNode* prve = *lt;
	ListNode* cur = *lt;
	while (cur->_next != NULL)
	{
		prve = cur;
		cur = cur->_next;
	}

	//当删到第一个
	if (cur == prve)
	{
		free(cur);
		//第一个节点释放后，双重指针指向得地方不存在了，置为空
		*lt = NULL;
	}
	else
	{
		prve->_next = NULL;
		free(cur);
	}

}

//头插
void Push_front(ListNode**lt,DateType x)
{
	if (!*lt)
		return;

	ListNode* Newnode = BuyNode(x);
	Newnode->_next = *lt;
	(*lt) = Newnode;
}

//头删
void Pop_front(ListNode**lt)
{
	if (!*lt)
		return;

	ListNode* Newhead = (*lt)->_next;
	free(*lt);
	*lt = Newhead;
}

//查找
ListNode* Find(ListNode** lt, DateType x)
{
	if (!*lt)
		return NULL;

	ListNode* cur = *lt;
	while (cur != NULL && cur->_val != x)
	{
		cur = cur->_next;
	}
	return cur;
}

void Insert(ListNode**pos,DateType x)
{
	if (!pos||!*pos)
		return;

	//单链表插入一定是往后插
	ListNode* next = (*pos)->_next;
	ListNode* NewNode = BuyNode(x);
	(*pos)->_next = NewNode;
	NewNode->_next = next;
}

//单链表删除是删后边的位置
void Erase(ListNode** pos)
{
	if (!pos || !*pos)
		return;

	if ((*pos)->_next->_next != NULL)
	{
		ListNode* next = (*pos)->_next->_next;
		free((*pos)->_next);
		next->_next = next;
	}
	else
	{
		free((*pos)->_next);
		(*pos)->_next = NULL;
	}
}

//销毁
void Destory(ListNode**lt)
{
	if (!lt)
		return;

	ListNode* cur = *lt;
	while (cur != NULL)
	{
		ListNode* next = cur->_next;
		free(cur);
		cur = next;
	}
	*lt = NULL;
}

int main()
{
	ListNode*head;
	InitList(&head,0);
	Push_back(&head,1);
	Push_front(&head,-1);
	Print_List(&head);
	
	Destory(&head);
	return 0;
}

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

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

数据