ArrayList理解

1.什么是ArrayList?

ArrayList集合是Collection和List接口的实现类，底层的数据结构可变的Object数组，对ArrayList的所有操作都是通过数据来实现的，数据结构特点是增删慢、查询快。

// 默认的容量大小（常量）

 private static final int DEFAULT_CAPACITY = 10; 



// 定义的空数组（final修饰，大小固定为0） 

private static final Object[] EMPTY_ELEMENTDATA = {};



 // 定义的默认空容量的数组（final修饰，大小固定为0）

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; 



// 定义的不可被序列化的数组，实际存储元素的数组

 transient Object[] elementData;  



// 数组中元素的个数 

private int size;

2.ArrayList线程安全吗？

Java高频面试题：谈谈你对ArrayList的理解？ - 知乎 (zhihu.com)

ArrayList是线程不安全的。

当开启多个线程操作List集合，向ArrayList中增加元素，同时去除元素。最后输出list中的所有数据，会出现几种情况：

①有些元素输出为Null；②数组下标越界异常。

有两种解决方案：

第一种是选用线程安全的数组容器是Vector，它将所有的方法都加上了synchronized。

public static Vector<Object> vector= new Vector<Object>(); 

第二种是用Collections.synchronizedList将ArrayList包装成线程安全的数组容器。

List<String> list = Collections.synchronizedList(new ArrayList<>());

为什么ArrayList线程不安全，我们还使用它？

因为大多数的场景中，查询操作使用频率高，增删操作的使用频率低。如果涉及频繁的增删，可以使用LinkedList，实际开发过程中还是ArrayList使用最多的。 不存在一个集合既查询效率高，又增删效率高，还线程安全的，因为数据结构的特性就是优劣共存的，想找个平衡点很难，牺牲了性能，那就安全，牺牲了安全那就快速。

3.ArrayList实现

private static final int DEFAULT_CAPACITY = 10;

private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient Object[] elementData;

private int size;

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

• DEFAULT_CAPACITY：默认容量为 10。
• EMPTY_ELEMENTDATA：通过构造方法指定的容量为 0 时，使用该空数组。
• DEFAULTCAPACITY_EMPTY_ELEMENTDATA：调用无参构造方法时，使用该数组。
• elementData：保存添加的元素，在 ArrayList 被序列化时，该属性不会被序列化。
• size：ArrayList 保存的元素个数。
• MAX_ARRAY_SIZE：ArrayList 能够容纳的最大长度，231 - 1 - 8。

1.数组缓冲区，数组列表的元素存储在其中。数组列表的容量是这个数组缓冲区的长度。任何带有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空数组列表在添加第一个元素时将被扩展为DEFAULT_CAPACITY。

transient Object[] elementData;

/** * Constructs an empty list with an initial capacity of ten. * 构造一个容量为 10 的空列表，当第一次添加元素时，elementData 会扩容到 10。 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

区分java7，在创建容器的时候底层并不会立刻创建，只有在第一次调用add方法的时候才会创建一个长度为10的数组

4.元素操作的基本方法

方法名	说明	时间复杂度
E get(int index)	返回指定索引的元素	O(1)
E set(int index, E element)	替换指定索引的元素，返回旧元素	O(1)
boolean add(E e)	向列表的末尾添加元素	O(1)
void add(int index, E element)	在指定位置插入元素	O(N)
E remove(int index)	删除指定位置的元素，返回旧元素	O(N)
boolean remove(Object o)	删除列表中与给定对象相同的元素	O(N)
boolean contains(Object o)	判断列表中是否包含指定元素	O(N)
int indexOf(Object o)	返回指定元素在列表中的索引	O(N)

其中，contains 方法直接 返回 indexOf(o) >= 0 。

5.迭代器方法

iterator()

返回一个迭代器，如果在迭代器遍历过程中调用了列表的 add，remove 等方法，会抛出 ConcurrentModificationException 。

public Iterator<E> iterator() {
    return new Itr();
}

listIterator()

ListIterator是Iterator的子接口。

返回一个迭代器，该迭代器可以向前后两个方向遍历元素。ListIter 继承于 Iter 。

public ListIterator<E> listIterator() {
    return new ListItr(0);
}

listIterator(int index)

返回一个从指定位置开始的迭代器。

public ListIterator<E> listIterator(int index) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}

6.扩展的方法

增加容量，以确保它至少可以容纳由最小容量参数指定的元素数量。@param minCapacity期望的最小容量

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // 溢出
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

扩容就是数组拷贝,将旧数组中的数据拷贝到新数组里,而新数组的长度为原来长度的1.5倍。 ArrayList支持缩容,但不会自动缩容,即便是ArrayList中只剩下少量数据时也不会主动缩容。如果我们希望缩减ArrayList的容量,则需要自己调用它的trimToSize()方法,届时数组将按照元素的实际个数进行缩减。

7.ArrayList频繁扩容导致添加性能急剧下降，如何处理？

使用ArrayList时，可以 new ArrayList(大小)构造方法来指定集合的大小，以减少扩容的次数，提高写入效率。

8.ArrayList用来做队列合适么？

队列一般是FIFO（先入先出）的，如果用ArrayList做队列，需要在数组尾部追加数据，数组头部删除数组，反过来也可以。但是无论如何总会有一个操作会涉及到数组的数据搬迁，这个是比较耗费性能的。

虽然ArrayList不适合做队列，但是数组是非常合适的。比如ArrayBlockingQueue内部实现就是一个环形队列，它是一个定长队列，内部是用一个定长数组来实现的。另外著名的Disruptor开源Library也是用环形数组来实现的超高性能队列，具体原理不做解释，比较复杂。简单点说就是使用两个偏移量来标记数组的读位置和写位置，如果超过长度就折回到数组开头，前提是它们是定长数组。

9.ArrayList和LinkedList的区别？

ArrayList：

• 基于动态数组的数据结构
• 对于随机访问的get和set，ArrayList要优于LinkedList
• 对于随机操作的add和remove，ArrayList不一定比LinkedList慢 (ArrayList底层由于是动态数组，因此并不是每次add和remove的时候都需要创建新数组)

*LinkedList：*

• 基于双向链表的数据结构（双向链表遍历效率可能优于单向链表，因为双向链表可以在查找元素时，判断靠近头还是靠近尾，如果靠近头从头开始找，如果靠近尾从尾开始找）
• 对于顺序操作，LinkedList不一定比ArrayList慢
• 对于随机操作，LinkedList效率明显较低