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

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

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

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模板网!

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

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

相关文章

  • 【数据结构】链表详解

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

    2024年02月03日
    浏览(41)
  • [数据结构]——链表详解

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

    2024年02月09日
    浏览(37)
  • 数据结构——链表详解

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

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

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

    2023年04月19日
    浏览(42)
  • 数据结构:链表(Python语言实现)

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

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

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

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

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

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

            机遇对于有准备的头脑有特别的亲和力。本章将讲写到链表其中主要将写到单链表和带头双向循环链表的如何实现。    话不多说安全带系好,发车啦 (建议电脑观看) 。 附:红色,部分为重点部分;蓝颜色为需要记忆的部分(不是死记硬背哈,多敲);黑色加粗

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

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

    2024年02月02日
    浏览(42)
  • 双向链表(数据结构)(C语言)

    目录 概念 带头双向循环链表的实现 前情提示 双向链表的结构体定义 双向链表的初始化 关于无头单向非循环链表无需初始化函数,顺序表、带头双向循环链表需要的思考 双向链表在pos位置之前插入x 双向链表的打印 双链表删除pos位置的结点 双向链表的尾插 关于单链表的尾

    2024年02月04日
    浏览(62)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包