3-2-List

文章目录

1. 1. ArrayList数组
   1. 1.1. 1.数组实现，快速随机访问
   2. 1.2. 2.元素没间隔，插入删除需复制移动旧，慢
   3. 1.3. 3.适合随机查找和遍历，不适合插入和删除
   4. 1.4. arrays.sort用什么排序
2. 2. vector（数组实现，线程安全）
   1. 2.1. 1.某一时刻只有一个线程能够读写vector
   2. 2.2. 2.同步高花费，访问比arraylist慢
3. 3. linkedlist（链表）
   1. 3.1. 1.适合数据动态插入和删除
   2. 3.2. 2.随机访问和遍历慢
   3. 3.3. 3.可操作表头表尾，可当堆栈、队列、双向队列用
4. 4. stack（继承vector类）
5. 5. Queue接口（LinkedList实现了queue接口）
   1. 5.1. 1. Queue接口窄化了对LinkedList的方法的访问权限，完全只能访问Queue接口所定义的方法
   2. 5.2. 2. BlockingQueue继承了Queue接口（线程池必考blockingqueue类别）
6. 6. 线程安全的list: copyonwritelist, synchronizedlist

ArrayList数组

1.数组实现，快速随机访问

2.元素没间隔，插入删除需复制移动旧，慢

3.适合随机查找和遍历，不适合插入和删除

arrays.sort用什么排序

1. 数量非常小的情况下（就像上面说到的，少于47的），插入排序等可能会比快速排序更快。 所以数组少于47的会进入插入排序。

2. 快排数据越无序越快（加入随机化后基本不会退化），平均常数最小，不需要额外空间，不稳定排序。

3. 归排速度稳定，常数比快排略大，需要额外空间，稳定排序。

   

看得出是数据越多，arrays.sort倾向用空间来换时间。少数据的时候时间复杂度差别不大，就不占用额外空间了。

vector（数组实现，线程安全）

1.某一时刻只有一个线程能够读写vector

2.同步高花费，访问比arraylist慢

linkedlist（链表）

1.适合数据动态插入和删除

2.随机访问和遍历慢

3.可操作表头表尾，可当堆栈、队列、双向队列用

stack（继承vector类）

栈是 后进先出的。 栈提供了通常的 push 和 pop 操作，以及取堆栈顶点的 peek 方法、测试堆栈是否为空的 empty 方法、在堆栈中查找项并确定到堆栈顶距离的 search 方法。

Queue接口（LinkedList实现了queue接口）

1. Queue接口窄化了对LinkedList的方法的访问权限，完全只能访问Queue接口所定义的方法

2. BlockingQueue继承了Queue接口（线程池必考blockingqueue类别）

线程安全的list: copyonwritelist, synchronizedlist

我们可以使用Collections.synchronizedList(List list)方式，也可以使用CopyOnWriteArrayList类。在真实环境中，使用它们可以根据我们的业务需要，在插入操作远远超过读取时，建议使用第一种方式，这是因为CopyOnWriteArrayList在插入的过程中会创建新的数组，这样在数据量特别大的情况下，对内存的消耗是很大的。当然，如果是读取操作远远大于插入时，第二种方式肯定更占优势，毕竟读取操作完全不需要加锁。