【数据结构】详解链表结构

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

引言

上篇博客已经介绍了顺序表的实现:【数据结构】详解顺序表。最后在里面也谈及了顺序表结构的缺陷,即效率低,空间浪费等等问题,那么为了解决这些问题,于是乎我们引入了链表的概念,下面将对链表结构进行讲解

一、链表的介绍

首先肯定会问,到底什么是链表?链表的概念链表是一种物理存储结构上非连续,非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的
在结构上其与火车的结构相似,分为一个个节点,再将每个节点连接起来,就形成了一个链表,其大致结构如下:
【数据结构】详解链表结构,数据结构和算法,数据结构,链表
但还要几点需要注意

  1. 链式结构在逻辑上是连续的,但在物理空间上不一定是连续的
  2. 这些节点一般是在堆上申请出来的,即使用malloc函数来动态申请空间;
  3. 每当需要增加一个数据时,便可申请一段空间,空间可能连续也可能不连续。

二、链表的几种分类

链表的结构大致可以分为8类,即:带头/不带头单向链表,带头/不带头双向链表,带头/不带头单向循环链表,带头/不带头双向循环链表。 今天我所介绍的是其中最简单的结构和最复杂的结构:

  1. 单向不带头不循环链表:
    【数据结构】详解链表结构,数据结构和算法,数据结构,链表
    单向不带头不循环链表结构简单,但实现起来并不简单且复杂度高,所以一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  2. 双向带头循环链表:
    【数据结构】详解链表结构,数据结构和算法,数据结构,链表
    带头双向循环链表结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。表面上看这结构十分的复杂,但在后面实现函数时会发现这种结构会带来很多优势,实现起来反而更简单了,复杂度也大大降低

三、不带头单链表的一些常用接口

定义如下结构体,表示链表的一个节点:

typedef int SLDataType;

typedef struct SlistNode
{
    SLDataType val;//所需保存的数据
    struct SListNode* next;//结构体指针,指向下一个节点的地址
}SLNode;

3.1 动态申请一个节点

为了使链表在各个函数中都可以使用,所以我们需要动态开辟内存来创建节点,再通过指针将他们相连接。在CreatNode()函数中我们创建节点并将他们初始化:

//动态申请节点
SLNode* CreatNode(SLTDateType x)
{
    SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
    //检测
    if(newnode == NULL)
    {
        perror("CreatNode()::malloc");
        return;
    }
    newnode->val = x;
    newnode->next = NULL;
    return newnode;
}

3.2 尾插数据

根据一般逻辑,我们想要尾插那就要先创建新节点并找到尾节点。那么我们定义指针tail,然后利用循环找尾节点再链接新节点tail->next = newnode,另外还要额外判断链表为空的情况,此情况直接尾插即可,具体如下:

//尾插
void SLPushBack(SLNode** pplist, SLDateType x)
{
	SLNode* newnode = CreatNode(x);
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
	    //找尾
		SLNode* tail = *pplist;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
        //链接
		tail->next = newnode;
	}
}

3.3 头插数据

头插就比较简单了,只需要注意一点:不额外定义变量时,要先将新节点链到链表,即newnode->next = *pplist然后再改头节点,即*pplist = newnode,如下:

void SLPushFront(SLNode** pplist, SLDateType x)
{
	assert(pplist);
	SLNode* newnode = CreatNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}

3.4 尾删数据

同样想要尾删,那就必须先找到尾节点然后释放空间。但释放完空间后,上一个节点的next仍然指向释放空间的地址,这就可能造成越界访问,野指针问题。所以我们还需要记录尾节点的上一个节点tailPrev,然后通过这个指针将此节点next置为NULL。此外还需用assert()检测链表不为NULL分类讨论链表只有一个节点和有多个节点的情况。如下:

