<数据结构> 链表 - 链表的概念及结构

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

1、 链表的概念

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

1、链表由一系列结点(链表中每一个元素称为结点)组成。

2、结点可以在运行时动态(malloc)生成。

3、每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域(详见1.2 节点部分)。

4、相比于线性表顺序结构,链表操作复杂。但是由于不需按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比顺序表快得多;但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表只需O(1)

2、 结点

链表由一个个结点构成,每个结点采用结构体的形式。结构体内前面的变量按照需要给予,最后一个变量是这个结构体类型的指针,用来存放下一节点的首地址‘

链表结点分为两个
数据域 :存放各种实际的数据
指针域 :存放下一结点的地址
<数据结构> 链表 - 链表的概念及结构(图为带哨兵位头结点的链表)

3、 链表的使用场景

线性表在 需要经常插入或删除数据元素 的情况下适合采用链式存储结构。

因为对于链表来说,插入或删除数据只需要创建一个结点、输入数据、修改指针把该结点连接到链表中的某一位置即可; 而对于顺序表,插入一个数据可能需要搬移其他数据,复杂度高。

4、 链表分类 和 常用的结构

<数据结构> 链表 - 链表的概念及结构各种链表的结构:
<数据结构> 链表 - 链表的概念及结构
虽然组合起来一共有8种链表可以选择,但是实际中最常用的主要还是 无头单向非循环 链表和 带头双向循环 链表。

1、无头单向非循环链表:俗称 “单链表”。结构简单,一般不会单独用来存储数据。实际上更多是作为其他数据结构的子结构(如哈希桶、图的邻接表、栈的链式结构等)

2、带头双向循环链表结构最复杂,一般用来单独存储数据。实际使用的链表,大多都是带头双向循环链表。虽然结构最复杂,但是这种结构会带来很多优势。

5、 与顺序表的比较

链表: 链表是通过结点把离散的数据链接成一个表,通过对结点的插入、删除操作从而实现对数据的存取。

顺序表: 顺序表是通过开辟一段连续的内存(直接使用 数组 或者 malloc后realloc扩容)来存储数据。

但是由于 realloc 扩容分为原地扩容和异地扩容,前者代价较低,而后者扩容时不仅需要拷贝数据,还要释放旧空间。再者,扩容时一般会扩到原来容量的2倍,扩容次数多了就容易造成空间的浪费

顺序表的每个成员对应链表的结点;成员和结点的数据类型可以是标准的c类型或者是用户自定义的结构体类型。文章来源地址https://www.toymoban.com/news/detail-406557.html

比较对象 顺序表 链表
存储空间 连续 不连续
插入或删除数据 可能要搬移数据,复杂度O(n) 只需修改指针
push 动态顺序表:空间不够了需要扩容 没有“容量”的概念,push时直接malloc新的结点
应用 需要频繁访问 需要频繁插入、删除数据

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

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

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

相关文章

  • 数据结构:栈的概念及栈的实现

    目录 1.栈的概念及结构 2.栈的实现  2.1  初始化栈 2.2 入栈  2.3 出栈  2.4 获取栈顶元素 2.5 获取栈中有效元素个数   2.6  检测栈是否为空,如果为空返回非零结果,如果不为空返回0 2.7 销毁栈  3. 完整代码 test.c  Stack.h Stack.c   栈(后进先出,先进后出) : 一种 特殊

    2024年02月01日
    浏览(41)
  • 数据结构 栈的概念及栈的实现

    目录 1.栈的概念及结构 2.栈的实现  2.1  初始化栈 2.2 入栈  2.3 出栈  2.4 获取栈顶元素 2.5 获取栈中有效元素个数   2.6  检测栈是否为空,如果为空返回非零结果,如果不为空返回0 2.7 销毁栈  3. 完整代码 test.c  Stack.h Stack.c   栈(后进先出,先进后出) : 一种 特殊

    2024年01月21日
    浏览(48)
  • 爱上数据结构:栈和队列的概念及使用

    ​ ​ 🔥个人主页 : guoguoqiang. 🔥 专栏 : 数据结构 ​ 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。 压栈:栈的插入操作

    2024年04月16日
    浏览(30)
  • 数据结构从入门到精通——排序的概念及运用

    排序是将数据按照一定规则重新排列的过程,常见规则有升序、降序等。排序算法如冒泡排序、快速排序等,广泛用于数据库、搜索引擎等场景,提高数据检索效率。此外,排序也应用于统计分析、机器学习等领域,以获取有序数据集或发现数据间的关联。 排序是一种将一组

    2024年03月21日
    浏览(40)
  • 数据结构 | 二叉树的概念及前中后序遍历

    下面内容来自百度百科 二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个节点最多只能

    2024年02月05日
    浏览(37)
  • 数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用

    普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用 顺序结构的数组来存储 ,需要注意的是 这里的堆和操作系统虚拟进程地址空间中的堆是两回事 ,一个是 数据结构 ,一

    2023年04月19日
    浏览(52)
  • 【数据结构】手撕排序(排序的概念及意义、直接插入和希尔排序的实现及分析)

    目录 一、排序的概念及其运用  1.1排序的概念  1.2排序运用 1.3 常见的排序算法  二、插入排序 2.1基本思想:  2.2直接插入排序:  2.3步骤: 2.4直接插入排序的实现 三、希尔排序( 缩小增量排序 )  3.1希尔排序的发展历史 3.2 希尔排序的思路 ​编辑 gap = 3的思路讲解 3.3 如何

    2024年02月03日
    浏览(48)
  • 数据结构(C语言实现)——二叉树的概念及二叉树顺序结构和链式结构的实现(堆排序+TOP-K问题+链式二叉树相关操作)

    前面学习了数据结构中线性结构的几种结构,顺序表,链表,栈和队列等,今天我们来学习一种非线性的数据结构——树。由于二叉树是数据结构中的一个重点和难点,所以本文着重介绍二叉树的相关概念和性质,以及二叉树的应用。 树是一种非线性的数据结构,它是由n(

    2023年04月21日
    浏览(44)
  • 【数据结构】反转链表、链表的中间节点、链表的回文结构(单链表OJ题)

    正如标题所说,本文会图文详细解析三道单链表OJ题,分别为:  反转链表 (简单)  链表的中间节点 (简单)  链表的回文结构 (较难) 把他们放在一起讲的原因是:  反转链表 和  链表的中间节点 是  链表的回文结构 的基础 为什么这样说?请往下看: 目录 1. 反转链

    2024年02月13日
    浏览(72)
  • 【数据结构】链表的回文结构

    单链表的操作算法是笔试面试中较为常见的题目。 本文将着重介绍平时面试中常见的关于链表的应用题目,马上要进行秋招了。希望对你们有帮助 _ 😀 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。 给定一个链表的头指针

    2024年02月12日
    浏览(54)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包