数据结构：单链表的实现

Ronin305

发布于 2025-12-22 12:42:30

350

上一次我们实现了顺序表的应用，但是对于顺序表还是会有以下几个问题：

1. 中间/头部的插入删除，时间复杂度为O(N)。 2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。那么有没有什么解决办法呢？

答案肯定是有的，那就是单链表。

那什么是单链表呢？

单链表的概念

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。单链表中的数据元素由一个数据域和一个指针域组成，其中指针域指向下一个数据元素。

简单来讲：

单链表由一系列的节点组成，每个节点包含数据部分和指针部分。

数据部分：存储实际的数据信息

指针部分：指向下一个节点，用于建立节点之间的顺序关系。

如下图所示：

为什么需要指针变量来保存下一个节点的位置？

链表中每个节点都是独立申请的（即需要插入数据时才去申请一块节点的空间），我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。这样就不会造成空间浪费了。

注意：每次申请一块节点空间时，它和之前的节点空间不一定是连续的，所以要想找到这块空间就得通过地址来找。

链表一共有8种分类，如下图所示：

今天我们来实现单链表，也就是不带头单向不循环链表。

同顺序表一样我们先创建一个SList.h的头文件和一个SList.c的源文件，.h文件实现函数的声明，.c文件实现函数的定义。在头文件中我们创建一个结构体，当然在这之前我们先对int类型重定义为SLTDataType(原因同顺序表一样)，结构体成员分别为SLTDataType data和struct SListNode* next，前者存放数据，后者指向下一个节点。

接下来实现单链表的增删查改：

void SLTPrint(SLTNode* phead);

//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

1.链表的打印

打印比较简单，就不细讲了。

注意：这里为了循环遍历链表之后phead仍然指向第一个节点，我们创建了一个变量pcur来遍历链表。

我们创建一个test.c文件来测试一下打印方法

2.链表的插入

1）尾插

尾插之前我们需要先创建一个新的节点

void SLTPushBack(SLTNode** pphead, SLTDataType x);

在这里我们的参数是二级指针，那为什么是二级指针呢？

因为这里有两种情况：空链表和非空链表

空链表时我们需要让新的节点成为第一个节点，实参此时会发生变化，而如果我们实参plist是一级指针,形参pphead也是一级指针的话,就相当于传值调用，在传值调用中形参是实参的临时拷贝，形参的改变不会影响实参，那么形参此时变成了非空链表，但实参仍然是空链表，并不会发生改变。如下图：我们可以看到空链表时，我们尾插一个1，打印出来仍然为空。

所以这个时候我们要想改变实参就要使用二级指针。

当然如果为非空链表的话我们不需要改变实参，只需要通过改变实参中next指针指向的地址（改变next指针指向的地址并不是改变实参），来完成访问下一个节点，此时使用一级指针就没有问题。如下图所示：

所以综合来看我们要使用二级指针作为形参。

现在我们来实现尾插，如下图：

尾插很简单，我们只需要注意，循环遍历时结束条件是尾节点的next指针为空，而不是尾节点为空。

运行测试一下：

2）头插

头插非常简单，也不需要判断是不是空链表，我们将新的节点的next指针指向第一个节点后，就直接让新的节点成为第一个节点，此时就算是空链表，那么也是next指针指向空后，直接让新节点成为第一个节点。

代码如图：

分别运行空链表和非空链表时测试一下：

3.链表的删除

1）尾删

尾删时我们的链表首先不能为空，不然就是删了个寂寞，然后我们要分为一个节点和多个节点。

我们先看多个节点，要先找到尾节点和尾节点前的一个节点，因为我们将尾节点释放后，尾节点前的节点中next指针中还存放着尾节点的地址，此时就会成为野指针，为避免这种情况我们要将尾节点前的节点中next指针置为空，但我们也要找到尾节点前的节点才能操作，所以我们这里创建了prev变量来找到尾节点前的节点。

链表只有一个节点时呢？我们最后将prev->next置为空，但在此之前prev和ptail都指向第一个节点，我们将第一个节点释放后，这个时候prev指针指向的节点不存在，此时prev就是野指针，同样我们的*pphead此时也是野指针，我们也需要将他们手动置为空。那这样的话，如果链表只有一个节点我们直接释放掉第一个节点*pphead,并手动置为空，不需要再创建ptail和prev去找尾节点和尾节点前的节点了。

运行测试一下：

2）头删

头删比较简单，不需要分为链表只有一个节点和多个节点。

运行测试一下：

4.链表的查找

查找很简单，我们只需要遍历链表，找到了就返回该节点的地址，没找到就返回NULL。

运行测试一下：

5.指定位置插入数据

1）指定位置之前插入数据

如果指定位置是第一个节点的话，就相当于是头插，我们直接调用头插就行；如果是其他位置的话，我们需要找到[pos之前的节点，因为我们要让pos之前的节点next指针指向新的节点。

测试运行一下：

2）指定位置之后插入数据

指定位置之后插入非常简单，代码同样满足尾插的情况，所以不需要再额外讨论尾插的情况。

测试运行：

6.删除节点

1）删除pos节点

和尾删有点相似，pos要分为第一个节点和其他节点两种情况。pos为第一个节点是就是头删，可以直接调用头删

测试运行：

2）删除pos之后的节点

注意pos之后的节点不能为空。

测试运行：

7.链表的销毁

需要循环将每个节点都释放掉。如图：

调试一下：

代码如下：

//SList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;//节点的数据
	struct SListNode* next;//指向下一个节点的地址
}SLTNode;

void SLTPrint(SLTNode* phead);

//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

//SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"

//打印
void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
//创建新的节点
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!\n");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//尾插之前得先有一个新的节点才能插
	SLTNode* newnode = SLTBuyNode(x);
	//空链表和非空链表
	if (*pphead == NULL)
	{
		//如果为空链表，直接让新节点成为第一个节点
		*pphead = newnode;
	}
	else
	{
		//尾插之前得要先找到尾节点
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		//此时找到尾节点
		ptail->next = newnode;
	}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);//链表不能为空
	//链表只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//链表有多个节点
	else
	{
		SLTNode* ptail = *pphead;
		SLTNode* prev = *pphead;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
}
//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//没找到
	return NULL;
}
//指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* newnode = SLTBuyNode(x);
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//找到了
		newnode->next = pos;
		prev->next = newnode;
	}
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		//先找到pos之前的节点
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}
//销毁链表
void SListDesTroy(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

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

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

指针