一、数据结构
1、红黑树
根黑子黑红子黑
接近平衡树（左右孩子数量相同），查询叶子快慢次数不超过2倍
二、List
1、概述
元素有序
线性存储
带有索引
可以重复
2、常用方法
增：add(I,E)
删：E removerI()
改：set(I,E)
查：get(O)
3、常用子类
ArrayList
LinkedList：提供大量首尾操作的方法，也可作为堆栈和队列使用
addFirst()
addLast()
getFirst()
getLast()
removeFirst()：移除并 返回
removeLast()
pop()
push()
isEmpty()
Vector：线程安全
Enumeration<E> elements()：返回元素的枚举
addElement(E)：添加到向量末尾，大小加一
三、Set
1、概述
元素无序
不会重复
2、HashSet
不重复，无序，速度快，初始容量为16
存储结构：
1.8前：数组+链表
1.8后：数组+链表--->数组+红黑树（链表长度超过8位时）
调用add方法时，会分别使用hashCode()和equals()方法判断元素是否重复
3、LinkedHashSet
链表+哈希表 ，保证元素有序且不重复
4、可变参数（jdk1.5后）
前提：参数类型确定，个数不确定
格式：定义方法时使用(数据类型…参数名)
原理：底层是数组，根据传参个数创建不同长度的数组，可以为0个
注意：只能有一个；参数有多个，可变参数必须写在末尾
举例：计算任意个数之和--add(int..arr)
五、Collections：用于对集合操作的集合工具类
1、常用方法
addAll(Collection<T> c, T... elements)：使用可变参数向集合中添加元素，如addAll(list,1,2,3,4)
shuffle(List)：打乱集合顺序
sort(List<T> list)：升序排序
sort(List<T> list，Comparator<? super T> )：按指定规则排序
2、Comparator
实现方式：Comparable接口（类中实现compareTo方法）和Comparator接口（区别）
Comparator作为参数传递，重写compare方法
import java.util.Arrays; public class User implements Comparable<User> { public int age;
public String username; public User(int age, String username) {
this.age = age;
this.username = username;
} @Override
public String toString() {
return this.username;
} @Override
public int compareTo(User o) {
if(this.age>o.age) {
return 1;
} else if(this.age<o.age) {
return -1;
} else {
return 0;
}
} public static void main(String[] args) {
User[] arr = new User[3];
arr[0] = new User(15,"user1");
arr[1] = new User(10,"user2");
arr[2] = new User(20,"user3"); System.out.println("排序前：");
System.out.println(Arrays.toString(arr)); Arrays.sort(arr); System.out.println("排序后：");
System.out.println(Arrays.toString(arr)); } }
