java学习笔记(6)——数据结构

先进后出

入:压栈

出:弹栈

队列

先进先出

入口和出口在两侧

java学习笔记(6)——数据结构

数组

查询快:地址连续,通过首地址与索引可以快速查找某个元素

增删慢:长度不变,增加/删除必须创建新数组,再把源数组复制过来,再把源数组的地址赋给新数组,源数组就会自动销毁

链表

查询慢:链表中 地址不连续 ,每次查询元素都必须 从头开始查询

增删快:链表结构,增加/删除一个元素,对链表的整体结构没有影响

链表总的每一个元素也称为一个 节点

一个节点包含了 一个数据 (存储数组), 两个指针域 (存储地址)

一个节点:

java学习笔记(6)——数据结构

单向链表:

链表中只有一条链子,不能保证元素的顺序(存储元素和取出元素的顺序有可能不一致)

无序

java学习笔记(6)——数据结构

双向链表:

链表中有两条链子,有一条链子是专门记录元素的顺序,是一个有序的集合

下一个节点记住上一个节点的地址,上一个节点也记住上一个节点的地址

有序

java学习笔记(6)——数据结构

计算机的树(倒着)

java学习笔记(6)——数据结构

二叉树:

分支不能超过两个

java学习笔记(6)——数据结构

排序树/查找树:

在二叉树的基础上,元素的是有大小顺序的

左子树小,右子树大

java学习笔记(6)——数据结构

平衡树:

左孩子数量和右孩子数量相等

不平衡树:

左孩子数量 != 右孩子数量

红黑树

特点:

趋于平衡式, 查询速度非常的快 ,查询叶子节点最大次数和最小次数不能超过2倍。

约束:

1.节点可以是红色的或者黑色的

2.根节点是黑色的

3.叶子节点(空节点)的黑色的

4.每个红色的节点的子节点都是黑色的

5.任何一个 节点 到其每一个 叶子节点 的所有路径上 黑色节点数 相同

原文 

https://segmentfault.com/a/1190000023293466

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » java学习笔记(6)——数据结构

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址