//尾删
void SLPopBack(SLNode** pplist)
{
    assert(pplist && *pplist);
	SLNode* tailPrev = NULL;
	SLNode* tail = *pplist;
	// 1.只有一个节点
	if (tail->next == NULL)
	{
		free(tail);
		*pplist = NULL;
	}
	// 2.两个及以上的节点
	else
	{
	    //找尾及上一个节点
		while (tail->next)
		{
			tailPrev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		tailPrev->next = NULL;
	}
}

3.5 头删数据

头删数据时,链表同样不能为空,另外头删无需判断链表节点数问题,这就比较容易实现了:

void SLPopFront(SLNode** pplist)
{
    //不为空
    assert(pplist && *pplist);
    //记录第一个节点
    SLNode* first= *pplist;
    *pplist = (*pplist)->next;
    free(first);
}

3.6 查找数据

给定一个val,再链表中向后寻找,找到时返回此节点地址pos,未找到返回NULL。我们只需定义一个结构体指针SLNode* cur = plist;,让他向后走,找到val时返回cur,直到cur = NULL时循环结束并返回NULL。因为这里无需改变链表指向,所以可以直接传一级指针。

SLNode* SLFind(SLNode* plist, SLDateType x)
{
	SLNode* cur = plist;
	while (cur)
	{
	    //寻找val
		if (cur->val == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

3.7 pos位置后插入数据

如下图,先创建一个节点newnode,然后将newnode->next指向pos位置的下一个节点,最后将pos->next指向新节点。
【数据结构】详解链表结构,数据结构和算法,数据结构,链表
当然pos != NULL

//指定位置插入
void SLInsertAfter(SLNode* pos, SLDataType x)
{
    assert(pos);
    SLNode* newnode = CreatNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

3.8 删除pos位置数据

先通过循环找到pos前一个节点地址posPrev,和后一个节点地址posNext,然后释放pos节点,链接posPrevposNext
【数据结构】详解链表结构,数据结构和算法,数据结构,链表
同样pos != NULL,还有一点是当pos为头节点,就相当于头删,但无需判断,同样适用。

void SLErase(SLNode* pos, SLNode** pplist)
{
    assert(pos && pplist);
    SLNode* posPrev = *pplist, *posNext = pos->next, *cur = *pplist;
    //找pos前一个节点
    while(cur != pos)
    {
        posPrev = cur;
        cur = cur->next;
    }
    //链接
    posPrev->next = posNext;
    free(pos);
}

3.9 释放空间

因为这是一个链式结构,且每个节点是malloc动态开辟的,所以最后要将所以节点释放,否则会造成内存泄漏问题。只需定义一个结构体指针SLNode* cur = *pplist,让他向后依次释放节点,直到cur = NULL

void SLDestroy(SLNode** pplist)
{
    assert(pplist);
    SLNode* cur = *pplist;
    while(cur)
    {
        //记录下一个节点
        SLNode* next = cur->next;
        free(cur);
        cur = next;
    }
}

四、带头双向链表的常见接口

通过上面对单向不循环链表的介绍,我们不难发现其实单链表的尾插,尾删和指定位置删除其实效率是不高的,时间复杂度为O(n)。而双向带头循环链表是不存在这个问题的,且因为链表带头节点的原因,在函数传参是无需用到二级指针,在实现函数时也会发现很多时候也不需要单独判断链表没节点的情况,因为头节点本身就是一个节点,这也大大降低了代码的难度
双向带头循环链表的每个节点都包含两个指针:一个指向上一个节点,一个指向下一个节点。那么便可这样设计节点:

typedef int DataType;
//节点设计
typedef struct DListNode
{
	DataType val;
	struct DListNode* _prev;//指向上一个节点的指针
	struct DListNode* _next;//指向下一个节点的指针
}DLNode;

4.1创建头节点(初始化)

头节点和其他节点的结构是相同的,就相当于链表自带一个节点,并将此节点初始化成以下格式:
【数据结构】详解链表结构,数据结构和算法,数据结构,链表

DLNode* InitDLNode(DLNode* phead)
{
    //创建
    DLNode* head = (DLNode*)malloc(sizeof(DLNode));
	if (head == NULL)
	{
		perror("InitDLNode()::malloc");
		return;
	}
	//形成循环结构
	head->_prev = head;
	head->_next = head;
	head->val = -1;
	return head;
}

4.2pos位置前插入

对于pos位置之前插入,可以先通过pos->_prev找到前一个节点的地址,然后再进行插入操作。因为是双向循环链表的原因,找pos前一个节点也不需要循环,时间复杂度只有O(1)
【数据结构】详解链表结构,数据结构和算法,数据结构,链表
事实上当链表无有效节点(即只有头节点)也不需要单独判断,这样降低了代码难度,具体实现代码如下:

//指定位置插入
void DLNodeInsert(DLNode* pos, DataType x)
{
	assert(pos);
	DLNode* posPrev = pos->_prev;//pos前一个节点
	DLNode* newnode = CreatNode(x);//创建新节点
	//链接
	posPrev->_next = newnode;
	newnode->_prev = posPrev;
	pos->_prev = newnode;
	newnode->_next = pos;
}

4.3删除pos位置数据

删除pos位置的数据,我们可以通过pos->_prev找到上一个节点的地址,再通过pos->_next找到下一个节点的地址。然后将这两个节点链接起来,并释放pos节点,如下:
【数据结构】详解链表结构,数据结构和算法,数据结构,链表
当只有一个头节点时我们还需额外判断一下,代码如下:

void DLNodeErase(DLNode* pos)
{
	assert(pos);
	assert(pos->_next != pos);//不能为头节点
	DLNode* posPrev = pos->_prev, * posNext = pos->_next;
	//链接
	posPrev->_next = posNext;
	posNext->_prev = posPrev;
	free(pos);
}

4.4其他

还有头删/插,尾删/插这四个函数,但这四个函数并不需要额外实现,因为:
头插/删可以当作pos = phead->_next的指定位置插入/删除,尾删也可以当作pos = phead->_prev的指定位置删除,尾插则是pos = phead的位置。头/尾删这两个pos分别代表头节点的后一个和前一个,且判断assert(phead != phead->_next)也是必要的,这里就不代码实现了。


五、总结

对比于顺序表我们发现链表有很多优点,也有一些缺点:
优点:

  1. 链表的空间浪费较小,按需开辟空间;
  2. 任意位置插入和删除数据效率更高,实现了O(1)时间复杂度;

缺点:文章来源地址https://www.toymoban.com/news/detail-751987.html

  1. 不支持随机访问数据(致命缺陷);
  2. 每个节点还要存储链接下一个节点的指针,这也会造成一点空间浪费;

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

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

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

相关文章

  • 【数据结构与算法】链表

    对于顺序表存在一些缺陷: 中间/头部的插入删除,时间复杂度为O(N) 。头部插入需要挪动后面的元素 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插

    2023年04月09日
    浏览(48)
  • 【数据结构】链表 详解

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

    2023年04月19日
    浏览(41)
  • 【数据结构】链表详解

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

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

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

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

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

    2024年02月09日
    浏览(37)
  • 02-链表 (数据结构和算法)

    3.1 链表的基本概念 前面我们在学习顺序表时,线性表的顺序存储结构的特点是逻辑关系上相邻的两个数据元素在物理位置上也是相邻的。我们会发现虽然顺序表的查询很快,时间复杂度为O(1),但是增删的效率是比较低的,因为每一次增删操作都伴随着大量的数据元素移动。为

    2024年02月16日
    浏览(46)
  • Python数据结构与算法-数据结构(列表、栈、队列、链表)

    数据结构是指相互之间存在这一种或者多种关系的数据元素的集合和该集合中元素之间的关系组成。 简单来说,数据结构就是设计数据以何种方式组织并存储在计算机中。 比如:列表、集合与字典等都是一种数据结构。 N.Wirth:“程序=数据结构+算法” 数据结构按照其 逻辑结

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

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

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

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

    2024年03月26日
    浏览(65)
  • 数据结构与算法:双向链表

    朋友们大家好啊,在上节完成单链表的讲解后,我们本篇文章来对 带头循环双向链表进行讲解 单链表中,一个节点存储数据和指向下一个节点的指针,而双向链表除了上述两个内容,还包括了 指向上一个节点的指针 带头的双向链表,是指在双向链表的最前端添加了一个 额

    2024年02月20日
    浏览(51)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包