常见数据结构: 堆栈, 队列, 数组, 链表, 红黑树
栈
先进后出(FILO)(first int last out)
栈的入口、出口的都是栈的顶端位置。
压栈：存元素。
弹栈：取元素。
队列 先进先出
数组
查询快 增删慢
数据结构
链表 :linked list, { ArrayList底层是一个数组}
查询慢 (没索引) 增删快
链表的适用场景:
查询少, 增删多的场景
链表可以实现栈和队列的结构, 因为栈和队列增删频繁
由结点组成.结点: 两部分 1. 数据域 2. 指针域
红黑树
二叉树：每个结点不超过2的有序树
二叉树是每个节点最多有两个子树的树结构。顶上的叫根结点，两边被称作“左子树”和“右子树”。
查找: 节点存储的元素是按照大小顺序存储
特点:
元素存储过程中就完成了大小排序
查询比链表快, 增删比数组快 (数组和链表的折中)
红黑树的适用场景:
查询和增删都有, 需要元素自动排序的场景
红黑树的约束:
1. 节点可以是红色的或者黑色的
2. 根节点是黑色的
3. 叶子节点(特指空节点)是黑色的
4. 每个红色节点的子节点都是黑色的
5. 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同
数据结构特点
List集合
1 有序 2 元素可重复 3 有索引
常用方法: 增删改查
public void add(int index, E element)
public E remove(int index)
public E set(int index, E element)
public E get(int index)
ArrayList集合
数组结构。元素增删慢，查找快
应用场景: 查询数据、遍历数据.
LinkedList集合
双向链表结构。方便元素添加、删除的集合。查询慢.
HashSet
根据对象的哈希值确定元素在集合中存储位置
因此具有良好的存取和查找性能
数据结构 数组+链表+红黑树 8
当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。
哈希值主要是为了提高对象存储在 哈希表 中的效率
去重 重写 hashCode 与equals 方法。
HashSet特点:
1. 元素不可重复
2. 没有索引
3. 元素存取无序 (存入和取出顺序有可能不一致)
4. 底层采用 哈希表 结构. (查询快)
哈希表 = 数组 + 链表或红黑树
LinkedHashSet集合
LinkedHashSet特点:
1. 元素存取有序 (存入和取出顺序一致)
2. 元素不可重复
3. 没有索引
总结: 什么时候用List, 什么时候用Set?
要存储的元素可以重复的, 用List集合:
增删少, 用ArrayList
增删多, 用LinkedList
要存储的数据要求不重复, 或者相对一个集合去重, 用Set集合:
不要求存取顺序一致, 用HashSet
要求存取顺序一致, 用LinkedHashSet
可变参数
可变参数的本质就是一个"数组"
注意事项:
1. 可变参数可以传递的参数个数, 可以是 0个, 1个, 多个
2. 一个方法的参数列表中, 只能有一个可变参数
3. 如果方法的参数有多个, 可变参数必须写在参数列表的最后
Collections集合工具类
静态方法:
boolean addAlladdAll(Collection<? super T> c, T... elements):往集合中添加一些元素
static void shuffle(List<?> list): 打乱集合顺序
sort(List<T> list): 将集合中元素按照默认规则排序
sort(List<T> list，Comparator<? super T> c):将集合中元素按照指定规则排序
Collections集合工具类: sort(List list)
sort(List<T> list): 默认按照"升序"将元素排序
数字, 字母, 都可以按照升序排序
自定义JavaBean对象要想排序重写 int compareTo(E e) 方法
规则:
this-参数: 升序(从小到大)
参数-this: 降序(从大到小)
Collections集合工具类: sort(List list，Comparator<? super T> )
Comparable接口和Comparator接口区别
Comparable: 让JavaBean自身具有可比较性 (自己和其他人比)
Comparator: 定义一个比较器类, 用比较器对象比 (让第三个人来帮两个人比较)
Comparator使用方式:
1. 定义类实现Comparator<E>接口, 重写 int compare(E o1, E o2) 方法, 泛型为比较元素的类型
规则:
o1-o2: 升序(从小到大)
o2-o1: 降序(从大到小)
2. 在Collections.sort(List<T> list，Comparator<? super T> c)方法中传入自定义比较器对象
栈
先进后出(FILO)(first int last out)
栈的入口、出口的都是栈的顶端位置。
压栈：存元素。
弹栈：取元素。
队列 先进先出
数组
查询快 增删慢
数据结构
链表 :linked list, { ArrayList底层是一个数组}
查询慢 (没索引) 增删快
链表的适用场景:
查询少, 增删多的场景
链表可以实现栈和队列的结构, 因为栈和队列增删频繁
由结点组成.结点: 两部分 1. 数据域 2. 指针域
红黑树
二叉树：每个结点不超过2的有序树
二叉树是每个节点最多有两个子树的树结构。顶上的叫根结点，两边被称作“左子树”和“右子树”。
查找: 节点存储的元素是按照大小顺序存储
特点:
元素存储过程中就完成了大小排序
查询比链表快, 增删比数组快 (数组和链表的折中)
红黑树的适用场景:
查询和增删都有, 需要元素自动排序的场景
红黑树的约束:
1. 节点可以是红色的或者黑色的
2. 根节点是黑色的
3. 叶子节点(特指空节点)是黑色的
4. 每个红色节点的子节点都是黑色的
5. 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同
数据结构特点
List集合
1 有序 2 元素可重复 3 有索引
常用方法: 增删改查
public void add(int index, E element)
public E remove(int index)
public E set(int index, E element)
public E get(int index)
ArrayList集合
数组结构。元素增删慢，查找快
应用场景: 查询数据、遍历数据.
LinkedList集合
双向链表结构。方便元素添加、删除的集合。查询慢.
HashSet
根据对象的哈希值确定元素在集合中存储位置
因此具有良好的存取和查找性能
数据结构 数组+链表+红黑树 8
当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。
哈希值主要是为了提高对象存储在 哈希表 中的效率
去重 重写 hashCode 与equals 方法。
HashSet特点:
1. 元素不可重复
2. 没有索引
3. 元素存取无序 (存入和取出顺序有可能不一致)
4. 底层采用 哈希表 结构. (查询快)
哈希表 = 数组 + 链表或红黑树
LinkedHashSet集合
LinkedHashSet特点:
1. 元素存取有序 (存入和取出顺序一致)
2. 元素不可重复
3. 没有索引
总结: 什么时候用List, 什么时候用Set?
要存储的元素可以重复的, 用List集合:
增删少, 用ArrayList
增删多, 用LinkedList
要存储的数据要求不重复, 或者相对一个集合去重, 用Set集合:
不要求存取顺序一致, 用HashSet
要求存取顺序一致, 用LinkedHashSet
可变参数
可变参数的本质就是一个"数组"
注意事项:
1. 可变参数可以传递的参数个数, 可以是 0个, 1个, 多个
2. 一个方法的参数列表中, 只能有一个可变参数
3. 如果方法的参数有多个, 可变参数必须写在参数列表的最后
Collections集合工具类
静态方法:
boolean addAlladdAll(Collection<? super T> c, T... elements):往集合中添加一些元素
static void shuffle(List<?> list): 打乱集合顺序
sort(List<T> list): 将集合中元素按照默认规则排序
sort(List<T> list，Comparator<? super T> c):将集合中元素按照指定规则排序
Collections集合工具类: sort(List list)
sort(List<T> list): 默认按照"升序"将元素排序
数字, 字母, 都可以按照升序排序
自定义JavaBean对象要想排序重写 int compareTo(E e) 方法
规则:
this-参数: 升序(从小到大)
参数-this: 降序(从大到小)
Collections集合工具类: sort(List list，Comparator<? super T> )
Comparable接口和Comparator接口区别
Comparable: 让JavaBean自身具有可比较性 (自己和其他人比)
Comparator: 定义一个比较器类, 用比较器对象比 (让第三个人来帮两个人比较)
Comparator使用方式:
1. 定义类实现Comparator<E>接口, 重写 int compare(E o1, E o2) 方法, 泛型为比较元素的类型
规则:
o1-o2: 升序(从小到大)
o2-o1: 降序(从大到小)
2. 在Collections.sort(List<T> list，Comparator<? super T> c)方法中传入自定义比较器对象
