List接口
ArrayList类
整体上：
- ArrayList实现了 RandomAccess 接口，因此支持随机访问；
实现了Cloneable接口，它的作用是使一个类的实例能够将自身拷贝到另一个新的实例中
主要成员变量
elementData：用于存放元素的Object数组
- size：elementData数组的大小
- DEFAULT_CAPACITY：数组的默认大小为10
扩容机制
添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为 oldCapacity + (oldCapacity >> 1)，也就是旧容量的 1.5 倍。扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小（默认大小为10），减少扩容操作的次数。
注意： “int newCapacity = oldCapacity + (oldCapacity >> 1)”，这句话比较准确的说法是：新的容量是旧容量加上旧容量值右移一位得到的，说1.5倍并不非常准确。比如：初始容量为15，那么，扩容1.5倍后应该为22.5，但实际上却是22，并不是1.5倍。所以严谨来说，ArrayList扩容机制为：新容量为原容量的1.5倍取整，或者是新容量为旧容量加上旧容量右移一位，推荐后一种说法。 参考文章：https://blog.csdn.net/ql_7256/article/details/107537476
删除元素
删除操作需要调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上，该操作的时间复杂度为 O(N)，可以看出 ArrayList 删除元素的代价是非常高的。
序列化
ArrayList 基于数组实现，并且具有动态扩容特性，因此保存元素的数组不一定都会被使用，那么就没必要全部进行序列化。保存元素的数组 elementData 使用 transient 修饰，该关键字声明数组默认不会被序列化。
transient Object[] elementData; // non-private to simplify nested class access
ArrayList 实现了 writeObject() 和 readObject() 来控制只序列化数组中有元素填充那部分内容。序列化时需要使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出，而 writeObject() 方法在传入的对象存在 writeObject() 的时候会去反射调用该对象的 writeObject() 来实现序列化。反序列化使用的是 ObjectInputStream 的 readObject() 方法，原理类似。
ArrayList list = new ArrayList();ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));oos.writeObject(list);
LinkedList类
主要成员变量
LinkedList是基于双向链表实现的：
- Node：Node是一个静态内部类，它代表双向链表的一个节点，其中的item是存储的元素，next是下一个节点指针，prev则是上一个节点指针
- first：头节点指针
- last：尾节点指针
并且LinkedList的头节点并不存放数据：
因此上面的链表对应的size=2而不是3
与ArrayList对比
LinkedList和ArrayList对比其实就是双向链表和数组的对比：
- ArrayList 基于动态数组实现，LinkedList 基于双向链表实现
- ArrayList 支持随机访问，LinkedList 不支持
- LinkedList 在任意位置添加删除元素更快
但是，二者的对比其实也不能像上面一样简单对比，还是需要深入对比：
- 顺序插入速度ArrayList会比较快，因为ArrayList是基于数组实现的，数组是事先new好的，只要往指定位置塞一个数据就好了；LinkedList则不同，每次顺序插入的时候LinkedList将new一个对象出来，如果对象比较大，那么new的时间势必会长一点，再加上一些引用赋值的操作，所以顺序插入LinkedList必然慢于ArrayList
- LinkedList里面不仅维护了待插入的元素，还维护了Entry的前置Entry和后继Entry，如果一个LinkedList中的Entry非常多，那么LinkedList将比ArrayList更耗费一些内存
- 通常认为认为LinkedList做插入和删除更快，但这种说法其实是不是非常准确：LinkedList做插入、删除的时候，慢在寻址，快在只需要改变前后Entry的引用地址；ArrayList做插入、删除的时候，慢在数组元素的批量copy，快在寻址。所以，如果待插入、删除的元素是在数据结构的前半段尤其是非常靠前的位置的时候，LinkedList的效率将大大快过ArrayList，因为ArrayList将批量copy大量的元素；越往后，对于LinkedList来说，因为它是双向链表，所以在第2个元素后面插入一个数据和在倒数第2个元素后面插入一个元素在效率上基本没有差别，但是ArrayList由于要批量copy的元素越来越少，操作速度必然追上乃至超过LinkedList。
Vector类
Vector类其实底层的数据结构和ArrayList类是一模一样的，只是ArrayList的方法是线程不安全的，但是Vexctor类是线程安全的，但是Vector这个类由于并发效率低下，因此通常不用这个类来做并发编程。同步
Vector实现线程安全的方式就是使用了synchronized 关键字来进行同步，如下所示： ```java public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; }
public synchronized E get(int index) { if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
其实就是简单的在ArrayList的方法上面加了一个 synchronized 关键字，因此才说Vector并发效率低下，锁的细粒度太粗糙了。<a name="hBI8E"></a>### 与ArrayList对比当然，与ArrayList对比来看，还是具有一些些细微的差别的：- Vector 是同步的，因此开销就比 ArrayList 要大，访问速度更慢。最好使用 ArrayList 而不是 Vector，因为同步操作完全可以由程序员自己来控制- Vector 每次扩容请求其大小的 2 倍空间，而 ArrayList 是 1.5 倍<a name="k1Zgc"></a>### 并发代替方案因为Vector的并发效率低下，所以JDK后面就提供了一些工具类代替这个过时的类：<br /><a name="T34Aq"></a># Set接口<a name="BBh79"></a>## HashSet类<br />可以看到，有两个重要熟悉。即map和PRESENT，其中PRESENT是静态的。通过构造方法可以看出，HashSet是基于HashMap实现的，默认构造函数是构建一个初始容量为16，负载因子为0.75 的HashMap。封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。> 注意：> HashSet其实是基于HashMap实现了，HashMap的实现原理：[https://www.yuque.com/zhengzaijiazai-9byqp/hicq1i/kqetlq#NbVuW](https://www.yuque.com/zhengzaijiazai-9byqp/hicq1i/kqetlq#NbVuW)[](https://blog.csdn.net/guoweimelon/article/details/50804799)<a name="S0ipW"></a>## TreeSet类<br />可以看到TreeSet的属性m其实就是一个TreeMap，因此TreeSet其实就是封装了一个TreeMap，以TreeMap的key作为TreeMap的value，TreeMap的value就是一个静态对象PRESENT。> 注意：> - 底层是在TreeMap的基础上进行封装，所以结构是红黑树，TreeMap实现：[https://www.yuque.com/zhengzaijiazai-9byqp/hicq1i/kqetlq#iv8hp](https://www.yuque.com/zhengzaijiazai-9byqp/hicq1i/kqetlq#iv8hp)> - 因为是红黑树结构，所以不需要重写hashCode()和equals()方法来保证唯一性。> - TreeMap有的特性TreeSet都有，还在这个基础上增加了保证元素唯一性的特点。<a name="detey"></a>## LinkedHashSet类LinkedHashSet是在HashSet基础上可以保持插入顺序的一种Set集合。它是直接继承了HashSet，而HashSet又是HashMap包装了一层，而LinkedHashMap是HashMap的子类，所以HashSet的实现其实是依赖了LinkedHashMap。<br /><br />LinkedHashSet就是在HashMap、HashSet和LinkedHashMap的基础上进行了下封装，没有加任何变化，从而达到在保证元素唯一性的情况下还可以保证遍历顺序是插入顺序的效果。<a name="oCivc"></a># Queue接口<a name="BxhCF"></a>## LinkedList类LinkedList其实也可以作为队列使用，因为LinkedList也实现了Queue接口的各个方法。如下所示：```java//不推荐LinkedList<T> q = new LinkedList<T>();//推荐Queue<T> q = new LinkedList<T>();//入队：void offer(T v)q.offer(v);//出队：//方法一：T poll(), 如果队列为空，则返回null//方法二：T remove(), 如果队列为空，则抛出异常T t=q.pop();//获取队头元素://方法一：T peek(), 如果队列为空，则返回null;//方法二：T element(), 如果队列为空，则抛出异常T t=q.peek();//判断队列是否为空，boolean isEmpty(), 空返回true，否则返回falseboolean b=q.isEmpty();
PriorityQueue类
PriorityQueue是一个优先级队列，所谓优先级队列就是数据按关键词有序排列，插入新数据的时候，会自动插入到合适的位置保证队列有序（默认升序）。PriorityQueue是基于优先堆的一个无界队列，这个优先队列中的元素可以默认自然排序或者通过提供的Comparator（比较器）在队列实例化的时排序。要求使用Java Comparable和Comparator接口给对象排序，并且在排序时会按照优先级处理其中的元素。如：
public class Main {
public static void main(String[] args) {
Queue<Integer> queue = new PriorityQueue<>(7);
List<Integer> randomList = new ArrayList<>();
List<Integer> res = new ArrayList<>();
Random random = new Random();
for (int i = 0; i < 7; i++) {
int integer = random.nextInt(7);
randomList.add(integer);
queue.add(integer);
}
for (int i = 0; i < 7; i++) {
res.add(queue.poll());
}
System.out.println(randomList);
System.out.println(res);
}
}
底层结构
而这个优先队列底层的数据结构是一个二叉堆，所谓二叉堆就是满足以下条件的二叉树：
- 二叉堆是一个完全二叉树
- 根节点总是大于左、右子节点（大顶堆），或者是小于左、右子节点（小顶堆）
其中（a）是大顶堆，（b）是小顶堆。
其中数组queu就是这个小顶堆（默认下）。以一个优先队列：3、5、7、9、10、11、12、13、15、20. 为例，以下是其存储结构：
每个元素按照层序遍历的方式进行了编号，发现父节点和子节点的编号是有联系的，更确切的说父子节点的编号之间有如下关系：
//其中nodeNo代表当前节点的编号，leftNo代表左子节点编号，rightNo代表右子节点，而
parentNo代表父节点编号
leftNo = parentNo*2+1
rightNo = parentNo*2+2
parentNo = (nodeNo-1)/2
入队
add(E e)和offer(E e)的语义相同，都是向优先队列中插入元素，只是Queue接口规定二者对插入失败时的处理不同，前者在插入失败时抛出异常，后则则会返回false。对于PriorityQueue这两个方法其实没什么差别，下图以插入元素4为例：
public boolean offer(E e) {
if (e == null)//不允许放入null元素
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);//自动扩容
size = i + 1;
if (i == 0)//队列原来为空，这是插入的第一个元素
queue[0] = e;
else
siftUp(i, e);//调整堆结构
return true;
}
出队
remove()和poll()方法的语义也完全相同，都是获取并删除队首元素，区别是当方法失败时前者抛出异常，后者返回null。由于删除操作会改变队列的结构，为维护小顶堆的性质，需要进行必要的调整。下图以删除最小元素3 为例：
有序性的说明
前面说的，优先队列数据按关键词有序排列其实并不十分准确，通过上面的图也可以知道，其实数组queue并不是物理上的有序，而优先队列的有序性指的是出队的顺序是从小到大（默认小顶堆）的有序出队，因为小顶堆的根节点一定（即队头）是所有元素中最小的。
若有收获，就点个赞吧
0 人点赞
