C语言手撕单链表

这篇具有很好参考价值的文章主要介绍了C语言手撕单链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构,也就是内存存储不是像顺序表那么连续存储,而是以结点的形式一块一块存储在堆上的(用动态内存开辟)。

既然在内存上不是连续存储,那我们如何将这一块一块单独的空间链接起来呢?

我们可以创建一个结构体充当我们的结点,里面分别存放数据(数据域)和下一个结点的地址(指针域),这样我们就可以将一块一块单独的空间链接起来了。

而单链表,顾名思义就是单向链接的链表,效果如同下图

C语言手撕单链表,数据结构,C语言,c语言,数据结构,链表

前言:

在讲解单链表的各个接口前,很有必要讲解以下单链表的物理内存到底是如何存储的,先掌握这个,接下来的讲解就会更容易理解

头结点指向的地址就是第一个结点的地址

第一个结点的指针域指向的是第二个结点的总地址,所以分为两个地址

一个是结点的总地址,另一个是结点总地址里面的next指针存放的指针域的地址,这个指针域的地址又指向了下一个结点的总地址。

看下面的图解内存存储的数据,实际中是没有箭头的,把箭头去掉,才是内存中真正的存储模式

C语言手撕单链表,数据结构,C语言,c语言,数据结构,链表

二、接口实现

对数据结构我们一般采用增删查改去实现。

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

SLTNode* BuySListNode(SLTDataType x);

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

void SLTPushFront(SLTNode** phead, SLTDataType x);

void SLTPopFront(SLTNode** phead);

void SLTPopBack(SLTNode** phead);

 1、遍历单链表打印函数

一般需要创建一个临时变量去接收头结点

//遍历链表肯定需要头结点
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;//一般需要临时创建变量
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL");
}

2、创建单链表函数

SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror(malloc);
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
}

3、尾插

需要分情况讨论,

  • 如果链表本身是空,直接改变头结点的指针,直接指向新建的结点
  • 若不为空,需要找到尾结点

TIP:何时用指针变量,何时用二级指针?

改变结构体本身,需要结构体指针

改变结构体指针,需要结构体指针指针(二级指针),并且要有解引用的操作

刚才第一种情况,直接将头结点的指针改变成新指针的地址,这种直接改变指针的模式,就需要二级指针,进行解引用才能达到目的。

void SLTPushBack(SLTNode** phead, SLTDataType x)
{
	//需要分情况讨论,如果链表本身是空
	if (*phead == NULL)
	{
		SLTNode* newnode = BuySListNode(x);
		//改变结构体本身,需要结构体的指针
		//改变结构体指针,需要结构体指针指针(二级指针),并且要有解引用的操作
		*phead = newnode;
	}
	else
	{
		//先找尾结点
		SLTNode* newnode = BuySListNode(x);
		SLTNode* tail = *phead;//需要对phead进行解引用
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
	
}

4、头插

头插肯定需要二级指针,因为每次头插都要改变头指针指向的位置

//头插肯定需要二级指针,因为每次头插都要改变头指针指向的位置
void SLTPushFront(SLTNode** phead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *phead;
	*phead = newnode;
}

5、尾删

分三种情况

  • 第一种是链表为空,需要assert断言检查
  • 第二种链表中只有一个结点,需要改变结构体指针,因此函数传参也是需要二级指针
  • 第三种链表有多于一个的结点,需要先找到尾结点。
void SLTPopBack(SLTNode** pphead)
{
	//分三种情况
	// 第一种就是链表为空
	assert(*pphead);
	// 第二种链表只有一个结点,需要改变结构体指针
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		pphead = NULL;
	}
	//第三种链表多于一个结点
	else
	{
		SLTNode* tail = *pphead;
		SLTNode* tailprev = NULL;
		while (tail->next != NULL)
		{
			tailprev = tail;
			tail = tail->next;
		}
		free(tail);
		tailprev->next = NULL;//严格要求尾指针前一个的next指向null
	}
}

6、头删

不需要分类讨论,直接改变头节点的指针指向,但是需要一个临时变量存储结点,便于后面的操作

void SLTPopFront(SLTNode** phead)
{
	assert(*phead);
	SLTNode* newnode = (*phead)->next;
	free(*phead);
	*phead = newnode;
}

三、链表和顺序表的比较

顺序表:数组

缺点:

  1. 中间或者头部插入删除数据要挪动数据,效率低
  2. 空间不够,只能扩容。扩容有消耗
  3. 倍数扩容,用不完,存在空间浪费

优点:

  1. 下标随机访问。排序,二分查找适合
  2. CPU高速缓存命中率比较高

链表

