java学习笔记（6）——数据结构
栈
先进后出
入：压栈
出：弹栈
队列
先进先出
入口和出口在两侧
数组
查询快：地址连续，通过首地址与索引可以快速查找某个元素
增删慢：长度不变，增加/删除必须创建新数组，再把源数组复制过来，再把源数组的地址赋给新数组，源数组就会自动销毁
链表
查询慢：链表中 地址不连续 ，每次查询元素都必须 从头开始查询
增删快：链表结构，增加/删除一个元素，对链表的整体结构没有影响
链表总的每一个元素也称为一个 节点
一个节点包含了 一个数据源 （存储数组）， 两个指针域 （存储地址）
一个节点：
单向链表：
链表中只有一条链子，不能保证元素的顺序（存储元素和取出元素的顺序有可能不一致）
无序
双向链表：
链表中有两条链子，有一条链子是专门记录元素的顺序，是一个有序的集合
下一个节点记住上一个节点的地址，上一个节点也记住上一个节点的地址
有序
树
计算机的树（倒着）
二叉树：
分支不能超过两个
排序树/查找树：
在二叉树的基础上，元素的是有大小顺序的
左子树小，右子树大
平衡树：
左孩子数量和右孩子数量相等
不平衡树：
左孩子数量 ！= 右孩子数量
红黑树
特点：
趋于平衡式， 查询速度非常的快 ，查询叶子节点最大次数和最小次数不能超过2倍。
约束：
1.节点可以是红色的或者黑色的
2.根节点是黑色的
3.叶子节点（空节点）的黑色的
4.每个红色的节点的子节点都是黑色的
5.任何一个 节点 到其每一个 叶子节点 的所有路径上 黑色节点数 相同
正文到此结束
热门推荐
相关文章
Loading...
![[HBLOG]公众号](http://www.liuhaihua.cn/img/qrcode_gzh.jpg)
