【数据结构初阶】单链表

凤年徐

发布于 2025-08-28 13:37:16

8200

代码可运行

文章被收录于专栏：代码飞升代码飞升

运行总次数：0

代码可运行

单链表

1. 链表的概念及结构

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

链表的结构跟火车厢相似，淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的。⻋厢是独⽴存在的，且每节⻋厢都有⻋⻔。想象⼀下这样的场景，假设每节⻋厢的⻋⻔都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带⼀把钥匙的情况下如何从⻋头⾛到⻋尾？最简单的做法：每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。在链表⾥，每节“⻋厢”是什么样的呢？

与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/节点” 节点的组成主要有两个部分：当前节点要保存的数据和保存下⼀个节点的地址（指针变量）。图中指针变量plist保存的是第⼀个节点的地址，我们称plist此时“指向”第⼀个节点，如果我们希望plist“指向”第⼆个节点时，只需要修改plist保存的内容为0x0012FFA0。为什么还需要指针变量来保存下⼀个节点的位置？链表中每个节点都是独⽴申请的（即需要插⼊数据时才去申请⼀块节点的空间），我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。结合前⾯学到的结构体知识，我们可以给出每个节点对应的结构体代码：假设当前保存的节点为整型：

struct SListNode
{
 int data; //节点数据 
 struct SListNode* next; //指针变量⽤保存下⼀个节点的地址 
};

当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数据，也需要保存下⼀个节点的地址（当下⼀个节点为空时保存的地址为空）。当我们想要从第⼀个节点⾛到最后⼀个节点时，只需要在前⼀个节点拿上下⼀个节点的地址（下⼀个节点的钥匙）就可以了。给定的链表结构中，如何实现节点从头到尾的打印？

2. 单链表的实现

1.定义结点

typedef int SLTDataType;

typedef struct SListNode //s single
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

2.打印数据

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

3.申请新的节点

SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode =  (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	//申请成功
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

4.尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//pphead不能为空 不能对空指针解引用
	//空链表和非空链表
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		//ptail指向尾节点
		ptail->next = newnode;
	}
}

5.头插

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

6.尾删

//尾删
void SLTPopBack(SLTNode** pphead)
{
	//链表不能为空
	assert(pphead&&*pphead);
	if ((*pphead)->next == NULL)//->的优先级高于*  所以要加括号
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找尾
		SLTNode* prev = *pphead;//要删除的前一个
		SLTNode* ptail = *pphead;//要删除的
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		//prev ptai
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
}

7.头删

void SLTPopFront(SLTNode** pphead)
{
	//链表不能为空
	assert(pphead && *pphead);
	SLTNode* next= (*pphead)->next;//记得加括号
	free(*pphead);
	*pphead = next;
}

8.查找

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* pcur = phead;
	while (pcur)//pcur != NULL
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//pcur == NULL
	return NULL;
}

9.指点位置之前插入

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);//若*pphead为空 则pos也为空
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	if (pos == *pphead)
	{
		SLTPushFront(pphead,x);
	}
	else
	{
		SLTNode* prev = *pphead;//找pos前一个节点
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//prev newnode pos
		
		prev->next = newnode;
		newnode->next = pos;
	}
	

}

10.指定位置后插入

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;//为什么顺序不能交换
	pos->next = newnode;
}

11.指定位置前删除

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	SLTNode* prev = *pphead;//找pos前一个节点
	if (pos == *pphead)
	{
		//头删
		SLTPopFront(pphead);
	}
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//prev pos pos->next
	prev->next = pos->next;
	free(pos);
	pos = NULL;

}

12.指定位置后删除

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos&&pos->next);
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del->next = NULL;
	
}

13.链表的销毁

void SLTDestroy(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* pcur = *pphead;
	
	while (pcur)
	{
		SLTNode* next = (*pphead)->next;
		free(pcur);
		pcur = next;
	}
	//pcur 为空
	*pphead = NULL;
}

3.程序源码

共分三个文件

SLTist.h 函数的声明

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

//定义节点结构
//数据+指向下一个节点的指针
typedef int SLTDataType;

typedef struct SListNode //s single
{
	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 SLTDestroy(SLTNode** pphead);

SList.c 函数的实现

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"
void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)//pcur!=NULL
	{
		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!");
		exit(1);
	}
	//申请成功
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//pphead不能为空 不能对空指针解引用
	//空链表和非空链表
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		//ptail指向尾节点
		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&&*pphead);
	if ((*pphead)->next == NULL)//->的优先级高于*  所以要加括号
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找尾
		SLTNode* prev = *pphead;//要删除的前一个
		SLTNode* ptail = *pphead;//要删除的
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		//prev ptai
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
}
//头删
void SLTPopFront(SLTNode** pphead)
{
	//链表不能为空
	assert(pphead && *pphead);
	SLTNode* next= (*pphead)->next;//记得加括号
	free(*pphead);
	*pphead = next;
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* pcur = phead;
	while (pcur)//pcur != NULL
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//pcur == NULL
	return NULL;
}

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);//若*pphead为空 则pos也为空
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	if (pos == *pphead)
	{
		SLTPushFront(pphead,x);
	}
	else
	{
		SLTNode* prev = *pphead;//找pos前一个节点
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//prev newnode pos
		
		prev->next = newnode;
		newnode->next = pos;
	}
	

}


void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;//为什么顺序不能交换
	pos->next = newnode;
}

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	SLTNode* prev = *pphead;//找pos前一个节点
	if (pos == *pphead)
	{
		//头删
		SLTPopFront(pphead);
	}
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//prev pos pos->next
	prev->next = pos->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->next = NULL;
	
}
void SLTDestroy(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* pcur = *pphead;
	
	while (pcur)
	{
		SLTNode* next = (*pphead)->next;
		free(pcur);
		pcur = next;
	}
	//pcur 为空
	*pphead = NULL;
}

test.c 用来测试

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"

void SListTest01()
{
	//链表是由一个一个的节点组成
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;
	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;

	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;

	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;

	//将四个节点连接起来
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;
	//调用链表的打印
	SLTNode* plist = node1;
	SLTPrint(plist);

}
void Test02()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	//SLTPushFront(&plist, 5);
	//SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTNode* find = SLTFind(plist,3);
	/*if (find == NULL)
	{
		printf("没有找到\n");
	}
	else
	{
		printf("找到了！\n");
	}*/
	//SLTInsert(&plist, find,11);
	SLTInsertAfter(find,9);

	SLTPrint(plist);
	SLTPopFront(&plist);

	SLTPrint(plist);
	SLTEraseAfter(find);
	SLTDestroy(&plist);

	SLTPrint(plist);




}
int main()
{
	//SListTest01();
	Test02();

	return 0;
}

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

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

数据结构