Java集合（二）List的常用实现类
List、ArrayList（动态数组）、LinkedList（链表）、fail-fast机制、CopyOnWriteArrayList、Vector、Stack（栈）
·
本系列文章：
Java集合（一）集合框架概述
Java集合（二）List的常用实现类
Java集合（三）Java集合（三）Map的常用实现类
Java集合（四）Set的常用实现类
Java集合（五）BlockingQueue的常用实现类
一、List
1.1 List简介
List是有序集合，使用List可以控制列表中每个元素的插入位置，可以通过整数索引（列表中的位置）访问元素，并搜索列表中的元素。
List通常允许重复的元素。
使用List存储的特点：元素有序、可重复。
List最常见的实现方式是ArrayList和LinkedList。以下是List接口常见实现类的对比：
| 具体实现 | 优点 | 缺点 |
|---|---|---|
| ArrayList | 底层数据结构是数组，查询快，效率高 |
增删慢；线程不安全 |
| LinkedList | 底层数据结构是链表，增删快，效率高 |
查询慢；线程不安全 |
| Vector | 底层数据结构是数组，查询快；线程安全 |
增删慢，效率低 |
| CopyOnWriteArrayList | 底层数据结构是数组，读写分离，效率高；线程安全， |
内存消耗较大；只能保证数据的最终一致性，不能保证数据的实时一致性 |
ArrayList是一个动态数组，随着容器中的元素不断增加，容器的大小也会随着增加。同时由于ArrayList底层是数组实现，所以可以随机访问元素。
Vector与ArrayList类似，不过是同步的，因此Vector是线程安全的动态数组。
Stack继承自Vector，实现一个后进先出的堆栈。
LinkedList是一个双向链表，LinkedList不能随机访问，增删元素比较方便。
CopyOnWriteArrayList是一个线程安全、并且在读操作时无锁的 ArrayList。当需要修改容器中的元素时，会首先将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器。
数据元素在内存中，主要有2种存储方式：顺序存储和链式存储。
- 1、顺序存储
这种方式，相邻的数据元素存放于相邻的内存地址中，整块内存地址是连续的。可以根据元素的位置直接计算出内存地址，直接进行读取。读取一个特定位置元素的平均时间复杂度为O(1)。正常来说，只有基于数组实现的集合，才有这种特性。
在List的实现类中，顺序存储以ArrayList为代表。 - 2、链式存储
这种方式，每一个数据元素，在内存中都不要求处于相邻的位置，每个数据元素包含它下一个元素的内存地址。不可以根据元素的位置直接计算出内存地址，只能按顺序读取元素。读取一个特定位置元素的平均时间复杂度为O(n)。主要以链表为代表。
在List的实现类中，链式存储以LinkedList为代表。
1.2 遍历List
对于List集合的实现类，常见的遍历方式是：for循环、for each遍历和迭代器遍历。
1.2.1 不同遍历方式(for循环/迭代器/foreach)
- 1、for循环遍历
基于计数器。在集合外部维护一个计数器，然后依次读取每一个位置的元素，当读取到最后一个元素后停止。这种遍历方式主要就是需要按元素的位置来读取元素。示例：
for (int i = 0; i < list.size(); i++) {
list.get(i);
}
- 2、迭代器遍历
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
iterator.next();
}
- 3、foreach 循环遍历
foreach内部也是采用了Iterator的方式实现，使用时不需要显式声明Iterator或计数器。优点是代码简洁，不易出错；缺点是只能做简单的遍历，不能在遍历过程中操作数据集合，例如删除、替换。示例：
for (String str : list) {
}
1.2.2 适用场合(数组实现的用for循环,其他使用Iterator/foreach)
- 1、for循环遍历
for循环遍历，适用于遍历顺序存储集合，因为读取性能比较高。扩展了说，for循环遍历适合实现了RandomAccess接口的集合。如果一个数据集合实现了该接口，就意味着它支持顺序访问，按位置读取元素的平均时间复杂度为 O(1)，如ArrayList。如果没有实现该接口，表示不支持顺序访问，如LinkedList。 - 2、迭代器遍历
顺序存储：如果不是太在意时间，推荐选择此方式，毕竟代码更加简洁。
链式存储：平均时间复杂度降为O(n)，所以推荐此种遍历方式。
使用迭代器更加线程安全，因为它可以确保，在当前遍历的集合元素被更改的时候，它会抛出ConcurrentModificationException。
综合而言，推荐的做法就是，支持顺序访问的List可用for循环遍历，否则建议用Iterator或foreach遍历。此外，如果需要在遍历时修改元素，则需要使用迭代器的遍历方式，否则会出现ConcurrentModificationException。
1.3 常见List实现类比较
1.3.1 ArrayList和LinkedList
| ArrayList | LinkedList | |
|---|---|---|
| 线程安全性 | 线程不安全 | 线程不安全 |
| 底层实现 | 动态数组 |
双向链表（JDK1.6之前为循环链表，JDK1.7取消了循环） |
| 访问方式 | 支持通过元素的下标访问元素 |
不支持通过元素的下标访问元素 |
| 增加和删除效率 | 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。 如果要在指定位置 i 插入和删除元素的话，时间复杂度就为 O(n)。 |
采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1） |
| 是否支持快速随机访问 |
支持 | 不支持 |
| 内存空间 | ArrayList的空间浪费主要体现在列表的结尾会预留⼀定的容量空间 | 更占内存，因为LinkedList的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素 |
LinkedList是一个双链表，在添加和删除元素时具有比ArrayList更好的性能，但在get与set方面弱于ArrayList。当然，这些对比都是指数据量很大或者操作很频繁。
综合来说，在需要频繁读取集合中的元素时，更推荐使用ArrayList，而在插入和删除操作较多时，更推荐使用LinkedList。
- 快速随机访问
快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(int index)方法)，对应到Java代码中，就是一个接口：
public interface RandomAccess {
}
RandomAccess接口用来标识其实现类具有快速随机访问的特点。
- 两者效率对比
当从头部依次添加元素时，链表和数组的性能差不不多。但当数据初始化完成之后，我们再进行插入操作时，尤其是从头部插入时，因为数组要移动之后的所有元素，因此性能要比链表低很多；但在查询时性能刚好相反，因为链表要遍历查询，并且LinkedList 是双向链表，所以在中间查询时性能要比数组查询慢了上万倍（查询 100 个元素），而两头查询（头部和尾部）时，链表也⽐数组慢了将近 1000 多倍（查询 100 个元素），因此在查询较多的场景中，我们要尽量使用数组，在添加和删除操作较多时，应该使用链表结构。
数组和链表的操作时间复杂度对比：
| 数组 | 链表 | |
|---|---|---|
| 查询 | O(1) | O(n) |
| 插入、删除 | O(n) | O(1) |
1.3.2 ArrayList和Vector
这两个类都实现了List接口，他们都是有序集合。相同点：
- ArrayList和Vector都是继承了相同的父类和实现了相同的接口。
- 底层都是数组实现的。
- 初始默认长度都为10。
- 迭代器的实现都是fail-fast的。
ArrayList和Vector的不同点：
| ArrayList | Vector | |
|---|---|---|
| 线程安全性 | 线程不安全 | 使用Synchronized来修饰大部分方法，线程安全 |
| 性能 | 更优 | 由于使用了Synchronized，性能较差 |
| 扩容 | 1.5倍扩容 |
2倍扩容 |
ArrayList与Vector都可以设置初始的空间大小， Vector还可以设置增长的空间大小，而ArrayList 没有提供设置增长空间的方法。
ArrayList更加通用，因为我们可以使用Collections工具类轻易地获取同步列表和只读列表。
二、ArrayList
2.1 ArrayList介绍
简单来说，ArrayList是动态数组（数组的容量会随着元素数量的增加而增加，即动态变化）。
ArrayList的继承关系：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
在ArrayList中，并没有规定特殊的元素操作规则（比如只能在数组两端进行增删等），所以ArrayList是操作非常自由的动态数组：
- 可以在数组头部 / 尾部 / 中间等任意位置插入、删除元素。
- 添加单个或集合中的元素时，未指明添加位置时，都是添加在尾部。
- 不会像队列那样在增加、取出元素时可能会产生阻塞现象。
2.1.1 ArrayList的特点(初始容量10/1.5倍扩容/访问元素效率高，增删元素效率低/线程不安全)
- 1、自动扩容(1.5倍扩容)
ArrayList是动态数组，这里的“动态”说的就是可以自动扩容。ArrayList默认初始容量为10，当容量不足时可以自动扩容（1.5倍扩容，即：原来大小+原来大小*0.5）。
ArrayList的初始容量可以指定，扩容倍数(1.5)不能指定。 - 2、线程不安全
ArrayList是线程不安全的，也实现了fail-fast机制。 - 3、访问元素效率高，增删元素效率低
ArrayList实现了RandomAccess接口，支持随机访问。get、set、isEmpty等方法的时间复杂度都是O(1)，即遍历和随机访问元素效率比较高；add的时间复杂度是O(n)，添加和删除元素效率比较低。 - 4、可添加null,有序可重复
ArrayList在添加元素时，并不需要进行非空判定，所以可以是null。ArrayList内的元素是有序的，所以也可重复。 - 5、元素下标是从0开始
因为ArrayList底层实现是数组，所以下标是从0开始。 - 6、大量使用System.arraycopy()
ArrayList是动态数组，所以肯定会有元素拷贝动作，ArrayList的实现中大量地调用了Arrays.copyof()和 System.arraycopy()方法，其实Arrays.copyof()内部也是调用 System.arraycopy()。System.arraycopy()为Native方法。 - 7、支持克隆和序列化
ArrayList实现了Cloneable接口，支持克隆。
ArrayList实现了Serializable接口，支持序列化，能通过序列化去传输。
2.1.2 ArrayList的使用
- 1、构造方法
可以指定初始容量，也可以不指定。
//构造一个初始容量为10的空ArrayList
//（其实是构造了一个容量为空的ArrayList，第一次添加元素时，扩容为10）
public ArrayList()
//构造具有指定初始容量的空ArrayList
public ArrayList(int initialCapacity)
- 2、添加元素
可以直接添加到尾部，也可以添加到指定位置。
//将元素追加到此ArrayList的尾部
public boolean add(E e)
//在指定位置插入元素
public void add(int index, E element)
- 3、删除元素
可以删除某个元素，也可以清空ArrayList。
//删除指定位置的元素
public E remove(int index)
//从ArrayList中删除第一个出现指定元素的（如果存在）
public boolean remove(Object o)
//清空ArrayList
public void clear()
- 4、获取元素
根据下标获取对应位置的元素，和数组类似。
public E get(int index)
- 5、获取指定元素的下标
可以从前向后，也可以从后向前，查找某个元素在ArrayList中的下标。
//返回指定元素的第一次出现的索引，如果此ArrayList不包含元素，则返回-1
public int indexOf(Object o)
//返回指定元素的最后一次出现的索引，如果此ArrayList不包含元素，则返回-1
public int lastIndexOf(Object o)
- 6、替换元素
和数组类似，替换指定下标的元素，并且将原下标对应的元素返回。
//替换元素，返回原有元素
public E set(int index, E element)
- 7、截取ArrayList
截取ArrayList的子串。
//返回此ArrayList中指定的 fromIndex （包括）和 toIndex（不包括）之间的子ArrayList
public List< E > subList(int fromIndex, int toIndex)
- 8、通用性方法
判断ArrayList是否为空、获取总的元素数等。
//判断ArrayList是否为空
public boolean isEmpty()
//返回ArrayList中的元素数
public int size()
//判断是否包含某个元素
public boolean contains(Object o)
2.1.3 自动扩容机制(1.5倍扩容)
ArrayList自动扩容的本质就是计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去。
自动扩容时的方法调用：add --> ensureCapacityInternal --> calculateCapacity --> grow --> hugeCapacity。
自动扩容机制是每次向数组中添加元素前，必须要做的判断操作，因此自动扩容的入口在add方法：
public boolean add(E e) {
//判断是否可以容纳e，若能，则直接添加在末尾；
//若不能，则进行扩容，然后再把e添加在末尾
ensureCapacityInternal(size + 1);
//将e添加到数组末尾
elementData[size++] = e;
return true;
}
//每次在add()一个元素时，arraylist都需要对这个list的容量进行一个判断。
//通过ensureCapacityInternal()方法确保当前ArrayList维护的数组具有存储
//新元素的能力，经过处理之后将元素存储在数组elementData的尾部
private void ensureCapacityInternal(int minCapacity) {
//先判断一下是否是使用无参构造方法创建的ArrayList对象，
//如果是的话，就设置默认数组大小为DEFAULT_CAPACITY（10）
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//如果修改后的(最小)数组容量minCapacity大于当前的数组长度elementData.length，
//那么就需要调用grow方法进行扩容，反之则不需要
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
//目前数组长度
int oldCapacity = elementData.length;
//先将当前数组容量扩充至1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//newCapacity：扩容1.5倍后的新数组容量
//minCapacity：数组存储元素所需要的最小容量
//检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么
//就把最小需要容量当作数组的新容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新容量大于MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8),
//调用hugeCapacity方法来获取扩容后数组的合适大小
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//将源数组复制到newCapcity大小的新数组上
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//对minCapacity和MAX_ARRAY_SIZE进行比较
//若minCapacity大，将Integer.MAX_VALUE作为新数组的大小
//若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
综上所述，ArrayList自动扩容流程：
- 1、是否用无参构造方法创建的ArrayList对象。如果是，则ArrayList新容量为10。
- 2、经过第一步后，判断新容量是否够用，不够用就进入扩容流程核心方法grow。
- 3、在grow扩容时，涉及到两个变量：
newCapacity：扩容1.5倍后的新数组容量；
minCapacity：数组存储元素所需要的最小容量，由现有数组元素数量size+1得来。
取两者较大者作为newCapacity。
- 此处为什么要用【初始容量 * 1.5】和【初始容量+1】相比。因为假如初始容量较小(比如0、1、2、3、4)，那么【初始容量 * 1.5】未必大于【初始容量+1】。
- MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8。
- 4、newCapacity与MAX_ARRAY_SIZE比较。
如果newCapacity< MAX_ARRAY_SIZE，则newCapcity不变。
如果newCapacity>MAX_ARRAY_SIZE，再比较minCapacity和MAX_ARRAY_SIZE的大小。如果大于，就令newCapacity = Integer.MAX_VALUE；否则newCapacity = MAX_ARRAY_SIZE。 - 5、将源数组复制到newCapcity大小的新数组上。
这里面有个ArrayList最大容量的问题，常规情况下ArrayList的最大容量为Integer.MAX_VALUE - 8，看源码：
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
ArrayList的存储空间，除了要存元素，还要存储对象头信息，所以-8，避免发生OOM。当然，从代码看，如果Integer.MAX_VALUE - 8的空间不够用的话，还是会将数组空间设置为Integer.MAX_VALUE。
2.2 ArrayList相关问题
2.2.1 Array和ArrayList的区别
| Array | ArrayList | |
|---|---|---|
| 存储的数据类型 | 可以存储基本数据类型和对象（其实是对象的引用） | 只能存储对象 |
| 大小 | 指定固定大小 | 动态扩展 |
2.2.2 多线程场景下如何使用ArrayList(锁/线程安全集合)
常见的方法有以下几种：
- 1、通过Collections的synchronizedList方法将其转换成线程安全的容器后再使用：
List<String> synchronizedList = Collections.synchronizedList(list);
- 2、加锁：
synchronized(list.get()) {
list.get().add(model);
}
- 3、直接使用线程安全的集合，如CopyOnWriteArrayList，替换线程不安全的ArrayList：
List<Object> list1 = new CopyOnWriteArrayList<Object>();
2.2.3 System.arraycopy和Arrays.copyOf
其实Arrays.copyof()也是调用System.arraycopy()来实现的。
- 1、System.arraycopy
在ArrayList的源码中，增删元素时，要移动元素，而移动数组内的元素都是通过System.arraycopy方法来实现的。
//Object src : 原数组
//int srcPos : 从元数据的起始位置开始
//Object dest : 目标数组
//int destPos : 目标数组的开始起始位置
//int length : 要copy的数组的长度
public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
看个例子：
int[] arrs = {1,2,3,4,5,6,7,8,9,10};
for(int i=0;i<arrs.length;i++)
System.out.print(arrs[i]+" "); //1 2 3 4 5 6 7 8 9 10
System.out.println();
//将arrs数组从下标为5的位置开始复制，总共复制5个元素，
//将上面的元素复制到arrs数组，起始位置的下标为0
System.arraycopy(arrs, 5,arrs, 0,5);
for(int i=0;i<arrs.length;i++)
System.out.print(arrs[i]+" "); //6 7 8 9 10 6 7 8 9 10
- 2、Arrays.copyOf
在数组进行扩容时，原有数组中元素的迁移是通过Arrays.copyOf方法来实现的：
//original：要复制的原数组
//newLength：指定要建立的新数组长度，如果新数组的长度超过原数组的长度，则保留数组默认值
//返回值：新的数组对象，改变传回数组中的元素值，不会影响原来的数组
public static < T > T[ ] copyOf(T[ ] original, int newLength)
看个例子：
int[] arr1 = {1, 2, 3, 4, 5};
int[] arr2 = Arrays.copyOf(arr1, 5);
int[] arr3 = Arrays.copyOf(arr1, 10);
for(int i = 0; i < arr2.length; i++)
System.out.print(arr2[i] + " ");
System.out.println(); //1 2 3 4 5
for(int i = 0; i < arr3.length; i++)
System.out.print(arr3[i] + " "); //1 2 3 4 5 0 0 0 0 0
}
2.2.4 ArrayList的扩容因子为什么是1.5
关于扩容因子，有一个很通俗的解释，扩容因子最适合范围为(1, 2)。
为什么不取扩容固定容量呢？扩容的目的需要综合考虑这两种情况：
1、扩容容量不能太小，防止频繁扩容，频繁申请内存空间和数组频繁复制。
2、扩容容量不能太大，需要充分利用空间，避免浪费过多空间。
为什么是1.5，而不是1.2、1.25、1.8或者1.75？因为1.5可以充分利用移位操作，减少浮点数或者运算时间和运算次数。
// 新容量计算
int newCapacity = oldCapacity + (oldCapacity >> 1);
三、LinkedList
3.1 LinkedList介绍
简单来说，LinkedList是一个双向链表：
LinkedList中存放的不是普通的某个中类型的元素，而是节点（Node）。
LinkedList通过prev、next将不连续的内存块串联起来使用。LinkedList是双向链表，除头节点的每一个元素都有prev（前驱指针）同时再指向它的上一个元素，除尾节点的每一个元素都有next（后继指针）同时再指向它的下一个元素。
LinkedList的继承关系：
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
3.1.1 LinkedList特点(双向链表/增删快、查询慢/线程不安全)
- 1、底层实现是双向链表
LinkedList内部是一个双向链表（可以双向遍历）的实现，一个节点除了存储自身的数据外，还持有前、后两个节点的引用。 - 2、增删快、查询慢
LinkedList具有对前后元素的引用，删除、插入节点很快，因为不需要移动其他元素，只需要改变部分节点的引用即可。
LinkedList元素存储地址不连续，不支持随机访问，所以查询速度相比于ArrayList，是比较慢的。 - 3、线程不安全
LinkedList是线程不安全的，也实现了fail-fast机制。 - 4、元素有序可重复
LinkedList中的前后指针可以保证元素的顺序，因此可以重复。 - 5、删除、添加操作时间复杂度为O(1)，查找时间复杂度为O(n)
查找函数有一定优化，容器会先判断查找的元素是离头部较近，还是尾部较近，来决定从头部开始遍历还是尾部开始遍历，因此推荐使用迭代器进行遍历。 - 6、实现了Deque接口，因此也可以作为栈、队列和双端队列来使用
LinkedList在首尾两端都可以操作，因此可以充当栈、队列和双端队列的实现工具。 - 7、可以存储Null值
Node中的item可以为null。
3.1.2 LinkedList的使用
- 1、 构造方法
一般构造空链表。
//构造一个空链表
public LinkedList()
//用已有的集合创建链表的构造方法
public LinkedList(Collection<? extends E> c)
- 2、添加元素
因为LinkedList是双向链表，在首尾都可以操作，所以从首部和尾部添加元素均可。添加元素的方法分为3类：addXxxx、offerXxx、push。
addXxxx：可在首部尾部添加，无返回值。
offerXxx：可在首部尾部添加，有返回值。
push：在首部添加，无返回值。
//将元素追加到此链表末尾
public boolean add(E e)
//在链表的指定位置插入元素
public void add(int index, E element)
//在链表的首部插入元素
public void addFirst(E e)
//将元素追加到链表末尾
public void addLast(E e)
//将元素添加到链表的尾部
public boolean offer(E e)
//在链表的首部插入元素
public boolean offerFirst(E e)
//在链表的末尾插入元素
public boolean offerLast(E e)
//在链表的头部添加元素
public void push(E e)
- 3、删除元素
因为LinkedList是双向链表，在首尾都可以操作，所以从首部和尾部删除元素均可。添加元素的方法分为3类：removeXxx、clear。
removeXxx：删除后可以返回被删除的元素，也可以返回表示删除结果的boolean值。
clear：删除所有元素，即清空链表。
//删除链表中指定位置的元素
public E remove(int index)
//从链表中删除指定元素的第一个出现（如果存在）
public boolean remove(Object o)
//从链表中删除并返回第一个元素
public E removeFirst()
//删除链表中指定元素的第一个出现（从头到尾遍历列表时）
public boolean removeFirstOccurrence(Object o)
//从链表中删除并返回最后一个元素
public E removeLast()
//删除链表中指定元素的最后一次出现（从头到尾遍历列表时）
public boolean removeLastOccurrence(Object o)
//清空链表
public void clear()
- 4、检索并删除元素
删除首部/尾部的元素，并把该元素返回。分为pop、remove、pullXxx3类。
pop/remove：删除并返回链表首部的元素。
pullXxx：可以删除并返回首部/尾部的元素。
//检索并删除链表的首部元素
public E poll()
//检索并删除链表的第一个元素，如果此LinkedList为空，则返回 null
public E pollFirst()
//检索并删除链表的最后一个元素，如果链表为空，则返回 null
public E pollLast()
//删除并返回链表的第一个元素
public E pop()
//检索并删除链表的首部元素
public E remove()
- 5、查找元素
仅查找、不删除元素，有element、getXxx、peekXxx3类。
//检索但不删除链表首部元素
public E element()
//返回链表指定位置的元素
public E get(int index)
//返回链表中的第一个元素
public E getFirst()
//返回链表中的最后一个元素
public E getLast()
//获取且不删除链表首部节点中的元素
public E peek()
//检索但不删除链表的第一个元素，如果链表为空，则返回 null
public E peekFirst()
//检索但不删除链表的最后一个元素，如果链表为空，则返回 null
public E peekLast()
- 6、检索元素位置
从前向后、从后向前，
//返回链表中指定元素的第一次出现的索引，如果此列表不包含元素，则返回-1
public int indexOf(Object o)
//返回链表中指定元素的最后一次出现的索引，如果此列表不包含元素，则返回-1
public int lastIndexOf(Object o)
- 7、替换元素
用指定的元素替换链表中指定位置的元素，并返回被替换的元素。
public E set(int index, E element)
- 8、通用性方法
获取链表元素的个数等。
//返回链表中的元素数
public int size()
//判断链表中是否包含某个元素
public boolean contains(Object o)
四、CopyOnWriteArrayList
4.1 CopyOnWriteArrayList介绍
在很多应用场景中，读操作可能会远远大于写操作。由于读操作根本不会修改原有的数据，因此对于每次读取都进行加锁其实是一种资源浪费。我们可以允许多个线程同时访问List 的内部数据，毕竟读取操作是安全的。CopyOnWriteArrayList恰恰符合这种要求。
CopyOnWriteArrayList位于JUC包下，可以说是读写分离、以空间换时间版的ArrayList。其继承关系和ArrayList也是一致的：
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
CopyOnWriteArrayList是一个线程安全、并且在读操作时无锁的ArrayList，其底层实现也是数组。不止读操作时无锁，写入也不会阻塞读取操作。只有写入和写入之间需要进行同步等待。
CopyOnWriteArrayList 类的所有可变操作（add、set等）都是通过创建底层数组的新副本来实现的。当List需要被修改的时候，并不修改原有内容，而是对原有数据进行一次复制，副本用来写，原来的数据用来读。写完之后，再将修改完的副本替换原来的数据，这样就可以保证写操作不会影响读操作。
4.1.1 CopyOnWriteArrayList的特点(现成安全/弱一致性/最终一致性/适合读操作大于写操作的场景)
- 1、线程安全
CopyOnWriteArrayList所有写操作，都是通过对底层数组进行一次新的复制来实现，是线程安全的。 - 2、适合读操作大于写操作的场景
CopyOnWriteArrayList适合使用在读操作远远大于写操作的场景里，比如缓存。CopyOnWriteArrayList不存在扩容的概念，每次写操作都要复制一个副本，在副本的基础上修改后改变原来的引用。CopyOnWriteArrayList中写操作需要大面积复制数组，所以性能差。 - 3、内存消耗较大
CopyOnWriteArrayList虽然读多写少的场景，不过要慎用 ，因为当CopyOnWriteArrayList存放的数据比较多时，每次add/set都要重新复制数组，这个代价实在太高。 - 4、数据一致性
CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。写和读分别作用在新老不同容器上，在写操作执行过程中，读不会阻塞但读取到的却是老容器的数据。 - 5、读写分离，效率高
采用读写分离方式，读的效率非常高。CopyOnWriteArrayList的迭代器是基于创建时的数据快照的，故数组的增删改不会影响到迭代器。 - 6、支持随机读
由于CopyOnWriteArrayList底层实现数组，数据存在连续的内存上，因此支持随机读。
4.1.2 CopyOnWriteArrayList的使用
- 1、构造方法
可以构建空对象，也可以根据数组、集合等对象来构建对象。
//构造一个空数组
public CopyOnWriteArrayList()
//将指定集合中的元素copy到数组中
public CopyOnWriteArrayList(Collection<? extends E> c)
//将指定数组中的元素copy到数组中
public CopyOnWriteArrayList(E[] toCopyIn)
- 2、添加元素
添加元素的方式和ArrayList类似，默认添加元素在数组尾部，也可以在指定位置添加。
//将指定的元素列表的结束
public boolean add(E e)
//在列表中指定的位置上插入指定的元素
public void add(int index, E element)
//追加指定集合的所有元素到这个列表的末尾
public boolean addAll(Collection<? extends E> c)
//将指定集合中的所有元素插入到该列表中，从指定位置开始
public boolean addAll(int index, Collection<? extends E> c)
- 3、判断是否包含某个元素
public boolean contains(Object o)
- 4、获取制定位置的元素
public E get(int index)
- 5、返回指定元素的索引
//返回此列表中指定元素的第一个出现的索引
public int indexOf(Object o)
//从指定位置搜索，返回此列表中的第一个出现的指定元素的索引
public int indexOf(E e, int index)
- 6、删除元素
//根据下标删除元素
public E remove(int index)
//删除列表中首次出现的元素
public boolean remove(Object o)
- 7、清空
public void clear()
4.2 相关问题
4.2.1 CopyOnWriteArrayList的迭代器支持fast-fail吗(不支持)
不支持。因为写时复制的存在，CopyOnWriteArrayList在使用迭代器迭代的时候，实际上迭代的是原数组，而不是更新的数组，所以中间如果发生新增、删除元素是在新数组上发生的，所以不影响旧数组的迭代，但是正因为元素的迭代发生在旧数组上，所以迭代时更新的数据是获取不到最新的。
五、Vector
5.1 Vector介绍
public class Vector<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
Vector与ArrayList很相似，也是基于数组来实现，与ArrayList相比，Vector是线程安全的（在每个方法上几乎都增加了synchronized关键字来实现线程间的同步，也正因为如此，Vector的效率会比较低）。可以简单地将Vector理解为线程安全版的ArrayList。
5.1.1 Vector的特点(数组实现/线程安全/默认2倍扩容)
- 1、底层实现与ArrayList相似
Vector底层也是数组，所以也支持随机访问。 - 2、线程安全
Vector与ArrayList最大的不同就在于其是线程安全的，元素修改的方法都是用synchronized关键字修饰的。 - 3、扩容时容量与ArrayList不同
ArrayList不可以设置扩展的容量，默认1.5倍。
Vector可以设置扩展的容量，如果没有设置，默认2倍。 - 4、初始容量与ArrayList不同
ArrayList的无参构造方法中初始容量为0（自动扩容时才扩容为10），而Vector的无参构造方法中初始容量为10。可以简单地理解为这两个容器的初始容量都是10。
5.1.2 Vector的使用
- 1、构造方法
在构造Vector对象时，可以指定初始容量initialCapacity和每次的增量capacityIncrement。当capacityIncrement小于等于0时，数组成倍扩容；当capacityIncrement大于0时，数组扩容时就增加相对的数值。
//构造一个空Vector，其内部数据数组的大小为10 ，标准容量增量为0
public Vector()
//构造具有指定初始容量，并且其容量增量等于0的空Vector
public Vector(int initialCapacity)
//构造具有指定的初始容量和容量增量的空Vector
public Vector(int initialCapacity, int capacityIncrement)
- 2、添加元素
添加的元素的方式和ArrayList类似，不过每个方法上多了synchronized ，保证线程安全。
//将指定的元素追加到此Vector的末尾
public synchronized boolean add(E e)
//在此Vector中的指定位置插入指定的元素
public void add(int index, E element)
//将指定的元素添加到此向量的末尾
public synchronized void addElement(E obj)
//在指定的index位置插入指定元素
public synchronized void insertElementAt(E obj, int index)
- 3、返回此Vector的当前元素个数
public synchronized int capacity()
- 4、清空Vector
public void clear()
- 5、判断是否包含某元素
public boolean contains(Object o)
- 6、获取元素
//返回指定位置的元素
public synchronized E elementAt(int index)
//返回此Vector的第一个元素
public synchronized E firstElement()
//返回此Vector中指定位置的元素
public synchronized E get(int index)
//获取Vector中的最后一个元素
public synchronized E lastElement()
- 7、比较两个Vector是否相等
public synchronized boolean equals(Object o)
- 8、支持for each循环
public synchronized void forEach(Consumer<? super E> action)
- 9、检索元素位置
//返回此Vector中指定元素的第一次出现的索引，如果此向量不包含元素，则返回-1
public int indexOf(Object o)
//返回此Vector中指定元素的第一次出现的索引，从 index向前检索，如果未找到
//该元素，则返回-1
public synchronized int indexOf(Object o, int index)
//返回此Vector中指定元素的最后一次出现的索引，如果此向量不包含元素，则返回-1
public synchronized int lastIndexOf(Object o)
//返回此Vector中指定元素的最后一次出现的索引，从 index开始 ，如果未找到
//元素，则返回-1
public synchronized int lastIndexOf(Object o, int index)
- 10、Vector是否为空
public synchronized boolean isEmpty()
- 11、返回一个迭代器
public synchronized Iterator< E > iterator()
- 12、删除元素
//删除此Vector中指定位置的元素
public synchronized E remove(int index)
//删除此Vector中第一个出现的指定元素，如果Vector不包含该元素，则不会更改
public boolean remove(Object o)
//删除指定索引处的元素
public synchronized void removeElementAt(int index)
- 13、替换元素
//用指定的元素替换此Vector中指定位置的元素
public synchronized E set(int index, E element)
//用指定的元素替换此Vector中指定位置的元素
public synchronized void setElementAt(E obj, int index)
- 14、返回此Vector中的元素数
public synchronized int size()
1.3 自动扩容(默认2倍扩容)
此处以调用addElement方法向Vector中添加元素为例：
public synchronized void addElement(E obj) {
//modCount用于fail-fast机制
modCount++;
//判断在增加一个新的元素后，原数组是否需要扩容
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
private void ensureCapacityHelper(int minCapacity) {
//判断minCapacity是否大于当前容量，如果大于，就调用grow进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//判断capacityIncrement变量是否为0，如果不为0，每次就增加相应的容量；
//为0的话就扩容一倍
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
此处的扩容实现过程与ArrayList大致相似，不同的地方在于判断capacityIncrement变量是否为0，如果不为0，每次就增加相应地的容量；为0的话就扩容一倍。而ArrayList是1.5倍扩容。
六、Stack
6.1 Stack介绍
Stack是栈，是Vector的“窄化”实现。在栈中，可以操作元素的一段叫栈顶（数组尾部），数组的另一端是栈底（数组首部），图示：
在栈中可以进行的操作是入栈和出栈。图示：
6.1.1 Stack的特点(数组实现/线程安全/先进后出)
Stack的特点，可以简单归结为两点：
- 1、在底层数组的一端（栈顶）进行存储/取出元素
普通的数组，一般都可以从两端进行存储和取出元素的操作，但Stack作为Vector的“窄化”实现，严格规定只能在数组的一端进行操作。 - 2、先进后出（LIFO）
Stack中存储的元素，都是后进先出（LIFO，最后入栈的元素最先出栈），因为先存入Stack中的元素存入了Stack底部，在取出该元素时自然是最后一个取出的。 - 3、线程安全
Stack继承于Vector，所以也是线程安全的。
6.1.2 Stack的使用
Stack继承了Vector，所以Vector的方法Stack都有。同时，由于Stack具有先进后出的特点，所以多了一些方法。
- 1、创建一个空栈
public Stack()
- 2、此栈是否为空
public boolean empty()
- 3、查看栈顶的对象，而不从栈中删除
public synchronized E peek()
- 4、删除并返回此堆栈顶部的对象
public synchronized E pop()
- 5、将元素存入到栈的顶部
public E push(E item)
- 6、返回一个对象在此栈上的基于栈顶的相对位置
public synchronized int search(Object o)
这个方法优点特殊，看个示例：
Stack<String> stack = new Stack<String>();
stack.push("A");
stack.push("B");
stack.push("C");
int index = stack.search("A");
if(index != -1) {
System.out.println("元素A在Stack中的位置是：" + index);
}
else {
System.out.println("元素A不在Stack中");
}
运行结果：
元素A在Stack中的位置是：3
这个方法比较特殊，图示：
像上图中的元素“3”，相对于栈顶的位置是1，因此用search检索，返回值就是1。
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
12
0- 0
已为社区贡献12条内容
所有评论(0)