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类型或者是用户自定义的结构体类型。
比较对象 | 顺序表 | 链表 |
---|---|---|
存储空间 | 连续 | 不连续 |
插入或删除数据 | 可能要搬移数据,复杂度O(n) | 只需修改指针 |
push | 动态顺序表:空间不够了需要扩容 | 没有“容量”的概念,push时直接malloc新的结点 |
应用 | 需要频繁访问 | 需要频繁插入、删除数据 |
以上是Java数据结构之链表的概念及结构是什么的详细内容。更多信息请关注PHP中文网其他相关文章!

本文讨论了使用Maven和Gradle进行Java项目管理,构建自动化和依赖性解决方案,以比较其方法和优化策略。

本文使用Maven和Gradle之类的工具讨论了具有适当的版本控制和依赖关系管理的自定义Java库(JAR文件)的创建和使用。

本文讨论了使用咖啡因和Guava缓存在Java中实施多层缓存以提高应用程序性能。它涵盖设置,集成和绩效优势,以及配置和驱逐政策管理最佳PRA

本文讨论了使用JPA进行对象相关映射,并具有高级功能,例如缓存和懒惰加载。它涵盖了设置,实体映射和优化性能的最佳实践,同时突出潜在的陷阱。[159个字符]

Java的类上载涉及使用带有引导,扩展程序和应用程序类负载器的分层系统加载,链接和初始化类。父代授权模型确保首先加载核心类别,从而影响自定义类LOA


热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

EditPlus 中文破解版
体积小,语法高亮,不支持代码提示功能

WebStorm Mac版
好用的JavaScript开发工具

安全考试浏览器
Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。

SublimeText3 英文版
推荐:为Win版本,支持代码提示!

禅工作室 13.0.1
功能强大的PHP集成开发环境