先看再点赞，给自己一点思考的时间，思考过后请毫不犹豫微信搜索【沉默王二】，关注这个靠才华苟且的程序员。
本文 GitHub github.com/itwanger 已收录，里面还有技术大佬整理的面试题，以及二哥的系列文章。
ArrayList 和 LinkedList 是 List 接口的两种不同实现，并且两者都不是线程安全的。但初学者往往搞不清楚它们两者之间的区别，不知道什么时候该用 ArrayList，什么时候该用 LinkedList，那这篇文章就来传道受业解惑一下。
ArrayList 内部使用的动态数组来存储元素，LinkedList 内部使用的双向链表来存储元素，这也是 ArrayList 和 LinkedList 最本质的区别。
注：本文使用的 JDK 源码版本为 14，小伙伴如果发现文章中的源码和自己本地的不同时，不要担心，不是我源码贴错了，也不是你本地的源码错了，只是版本不同而已。
由于 ArrayList 和 LinkedList 内部使用的存储方式不同，导致它们的各种方法具有不同的时间复杂度。先来通过维基百科理解一下时间复杂度这个概念。
在计算机科学中，算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大 O 符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 n （必须比 大）的输入，它至多需要 的时间运行完毕，那么它的渐近时间复杂度是 。
对于 ArrayList 来说：
1）get(int index) 方法的时间复杂度为 ，因为是直接从底层数组根据下标获取的，和数组长度无关。
public E get(int index) {Objects.checkIndex(index, size);
return elementData(index);
}
这也是 ArrayList 的最大优点。
2）add(E e) 方法会默认将元素添加到数组末尾，但需要考虑到数组扩容的情况，如果不需要扩容，时间复杂度为 。
public boolean add(E e) {modCount++;
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
如果需要扩容的话，并且不是第一次（oldCapacity > 0）扩容的时候，内部执行的 Arrays.copyOf() 方法是耗时的关键，需要把原有数组中的元素复制到扩容后的新数组当中。
private Object[] grow(int minCapacity) {int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
3）add(int index, E element) 方法将新的元素插入到指定的位置，考虑到需要复制底层数组（根据之前的判断，扩容的话，数组可能要复制一次），根据最坏的打算（不管需要不需要扩容，System.arraycopy() 肯定要执行），所以时间复杂度为 。
public void add(int index, E element) {rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}