[数据结构]——链表详解

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

[数据结构]——链表详解

1.什么是链表?链表的概念及结构

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

链表,链表,数据结构,c语言,学习

注意:

1.链式结构在逻辑上是连续的,但在物理上不一定连续

2.现实中的结点一般都是从堆上申请出来的

3.从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续

2.链表的分类

实际中链表的结构非常多样,以下的情况组合起来就有8种链表结构

1.单向或者双向

链表,链表,数据结构,c语言,学习

2.带头或者不带头

链表,链表,数据结构,c语言,学习

3.循环或者非循环

链表,链表,数据结构,c语言,学习

虽然有这么多的链表的结构,但是我们实际中最常用的还是两种结构

1.无头单向非循环链表

链表,链表,数据结构,c语言,学习

2.带头双向循环链表

链表,链表,数据结构,c语言,学习

  1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。

3.单链表的实现(增删查改)

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SListNodeType;
typedef struct SListNode
{
	SListNodeType data;
	SListNodeType* next;
}SLNode;

void SLNodePrint(SLNode* phead);

SLNode* BuySLNode(SListNodeType x);

void SLNodePushFront(SLNode* pphead, SListNodeType x);

void SLNodePushBack(SLNode** pphead, SListNodeType x);

void SLNodePopBack(SLNode** pphead);

void SLNodePopFront(SLNode** pphead);

void SListDestory(SLNode** pphead);

SLNode* SListFind(SLNode* phead, SListNodeType x);

void SListInsert(SLNode** pphead, SLNode* pos, SListNodeType x);

void SListInsertAfter(SLNode* pos, SListNodeType x);
1)链表的初始化
void SLNodeInit(SLNode* phead)
{
    phead->data=0;
    phead->next=NULL;
}
2)动态申请一个结点
//新创建一个结构体空间,存放新输入的数据
SLNode* BuySLNode(SListNodeType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
3)单链表尾插
//在链表最后端插入一个数据
void SLNodePushBack(SLNode** pphead, SListNodeType x)
{
	SLNode* newnode = BuySLNode(x);
	/*1.整个链表为空*/
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	/*2.链表不为空*/
	else
	{
		SLNode* cur = *pphead;
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		newnode = cur->next;
	}
}
4)单链表头插
//在链表最前端插入一个数据
void SLNodePushFront(SLNode** pphead, SListNodeType x)
{
	assert(pphead);
	SLNode* newnode=BuySLNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
5)单链表尾删
//删除链表最后端的数据
void SLNodePopBack(SLNode** pphead)
{
	/*1.链表为空*/
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	/*2.链表不为空*/
	else
	{
		SLNode* cur = *pphead;
		SLNode* prev = NULL;
		while (cur->next != NULL)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = NULL;
		free(cur);
		cur = NULL;
	}
}
6)单链表头删
//删除链表最前端的数据
void SLNodePopFront(SLNode** pphead)
{
	assert(pphead);
	SLNode* det = *pphead;
	*pphead = (*pphead)->next;
	free(det);
	det = NULL;
}
7)单链表查找
//在链表中查找某个数据
SLNode* SListFind(SLNode* phead, SListNodeType x)
{
	SLNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
8)在单链表中某个位置前插入数据
//在pos前插入一个数据
void SListInsert(SLNode** pphead, SLNode* pos, SListNodeType x)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLNodePushFront(*pphead, x);
	}
	else
	{
		SLNode* cur = *pphead;
		SLNode* newnode = BuySLNode(x);
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next=newnode;
		newnode->next = pos;
	}

