今天会是有Offer的一天么：面试时不要再问我ArrayList、LinkedList和CopyOnWriteArrayList的区别了

今天不看源码（想看源码的同学可以自己在本机进行查阅），只是大概说一下这三者的区别。方便大家能够在面试的时候说出这三者的不同。

ArrayList方面 ArrayList简介：

ArrayList是一种以数组实现的List，它实现了List, RandomAccess, Cloneable, Serializable接口。

实现List接口表示它可以支持删除、添加和查找等操作。 实现RandomAccess接口表示它可以支持随机访问（强调一点，并不是因为实现了RandomAccess接口，ArrayList才支持随机访问。RandomAccess只是一个标记接口，接口RandomAccess中内容是空的，只是作为标记使用。）。 实现了Cloneable接口表示ArrayList可以被克隆。 实现了Serializable接口表示ArrayList可以被序列化。 ArrayList中的属性 DEFAULT_CAPACITY =10;表示默认的容量为10。 Object[] EMPTY_ELEMENTDATA ={};表示一个空数组，如果你传入的容量为0时使用，例如：ArrayList list=new ArrayList（0）。 Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA={}；表示一个空的数组，在你不传入容量的时候使用，例如：ArrayList list=new ArrayList（）时使用。在添加第一个元素的时候会初始化默认的大小10. Object[] elementData；用于存储元素的数组。 int size；表示元素的个数。 modCount；对于add操作，remove操作，modCount会进行自增操作。表示ArrayList支持fail-fast。 ArrayList的构造方法（三种） ArrayList list =new ArrayList(int initialCapacity)

传入初始容量，如果小于0就抛出异常；如果大于0，则使用传入的容量；如果等于0就使用EMPTY_ELEMENTDATA空数组。

ArrayList list=new ArrayList（）

不传入初始容量，默认使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组，在添加第一个元素的时候扩容为默认的大小DEFAULT_CAPACITY也就是10。

ArrayList list=new ArrayList（Collection c）

会将Collection集合转化为数组拷贝到element数组中（elementData=c.toArray()）。

ArrayList的各种操作 add（E e）

将元素添加到末尾，平均时间复杂度为O(1);

检查数组是否需要扩容 首先判断elementData是否等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA即是否为空数组，如果是就初始化为默认大小DEFAULT_CAPACITY（10）； 新容量为旧容量的1.5倍；如果发现还是比需要的容量小，则以需要的容量为标准；如果需要的容量已经超过最大的容量（MAX_ARRAY_SIZE），则使用最大的容量；最后以新容量拷贝出一个新的数组。 添加元素。 add（int index，E element）

将元素添加到指定位置，时间复杂度为O(n),因为需要将index后的元素整体向后移动一位。

检查index是否越界。 检查是否需要进行扩容。 将index后的元素整体向后移动一位。 将index位置的元素赋值为element。 size++，表示元素个数增加一。 get（int index）

返回指定位置的元素，时间复杂度为o（1）。

判断index是否越界。 返回index位置的元素。 remove（int index）

删除指定位置的元素，时间复杂度为o（n），因为需要将index后的元素整体向前移动一位。

检查是否越界。 modCount++。 调用System.arrayCopy()方法对于数组本身进行复制，将index后的元素整体向前移动一位。 将最后一个元素设置为null，帮助GC。 返回index位置的旧值。 remove（Object o）

删除指定元素的值，时间复杂为o（n）。

遍历数组，如果删除的元素为null，使用==进行null的比较；如果删除的元素不为null，使用equals（）进行比较。 modCount++； 调用System.arrayCopy()方法将删除元素位置后的所有元素整体向前移动一位。 将最后一个元素设置为null，方便进行GC。 返回true或false表示删除成功或者失败。 ArrayList总结 ArrayList使用数组存储元素，当数组长度不够的时候，会进行扩容，每次扩容为1.5倍。 ArrayList添加元素到尾部，平均时间复杂度为O（1）。 ArrayList添加元素到中间，平均时间复杂度为O（n）。 ArrayList删除尾部的元素，平均时间复杂度为O（1）。 ArrayList从中间删除元素比价慢，平均时间复杂度为O（n）。 ArrayList支持随机访问，时间复杂度为O（1）。
LinkedList相关方面 LinkedList简介：

相较于ArrayList的数组实现，LinkedList是基于双向链表实现的。它实现了List, Deque,Queue， Cloneable, Serializable接口。

实现List接口表示它可以支持删除、添加和查找等操作。 实现Deque和Queue接口表示它可以作为双端队列进行使用，同时也可以作为栈进行使用。 实现了Cloneable接口表示ArrayList可以被克隆。 实现了Serializable接口表示ArrayList可以被序列化。 LinkedList的内部属性 int size表示元素的个数，初始为0。 Node first。表示链表的第一个节点。 Node last。表示链表中的最后一个节点。 Node 是一个双向链表的结构。Node内部包括Node next,Node prev和E item。 modcount表示支持fail-fast。 LinkedList的主要方法 addFirst（E e）

