单链表实现：从理论到代码

秋邱

发布于 2024-10-09 20:20:06

1240

发布于 2024-10-09 20:20:06

文章被收录于专栏：笔记

前言

前面学习了顺序表，顺序表优点：

可以随机访问元素，通过索引能快速定位到元素。
存储密度高，不需要额外的指针空间。

但是它也有一些不足的地方：

中间/头部位置的插入删除，需要挪动数据，效率低下。
动态顺序表，空间不够时需要扩容，扩容本身有消耗，空间浪费。

这时候就有了链表。

链表的概念以及结构

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

链表分类

链表的结构非常的多样化，一共有2 * 2 * 2种链表。

1、单向或者双向

2、带头或者不带头

3、循环或者不循环

虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构：单链表和双向带头循环链表 1.⽆头单向⾮循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。 2.带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带来很多优势，实现反⽽简单了，后⾯我们代码实现了就知道了。

定义结构体

单链表在内存中的存储（单向，不带头，不循环）

结合前面所学的知识，可以定义结构体：

typedef int SLTypeData;//方便之后更改类型
typedef  struct SListNode
{
	SLTypeData data; //节点数据
	struct SListNode* next; //指针变量保存下个节点的地址
}SLTNode;

单链表的功能

功能实现

对单链表的打印插入数据：头插，尾插，删除某个数据删除数据：头删，尾删，删除某个数据查找数据摧毁单链表

单链表的打印

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

创建一个指针来遍历链表，phead是链表的头节点，通过将phead 赋值给 pcur，就可以利用 pcur来逐个访问链表中的节点。这样能保持phead不变性，方便后续可能的其他操作，而影响phead的值，确保链表结构的完整性。

热知识：while(pcur) 等同于 while(pcur != NULL)

注意

在实现之前，我们需要来了解传值和传址的区别。传值：

是将实参的值复制一份传递给形参。
在函数内部对形参的修改不会影响到外部的实参。

传址：

传递的是实参的地址。
函数内部可以通过该地址直接操作外部的实参。
可以实现对外部数据的修改。

在插入，删除等操作时，需要传一级指针的地址，这就需要用二级指针来接收，若用一级指针来接收，则修改的数据不会影响外部的实参。

插入数据

尾插

思路：首先创建一个newnode，然后进行插入。

情况(1).若头为空，插入的newnode则为头。

情况(2).若头不为空，需要将最后一个节点的下一个节点指向newnode即可。

//尾插
void SLTPushBack(SLTNode** pphead, SLTypeData 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;
	}
}

头插

思路：创建一个newnode，将新节点的下一个节点指向头节点。

代码实现

//头插
void SLTPushFront(SLTNode** pphead, SLTypeData x)
{
	assert(*pphead);//不能对空指针进行解引用
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

指定位置之前插入数据

思路：

创建一个newnode，对数据进行插入。

情况1.若头节点为空，pos成为头节点，进行头插。

情况2.若头节点为非空，这时需要创建变量prev来遍历链表，指向pos的前一个节点(prev)，让前一个节点指向新节点(newnode)，新节点指向pos。

//在指定位置之前插数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTypeData x)
{
	assert(pphead && *pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		SLTNode* newnode = SLTBuyNode(x);
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
		}
}

指定位置之后插入数据

思路：

创建一个新节点(newnode)，将pos newnode pos->next,三者连接起来，先将新节点的下一个节点指向pos的下一个节点(pos->next),然后让pos的下一个节点指向新节点。

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTypeData x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	/*	pos newnode pos->next;*/
    //代码1
	newnode->next = pos->next;
	pos->next = newnode;
    //代码2
    //pos->next = newnode;
    //newnode->next = pos->next;
}

代码2和代码1一样，只是顺序不一样，那么代码1是否能代替代码2呢？

答案是不能，如果先将pos的next指向新节点，那么pos->next，待会酒就会找不到，所以这个代码2是不对的。

