搜索
首页Javajava教程Java数据结构之链表的概念及结构是什么

1、 链表的概念

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

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

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

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

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

2、 结点

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

链表结点分为两个域
数据域 :存放各种实际的数据
指针域 :存放下一结点的地址

Java数据结构之链表的概念及结构是什么

(图为带哨兵位头结点的链表)

3、 链表的使用场景

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

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

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

Java数据结构之链表的概念及结构是什么

Java数据结构之链表的概念及结构是什么

虽然组合起来一共有8种链表可以选择,但是实际中最常用的主要还是 无头单向非循环 链表和 带头双向循环 链表。

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

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

5、 与顺序表的比较

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

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

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

顺序表的每个成员对应链表的结点;成员和结点的数据类型可以是标准的c类型或者是用户自定义的结构体类型。

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

以上是Java数据结构之链表的概念及结构是什么的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文转载于:亿速云。如有侵权,请联系admin@php.cn删除
带你搞懂Java结构化数据处理开源库SPL带你搞懂Java结构化数据处理开源库SPLMay 24, 2022 pm 01:34 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于结构化数据处理开源库SPL的相关问题,下面就一起来看一下java下理想的结构化数据处理类库,希望对大家有帮助。

Java集合框架之PriorityQueue优先级队列Java集合框架之PriorityQueue优先级队列Jun 09, 2022 am 11:47 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于PriorityQueue优先级队列的相关知识,Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,下面一起来看一下,希望对大家有帮助。

完全掌握Java锁(图文解析)完全掌握Java锁(图文解析)Jun 14, 2022 am 11:47 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于java锁的相关问题,包括了独占锁、悲观锁、乐观锁、共享锁等等内容,下面一起来看一下,希望对大家有帮助。

一起聊聊Java多线程之线程安全问题一起聊聊Java多线程之线程安全问题Apr 21, 2022 pm 06:17 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于多线程的相关问题,包括了线程安装、线程加锁与线程不安全的原因、线程安全的标准类等等内容,希望对大家有帮助。

Java基础归纳之枚举Java基础归纳之枚举May 26, 2022 am 11:50 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于枚举的相关问题,包括了枚举的基本操作、集合类对枚举的支持等等内容,下面一起来看一下,希望对大家有帮助。

详细解析Java的this和super关键字详细解析Java的this和super关键字Apr 30, 2022 am 09:00 AM

本篇文章给大家带来了关于Java的相关知识,其中主要介绍了关于关键字中this和super的相关问题,以及他们的一些区别,下面一起来看一下,希望对大家有帮助。

Java数据结构之AVL树详解Java数据结构之AVL树详解Jun 01, 2022 am 11:39 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于平衡二叉树(AVL树)的相关知识,AVL树本质上是带了平衡功能的二叉查找树,下面一起来看一下,希望对大家有帮助。

一文掌握Java8新特性Stream流的概念和使用一文掌握Java8新特性Stream流的概念和使用Jun 23, 2022 pm 12:03 PM

本篇文章给大家带来了关于Java的相关知识,其中主要整理了Stream流的概念和使用的相关问题,包括了Stream流的概念、Stream流的获取、Stream流的常用方法等等内容,下面一起来看一下,希望对大家有帮助。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
3 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

Dreamweaver Mac版

Dreamweaver Mac版

视觉化网页开发工具

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序,非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具,帮助Web开发人员更好地理解保护Web应用程序的过程,并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞,难度各不相同。请注意,该软件中

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

EditPlus 中文破解版

EditPlus 中文破解版

体积小,语法高亮,不支持代码提示功能

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版