在队首添加元素，时间复杂度为O(1)。

创建一个新的节点newNode。 将newNode赋值给first即first=newNode。 判断newNode是不是第一个新添加的节点，如果是的话，将newNode赋值给last即last=newNode。 size++。 modcount++。 addLast（E e）

在队尾添加元素和addFirst（E e）同理，时间复杂度为O（1）。

add（int index，E element）

在指定位置添加元素，时间复杂度为O（n）。因为需要遍历，查找到插入位置的后继节点。

判断是否越界。 如果index小于size/2,从前往后进行遍历找到插入位置的后继节点；如果index大于size/2,从后往前遍历找到插入位置的后继节点。 按照双线链表在中间插入元素的方法进行插入。 removeFirst（）

删除队首的元素，时间复杂度为O（1）。

如果链表中没有元素，抛出异常。 查找first的后继节点假设是first_next，将first设置为null，方便进行GC。 将first设置为first_next即first=first_next;判断first_next是否为null，如果first_next等于null，则将last设置为null否则将first_next.prev设置为null。 size–。 modcount++。 removeLast（）

删除队尾的元素，时间复杂度为O（1）。原理同上。

remove(int index)

删除指定位置的元素，时间复杂度为O（n），原理同add(int index,E element)。

LinkedList总结 LinkedList是基于双向链表实现，可以作为双端队列，栈来进行使用。 LinkedList在队首队尾删除添加比较快，时间复杂度为O(1)。 LinkedList在链表中间添加删除比较慢，时间复杂度为O（n）。 另外要注意的是，LinkedList是不支持随机访问的，所以访问中间元素的效率比较低。
CopyOnWriteArrayList相关 CopyOnWriteArrayList简介：

CopyOnWriteArrayList是ArrayList的线程安全版本，也是通过数组实现的。相较于ArrayList，CopyOnWriteArrayList使用ReentrantLock重入锁加锁，保证线程安全。每次对数组的修改都完全拷贝一份新的数组来修改，修改完了再替换掉老数组，这样保证了只阻塞写操作，不阻塞读操作，实现读写分离。
CopyOnWriteArrayList实现了List, RandomAccess, Cloneable, Serializable接口。

实现List接口表示它可以支持删除、添加和查找等操作。 实现RandomAccess接口表示它可以支持随机访问（强调一点，并不是因为实现了RandomAccess接口，ArrayList才支持随机访问。RandomAccess只是一个标记接口，接口RandomAccess中内容是空的，只是作为标记使用。）。 实现了Cloneable接口表示ArrayList可以被克隆。 实现了Serializable接口表示ArrayList可以被序列化。 CopyOnWriteArrayList主要的内部属性： ReentrantLock lock=new ReentrantLock();用于修改时进行加锁。 Object[]array用于纯属元素。 CopyOnWriteArrayList主要方法： add（E e）

添加一个元素到末尾。

使用ReentrantLock进行加锁。 使用getArray（）方法获取元素的数组。 新建一个数组大小是原数组的长度加一，并使用Arrays.copyof()方法将原数组拷贝到新数组中。 将添加的元素放到新数组的末尾。 将新数组覆盖原数组。 解锁。 add（int index，E element）

添加元素到制定的位置。

加锁。 判断是否越界，如果越界抛出异常。 如果索引等于数组长度，那就拷贝一个len+1的数组即newElements =Arrays.copyOf(elements,len+1)。 如果索引不等于数组长度，那就新建一个len+1的数组，将索引之前的部分拷贝到新数组索引之前，索引之后拷贝到新数组索引之后的位置。 把索引位置赋值为待添加的元素。 把新数组赋值给当前对象的array属性，覆盖原数组。 解锁。 get（int index）

获取指定位置的元素，时间复杂度为O（1）。

通过getAway（）方法获取数组。 返回指定位置的元素。 remove（int index）

删除指定位置的元素，时间复杂度O（n）。

加锁。 通过getAway（）方法获取旧数组。 如果移除的是最后一位，那么直接拷贝一份n-1的新数组, 最后一位就自动删除。 如果移除的不是最后一位，那么新建一个n-1的新数组。将前index的元素拷贝到新数组中，将index后面的元素往前挪一位拷贝到新数组中。 将新数组赋值给当前对象的数组属性。 解锁并返回旧值。 CopyOnWriteArrayList总结： 对于写操作，CopyOnWriteArrayList使用ReentrantLock重入锁加锁，保证线程安全。 CopyOnWriteArrayList的写操作要先拷贝一份新数组，在新数组中进行修改，修改完了再用新数组去替换旧的数组。 CopyOnWriteArrayList采用读写分离的思想，读操作不加锁，但是写操作需要加锁。 CopyOnWriteArrayList支持随机快速访问，时间复杂度为O(1)。
作者：今天会是有offfer的一天么

面试 offer arraylist