优点:

  1. 任意位置插入删除效率高
  2. 按需申请释放,不存在扩容

缺点:

  1. 下标不是随机访问,不适合排序,二分查找
  2. CPU高速缓存命中率比较低

由此可见,链表和顺序表是两种互补的数据结构~文章来源地址https://www.toymoban.com/news/detail-623181.html

到了这里,关于C语言手撕单链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】手撕双向链表

    目录 前言 1. 双向链表  带头双向循环链表的结构 2. 链表的实现 2.1 初始化 2.2 尾插 2.3 尾删 2.4 头插 2.5 头删 2.6 在pos位置之前插入 2.7 删除pos位置 3.双向链表完整源码 List.h List.c 在上一期中我们介绍了单链表,也做了一些练习题,在一些题中使用单链表会十分繁琐。因为单链

    2024年02月05日
    浏览(49)
  • 数据结构-链表-单链表(3)

    目录 1. 顺序表的缺陷 2. 单链表 2.1 单链表的基本结构与接口函数 2.2 重要接口 创建新节点的函数: 2.2.1 尾插 2.2.2 头插 2.2.3 尾删 2.2.4 头删 2.2.5 查找 2.2.6 插入 2.2.7 删除 2.2.8 从pos后面插入 2.2.9 从pos后面删除 3. 链表的缺陷与优势: 4. 链表与顺序表比较 写在最后: 为什么

    2024年01月17日
    浏览(93)
  • 数据结构---手撕图解单链表---phead的多种传参方式对比和辅助理解

    前面我们知道了顺序表,当顺序表的容量到达上限后就需要申请新的空间,而申请新空间就会遇到一些问题 1.当利用realloc函数进行申请新空间时,会涉及到开辟新空间–拷贝原有数据–释放原空间这三个步骤,而这三个步骤会有不小的损耗 2.增容一般是2倍的增长,势必会有

    2024年02月17日
    浏览(49)
  • 数据结构:手撕图解单链表---phead的多种传参方式对比和辅助理解

    前面我们知道了顺序表,当顺序表的容量到达上限后就需要申请新的空间,而申请新空间就会遇到一些问题 1.当利用realloc函数进行申请新空间时,会涉及到开辟新空间–拷贝原有数据–释放原空间这三个步骤,而这三个步骤会有不小的损耗 2.增容一般是2倍的增长,势必会有

    2024年02月15日
    浏览(43)
  • 【手撕数据结构】(三)顺序表和链表

    🎗️线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 🎗️线性表在逻辑上是线性结构,也就说是一条连续的直线。但是在物理结构上并不一定是连续的,线性表在物理上存储

    2024年02月05日
    浏览(50)
  • 【数据结构与算法】手撕链表OJ题

    给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 思路一 :一种比较普遍的方式,边遍历边找不同。我们可以通过定义两个指针,一个指向头节点,一个置为NULL。当遇到值为相同的时候,直接跳过去。指向下一位

    2024年02月10日
    浏览(40)
  • 数据结构之手撕链表(讲解➕源代码)

    我们在学习过顺序表之后,会发现两点不是很优秀的操作: 1.顺序表的 头插和中间的插入,头删和中间的删除:          需要不断的覆盖数据,时间复杂度是O(n),当我们的顺序表存入100w个数据的时候,花费的时间是非常之多的。 2. 动态开辟空间:         a. 一般动态

    2024年02月08日
    浏览(37)
  • 【数据结构】- 链表之单链表(下)

    未来藏在迷雾中 叫人看来胆怯 带你踏足其中 就会云开雾散 本章是关于数据结构中的链表之单链表(下) 提示:以下是本篇文章正文内容,下面案例可供参考 1.2.1 在pos位置插入(也就是pos位置之前) 流程图 多个节点 一个节点 1.2.2 在pos位置之后插入 流程图: 注意: 下面这种写

    2023年04月23日
    浏览(60)
  • [数据结构]链表之单链表(详解)

    在学习 链表 之前,我们已经学习了 顺序表 了 根据 顺序表 的特点,我们可以发现 顺序表 有优点,也有一些缺陷。 所以根据 顺序表 的缺点,链表就横空出世啦~ **概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次

    2023年04月08日
    浏览(53)
  • 数据结构入门 — 链表详解_单链表

    数据结构入门 — 单链表详解 * 博客主页链接:https://blog.csdn.net/m0_74014525 关注博主,后期持续更新系列文章 文章末尾有源码 *****感谢观看,希望对你有所帮助***** 第一篇:数据结构入门 — 链表详解_单链表 第二篇:数据结构入门 — 链表详解_双向链表 第三篇:数据结构入门

    2024年02月11日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包