结论：单纯的添加、随机读取和遍历使用 ArrayList （单纯使用List作为存储数据结构时使用 ArrayList），如果有大量的随机写入和删除操作则使用 LinkedList
ArrayList 和 LinkedList 都实现了集合中 List 接口。LinkedList 使用双链表实现。 ArrayList 通过一个动态数组实现。
LinkedList 的方法时间复杂度
get：O（n）-（平均 n / 4 步）
add：O（1）
add（指定位置）：O（n）（平均n / 4步）-（首位添加是O（1））
remove(指定位置) ：O（n）-（平均n / 4步）
Iterator.remove：O（1）
ListIterator.add：O（1）
注意：许多操作平均需要n / 4步，最佳情况下的步数为常数（例如，索引= 0），最坏情况下为n / 2步（列表中部）
ArrayList 的方法时间复杂度
get（指定位置）：O（1）
add：O（1）首尾，但O（n）最坏的情况，超出容量时数组必须调整大小并复制
add（指定位置）：O（n）-（平均n / 2步）
remove（指定位置）：O（n）-（平均n / 2步）
Iterator.remove（）：O（n）-（平均n / 2步）
ListIterator.add（）：O（n）-（平均n / 2步）
注意：许多操作平均需要n / 2步，在容量内是最佳情况O（1），超容需要复制，最差情况O（n）
10w级读写测试：
public static void main(String[] args) throws InterruptedException {
LinkedList<Integer> linkedList = new LinkedList<>();
ArrayList<Integer> arrayList = new ArrayList<>();
// 插入数据测试
long startLinked = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
linkedList.add(i);
}
long endLinked = System.currentTimeMillis();
System.out.println("添加数据 LinkedList: " + (endLinked - startLinked) + " 毫秒");
Thread.sleep(1000);
long startArray = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
arrayList.add(i);
}
long endArray = System.currentTimeMillis();
System.out.println("添加数据 ArrayList: " + (endArray - startArray) + " 毫秒");
Thread.sleep(1000);
// 使用遍历访问数据
long startL = System.currentTimeMillis();
for (int i = 0; i < linkedList.size(); i++) {
int tmp = linkedList.get(i);
}
long endL = System.currentTimeMillis();
System.out.println("查询数据 LinkedList: " + (endL - startL) + " 毫秒");
Thread.sleep(1000);
long startA = System.currentTimeMillis();
for (int i = 0; i < arrayList.size(); i++) {
int tmp = arrayList.get(i);
}
long endA = System.currentTimeMillis();
System.out.println("查询数据 ArrayList: " + (endA - startA) + " 毫秒");
}
结果（时间有浮动，但是LinkedList 整体比 ArrayList 慢）：
添加数据 LinkedList: 11 毫秒
添加数据 ArrayList: 0 毫秒
查询数据 LinkedList: 4852 毫秒
查询数据 ArrayList: 0 毫秒