9)在单链表中某个位置后插入数据
// 在pos后面插入
void SListInsertAfter(SLNode* pos, SListNodeType x)
{
	assert(pos);
	SLNode* newnode = BuySLNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
10)销毁单链表
void SListDestory(SLNode** pphead)
{
	assert(pphead);
	SLNode* cur = *pphead;
	while (cur != NULL)
	{
		SLNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

4.双向链表的实现

双向链表的原理与单链表类似,双向链表需要两个指针来链接,一个指向前面的,一个指向后面的。同时需要一个head,头链表,方便操作。
链表,链表,数据结构,c语言,学习文章来源地址https://www.toymoban.com/news/detail-709350.html

#pragma once
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}ListNode;

ListNode* ListInit();

ListNode* BuyListNode(LTDataType x);

void ListPushBack(ListNode* phead, LTDataType x);

void ListPushFront(ListNode* phead, LTDataType x);

void ListNodePopBack(ListNode* phead);

void ListNodePopFront(ListNode* phead);

bool ListNodeEmpty(ListNode* phead);

size_t ListNodeSize(ListNode* phead);

void ListNodeInsert(ListNode* pos, LTDataType x);

ListNode* ListNodeFInd(ListNode* phead, LTDataType x);

void ListNodeErase(ListNode* pos);

void ListNodeDestory(ListNode* phead);
1)双向链表的初始化
ListNode* ListInit()
{
	ListNode* Guard=(ListNode*)malloc(sizeof(ListNode));
	if (Guard == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	Guard->next = Guard;
	Guard->prev = Guard;
	return Guard;
}
2)动态申请一个结点
ListNode* BuyListNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
3)双向链表的尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	ListNode* tail = phead->prev;

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
4)双向链表的头插
void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	ListNode* cur = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = cur;
	cur->prev= newnode;
}
5)双向链表的尾删
void ListNodePopBack(ListNode* phead)
{
	assert(phead);
	assert(!ListNodeEmpty(phead));
	ListNode* tail = phead->prev;
	ListNode* cur = tail->prev;
	cur->next = phead;
	phead -> prev = cur;
	free(tail);
	tail = NULL;
}
6)双向链表的头删
void ListNodePopFront(ListNode* phead)
{
	assert(phead);
	assert(!ListNodeEmpty(phead));
	ListNode* cur = phead->next;
	ListNode* pe = cur->next;
	phead->next = pe;
	pe->prev = phead;
	free(cur);
	cur = NULL;
}
7)判断链表是否为空
bool ListNodeEmpty(ListNode* phead)
{
	assert(phead);
	return phead->next==phead;
}
8)双向链表数据的个数
size_t ListNodeSize(ListNode* phead)
{
	size_t n = 0;
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		++n;
		cur = cur->next;
	}
	return n;
}
9)在双向链表查找数据
ListNode* ListNodeFInd(ListNode* phead, LTDataType x)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
10)在双向链表中插入一个数据
void ListNodeInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* newnode = BuyListNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
11)在双向链表中删除一个数据
void ListNodeErase(ListNode* pos)
{
	assert(pos);

	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;
}
12)销毁双向链表
void ListNodeDestory(ListNode* phead)
{
	assert(phead);

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

5.顺序表与链表的区别

不同点 顺序表 链表
存储空间上 物理上一定连续 逻辑上连续,但物理上不一定连续
随机访问 支持O(1) 不支持:O(N)
任意位置插入或者删除元素 可能需要搬移元素,效率低O(N) 只需要修改指针指向
插入 动态顺序表,空间不够时需要扩容 没有容量概念
应用场景 元素高效存储+频繁访问 任意位置的插入和删除
缓存利用率

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

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

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

相关文章

  • [数据结构]——链表详解

    1.什么是链表?链表的概念及结构 链表是一种 物理存储结构上非连续、非顺序 的存储结构,数据元素的 逻辑顺序 是通过链表中的 指针链接 次序实现的。 注意: 1.链式结构在逻辑上是连续的,但在物理上不一定连续 2.现实中的结点一般都是从堆上申请出来的 3.从堆上申请的

    2024年02月09日
    浏览(35)
  • 【数据结构】链表 详解

    我们不废话,直入正题。 什么是链表? 来看看百度怎么说: 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包

    2023年04月19日
    浏览(35)
  • 数据结构——链表详解

    new一个奶黄包:没关系,这条路我陪你走到底 单链表结构图 带头单循环链表结构图 双向循环链表结构图 带头双向循环链表结构图 链表特点 单链表在内存中,并不是连续存储的(逻辑上连续)。 不支持随机访问 插入时只需要改变指针指向 没有容量的概念 可以高效的在任意

    2024年02月12日
    浏览(35)
  • 【数据结构】链表详解

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:数据结构 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 在前面我们已经学习过了有关顺序表的知识,但是我们知道顺序表是存在着一些问题的 问题: 中间/头部的插入删除,时间复杂度

    2024年02月03日
    浏览(39)
  • 数据结构:链表(Python语言实现)

    链表分为单链表、双链表、循环单链表和循环双链表。 本文以单链表为例,用python创建一个单链表数据结构,同时定义链表节点的增加、删除、查询和打印操作。 创建一个名为Node的节点类,节点类里面包含2个属性和1个方法。 分别为data数据域属性和next指针域属性。 has_va

    2024年02月16日
    浏览(52)
  • 数据结构入门 — 链表详解_双向链表

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

    2024年02月11日
    浏览(47)
  • 数据结构:详解【链表】的实现(单向链表+双向链表)

    1.顺序表的问题和思考 问题: 中间/头部的插入删除,时间复杂度为O(N)。 增容需要申请新空间,拷贝数据,释放旧空间,会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据

    2024年03月26日
    浏览(64)
  • C语言数据结构之链表

    在上一篇博客中我们提到,线性表包括顺序表和链表,顺序表在上篇博客中已经介绍,本篇博客介绍一下另一种线性表—— 链表 。 概念:链表是⼀种 物理存储结构上⾮连续、⾮顺序 的存储结构,数据元素的 逻辑顺序是通过链表中的指针链接次序实现的 。 链表的结构跟⽕

    2024年04月22日
    浏览(44)
  • C语言数据结构-双向链表

    带头链表的头结点,实际是\\\"哨兵位\\\",哨兵位节点不存储任何有效元素,只是站在这里\\\"放哨的\\\". 哨兵位的意义:遍历循环链表避免死循环. 笔者在删除,插入数据时,画好图后,也好了代码,但是在调试中多次出现 代码位置出错 ,导致写的代码的含义不符合预期. 所以说思路一定要清晰

    2024年02月04日
    浏览(48)
  • C语言实现链表--数据结构

    魔王的介绍:😶‍🌫️一名双非本科大一小白。 魔王的目标:🤯努力赶上周围卷王的脚步。 魔王的主页:🔥🔥🔥大魔王.🔥🔥🔥 ❤️‍🔥大魔王与你分享:很喜欢宫崎骏说的一句话:“不要轻易去依赖一个人,它会成为你的习惯当分别来临,你失去的不是某个人而是你精

    2024年02月02日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包