ArrayList

Java 的 List 是非常常用的数据类型。List 是有序的 Collection。Java List 一共三个实现类: 分别是 ArrayList、Vector 和 LinkedList。

ArrayList初始化

List list1 = new ArrayList<>(); 对应的堆栈如下：

注：常量池位于方法区，方法区位于堆内存

1. ArrayList 构造器

/**
 * Constructs an empty list with an initial capacity of ten.
 * 初始化的容量为10
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

elementData :

transient Object[] elementData; // non-private to simplify nested class access

DEFAULTCAPACITY_EMPTY_ELEMENTDATA :

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

可以看出 底层是 Object[]数组，也就是说该数组可以放任何对象。执行完构造函数后，如下图：

static修饰的变量，常驻于方法区，我们不需要new，JVM会提前给我们初始化好，这个特性在实际开发过程中，经常拿来做缓存。

在让人疑惑的Java代码 - Java那些事儿 一文中，我们文中Integer的缓存就是最好的例子。static变量又叫类变量，不管该类有多少个对象，static的变量只有一份，独一无二。

fianl修饰的变量，JVM也会提前给我们初始化好。transient这个关键字告诉我们该对象在序列化的时候请忽略这个元素

继续执行： List list2 = new ArrayList<>();

在new的时候考虑到了缓存，为了避免我们反复的创建无用数组，所有新new出来的ArrayList底层数组都指向缓存在方法区里的Object[]数组。

继续执行 Person person1 = new Person("张三")

2. ArrayList 的 add()方法

看一下 System.arraycopy() 方法，好奇怪，这个方法只有定义，却没有实现，方法用了一个 native 来修饰。native 的方法，是由其它语言来实现的，一般是(C或C++)，所以这儿没有实现代码。这是一个数组拷贝方法，大家还在写 for 循环拷贝数组吗？以后多用这个方法吧，简单又方便还能获得得更好的性能。

public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

• src：要拷贝的数组
• srcPos：要拷贝数组的起始位置
• dest：目标数组
• destPos：目标数组的起始位置
• length：拷贝多少个元素

再回过头来看，add()这个方法

size现在是0，就是把传进来的这个e(这里是person1)，放到 list1 的 elementData[]下标为0的数组里面，同时size加1：

注意看红框里，虽然我们 list1 里的 elementData 数组的长度是 10，但是 size 是1，size 是逻辑长度，并不是数组长度。就一个元素，在堆内存中占了10个位置，好浪费呀，没办法，你要享受ArrayList的便利与丰富的API，就得牺牲一下空间作为代价。

ArrayList底层数组扩容原理

在Java中，数组一但在堆内存中创建，长度是固定的。List 是动态扩容的。

int newCapacity = oldCapacity + (oldCapacity >> 1) ， >> 是移位运算符，相当于 int newCapacity = oldCapacity + (oldCapacity/2) ，但性能会好一些。相当于扩容1.5倍。

当我们在写代码过程中，如果我们大概知道元素的个数，比如一个班级大概有40-50人，我们优先考虑 List<Person> list2 = new ArrayList<>(50) 以指定个数的方式去构造，这样可以避免底层数组的多次拷贝，进而提高程序性能。

ArrayList 删除和时间复杂度

孙七是没办法删除的，根据源码分析下原因：

另一种删除方式：

可以看出 删除的时候是for循环去用 equals()方法 判断，而 Objec 的 equals 方法是 **==** 去比较堆内存的地址，因此没有删掉，要想删除需要我们重写 **equals()** 方法：

我们说一说ArrayList中删除元素的时间复杂度。在ArrayLIst中，如果底层数组长度为n。

当我们用下标方式去删除元素时，如果删除的是最后一个元素，不会触发数组底层的复制，时间复杂度为O(1)。如果删除第i的元素，会触发底层数组复制n-i次，根据最坏情况，时间复杂度为O(n)。

由此看来，在 ArrayList 中删除指定元素的效率不是太高，删除元素会造成底层数组复制，这个问在 LinkedList 有方案解决。

ArrayList 的 add、set、get 和时间复杂度

1. add 方法

在以前的文章里，我们已经看过了add方法的源码，还有一个add方法，我们看一下， public void add(int index, E element) ，从指定位置添加元素：

按照下标把元素添加到指定位置，想必大家都知道，我们直接上源码。

老规矩，我们还是画一画，当执行到System.arraycopy()这个方法时

我看到有些书上写的是依次移动元素到下一格，这种说法不够严谨，所以我再强调一遍，是依次复制插入位置及后面的数组元素，到后面一格，不是移动，因此，复制完后，arr[2],arr[3]指向对一个对象。

在代码执行完这一句

我们debug验证一下。

最后，在堆内存中创建李莫愁这个对象，把arr[2]的引用指向它。

再debug一下

最后我们来说说ArrayLIst这个对象里添加的时间复杂度：

如果我们不指定位置直接添加元素时(add(E element))，元素会默认会添加在最后，不会触发底层数组的复制，不考虑底层数组自动扩容的话，时间复杂度为O(1) ，在指定位置添加元素(add(int index, E element))，需要复制底层数组，根据最坏打算，时间复杂度是O(n)。

2. get 方法

3. set 方法

在ArrayList中，底层数组存/取元素效率非常的高(get/set)，时间复杂度是O(1)，而查找，插入和删除元素效率似乎不太高，时间复杂度为O(n)。

当我们ArrayLIst里有大量数据时，这时候去频繁插入/删除元素会触发底层数组频繁拷贝，效率不高，还会造成内存空间的浪费，这个问题在另一个类：LinkedList里有解决方案。

查找元素效率不高，在HashMap里有解决方案，请关注后续文章。

ArrayList与Vector的区别

首先我们给出标准答案：
1、Vector是线程安全的（加了synchronize锁），ArrayList不是线程安全的。
2、ArrayList在底层数组不够用时在原来的基础上扩展0.5倍，Vector是扩展1倍。
和ArrayList和Vector一样，同样的类似关系的类还有HashMap和HashTable，StringBuilder和StringBuffer，后者是前者线程安全版本的实现。

LinkList

LinkedList 是用链表结构存储数据的，很适合数据的动态插入和删除，随机访问和遍历速度比较 慢。另外，他还提供了 List 接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆 栈、队列和双向队列使用。