删除数据

头删

思路：创建一个变量*phead来接收*pphead，然后让*pphead指向下一个节点((*pphead)->next)，随后释放phead，将其置为NULL。

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* phead = *pphead;
	*pphead = (*pphead)->next;
	free(phead);
	phead = NULL;
}

尾删

思路：

情况1.单节点，即头节直接将头节点释放，置为空。

情况2.多节点，创建两个变量，prev和ptail，遍历链表找到尾节点ptail和尾节点的前一节点prev，将prev的指向的下一个节点置为空，释放ptail，置为空。

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead && pphead);
	//单节点
	
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//多节点
	else
	{
		SLTNode* ptail = *pphead;
		SLTNode* prev = *pphead;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		prev->next = NULL;
		free(ptail);
		ptail = NULL;
	}

}

删除指定位置的数据

思路：

情况1.单节点，头节点与pos相等就是头删。

情况2.多节点，创建一个变量prev赋值为*pphead，遍历pos的前一个节点prev，将prev的下一个节点指向pos->next。

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

删除指定位置之后的数据

思路：

创建一个变量del=pos->next，将pos，del，pos->next三者连接起来，pos下一个节点指向del的下一节点。最后释放del，置为空。

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);//对pos和pos->next断言，不存在办法删
	SLTNode* del = pos->next;
	//pos del del->next
	pos->next = del->next;
	free(del);
	del = NULL;
}

摧毁单链表

思路：

创建一个变量pcur=*pphead，随后进行遍历，每次先将pcur->next，存在next里，释放pcur，pcur =next，最后头节点置为空。

//摧毁链表
void SListDesTroy(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur != NULL)
	{
		SLTNode*	next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

完整代码

Slist.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<stdlib.h>
typedef int SLTypeData;
typedef  struct SListNode
{
	SLTypeData data; //节点数据
	struct SListNode* next; //指针变量?保存下?个节点的地址
}SLTNode;

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

Slist.c

#include"SList.h"

void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while(pcur)//pcur != NULL
	{
		printf("%d", pcur->data);
		printf("->");
		pcur = pcur->next;
	}
	printf("NULL\n");
}
//创建链表
SLTNode* SLTBuyNode(SLTypeData x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc error");
		return NULL;
	}

	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTypeData 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, SLTypeData 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* ptail = *pphead;
		SLTNode* prev = *pphead;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		prev->next = NULL;
		free(ptail);
		ptail = NULL;
	}

}
//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* phead = *pphead;
	*pphead = (*pphead)->next;
	free(phead);
	phead = NULL;
}
// 查找
SLTNode* SLTFind(SLTNode* phead, SLTypeData x)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x) 
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
//在指定位置之前插?数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTypeData x)
{
	assert(pphead && *pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		SLTNode* newnode = SLTBuyNode(x);
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
		}
}
// 删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//prev pos pos->next
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTypeData x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	/*	pos newnode pos->next;*/
	newnode->next = pos->next;
	pos->next = newnode;
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);//对pos和pos->next断言，不存在办法删
	SLTNode* del = pos->next;
	//pos del del - next
	pos->next = del->next;
	free(del);
	del = NULL;
}
//摧毁链表
void SListDesTroy(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur != NULL)
	{
		SLTNode*	next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

Test.c

#include"SList.h"

void test1()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPrint(plist); // 1->2->3->NULL
	
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPushFront(&plist, 6);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTNode* ret = SLTFind(plist, 1);
	if (ret == NULL)
	{
		printf("没找到");
	}
	else
	{
		printf("找到啦");
	}
	SLTInsert(&plist, ret, 5);
	SLTErase(&plist, ret);
	SLTInsertAfter(ret, 6);
	SLTEraseAfter(ret);
	SLTPrint(plist);
	SListDesTroy
}

int main()
{
	test1();
	return 0;
 }

感谢各位大佬的关注，点赞，评论

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

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

指针