ArrayList 和LinkedList的区别比较
前言
ArrayList和LinkedList的主要区别在于它们的底层数据结构、性能特点以及适用场景。ArrayList和LinkedList从名字分析，他们一个是Array（动态数组）的数据结构，一个是Linked（链表）的数据结构，此外，他们两个都是对List接口的实现。前者是数组队列，相当于动态数组；后者为双向链表结构，也可当作堆栈、队列、双端队列。
一、底层数据结构
ArrayList：基于动态数组实现。它维护一个Object类型的数组来存储元素，可以根据需要自动扩展容量。当元素数量超过当前容量时，ArrayList会进行扩容操作，通常是将现有元素复制到一个新的更大数组中。
LinkedList：基于双向链表实现。每个节点包含存储的元素、指向前一个节点的引用和指向下一个节点的引用。LinkedList不需要预先分配固定大小的空间，可以在链表的头部或尾部灵活地添加或删除元素。
二、性能特点
2.1 查询性能：
ArrayList：通过索引直接访问元素，查询速度非常快，时间复杂度为O(1)。适合需要频繁访问特定位置数据的场景。
LinkedList：由于需要遍历链表来找到指定索引的元素，查询速度较慢，时间复杂度为O(n)。
2.2 添加和删除性能：
ArrayList：在列表中间插入或删除元素时，需要移动后续的所有元素，时间复杂度为O(n)。因此，在列表中间进行添加或删除操作时，LinkedList通常更快。
LinkedList：在头部或尾部添加或删除元素时，只需更改指针引用，时间复杂度为O(1)，因此在这些位置进行操作时更快。
三、空间和耗时效率对比
从利用效率来看，ArrayList自由性较低，因为它需要手动的设置固定大小的变化，但是他的使用比较方便，只需要创建，然后添加数据，通过调用下标进行使用；而LinkedList自由性较高，能够动态的数据量的变化而变化，但是他不便于使用。
ArrayList主要的空间开销在于需要在IList列表预留一定空间；而LinkedList主要空间开销在于需要存储节点信息以及结点指针信息。
ArrayList想要在指定位置插入或删除元素时，主要耗时的是 System.arraycopy 动作，会移动 index 后面所有的元素；LinkedList 主耗时的是要先通过 for 循环找到 index，然后直接插入或删除。这就导致了两者并非一定谁快谁慢。 主要有两个因素决定他们的效率，插入的数据量和插入的位置。
LinkedList需要更多的内存，因为ArrayList的每个索引的位置是实际的数据，而LinkedList中的每个节点中存储的是实际的数据和前后节点的位置。
四、ArrayList 扩容问题
ArrayList 使用一个内置的数组来存储元素，这个数组的起始容量是 10，当数组需要增长时，新的容量按如下公式获得：新容量=(旧容量*3)/2+1，也就是说每一次容量大概会增长50%。这就意味着，如果你有一个包含大量元素的 ArrayList 对象，那么最终将有很大的空间会被浪费掉，这个浪费是由ArrayList的工作方式本身造成的。如果没有足够的空间来存放新的元素，数组将不得不被重新进行分配以便能够增加新的元素。对数组进行重新分配，将会导致性能急剧下降。
五、ArrayList随机访问比LinkedList快的原因
ArrayList从原理上就是数据结构中的数组，也就是内存中的一片空间，这意味着，当我get(index)的时候，我可以根据数组的首地址+偏移量，直接计算出我想访问的第index元素在内存中的位置；而LinkedList可以简单理解为数据结构中的链表，在内存中开辟的不是一段连续的空间，而是每个元素有一个元素和下一个元素地址这样的内存结构，当get(index)时，只能从首元素开始，依次获取下一个元素的地址。上面已经说过，用时间复杂度来表示的话，ArrayList的get(index)是O(1)，而LinkedList是O(n)。
我们编写代码对比测试，说明两者的性能：
1. 定义抽象类，作为List接口的测试，并定义有测试方法
//定义内部抽象类，作为List测试。
private abstract static class Tester {
String name;
int size;
Tester(String name, int size) {
this.name = name;
this.size = size;
}
//定义抽象方法
abstract void test(List a);
}2. 定义一个测试的数组,分别存储获取、遍历、插入和删除的方法
private static final int LOOP_COUNTS = 1000;
private static Tester[] tests = {
//一个测试数组，存储get(随机取)、iteration(顺序遍历)、insert(中间插入)、remove(随机删除)
new Tester("get", 500) {
void test(List a) {
for (int i = 0; i < LOOP_COUNTS; i++) {
for (int j = 0; j < a.size(); j++) {
a.get(j);
}
}
}
},
new Tester("iteration", 500) {
void test(List a) {
for (int i = 0; i < LOOP_COUNTS; i++) {
Iterator it = a.iterator();
while (it.hasNext()) {
it.next();
}
}
}
},
new Tester("insert", 2000) {
void test(List a) {
int half = a.size() / 2;
String s = "test";
ListIterator it = a.listIterator(half);
for (int i = 0; i < size * 10; i++) {
it.add(s);
}
}
},
new Tester("remove", 5000) {
void test(List a) {
ListIterator it = a.listIterator(3);
while (it.hasNext()) {
it.next();
it.remove();
}
}
}
};3. 编写测试方法
public static void test(List a) {
//输出测试的类名称
System.out.println("Testing for --" + a.getClass().getName());
for (int i = 0; i < tests.length; i++) {
fill(a, tests[i].size);//填充空集合
System.out.print(tests[i].name);
long t1 = System.currentTimeMillis();
tests[i].test(a);//进行测试
long t2 = System.currentTimeMillis();
System.out.print("花费时间:" + (t2 - t1) + " ms ，");
}
}
public static Collection fill(Collection c, int size) {
for (int i = 0; i < size; i++) {
c.add(Integer.toString(i));
}
return c;
}4. 调用ArrayList和LinkedList的方法
public static void main(String[] args) {
test(new ArrayList());
System.out.println();
test(new LinkedList());
}5. 运行结果
六、适用场景
ArrayList：适合需要频繁访问特定位置数据的场景，如排行榜、购物车列表等。由于扩容机制的存在，建议在创建时指定初始容量以减少扩容次数。
LinkedList：适合需要频繁在列表开头、中间或末尾进行添加和删除操作的场景。由于其链表结构，插入和删除操作更为高效。
总之， 它们的适用场景：Array数组，查找快，插入删除慢。 适用于频繁查找和修改的场景。Linked链表，插入删除快，查找修改慢。适用于频繁添加和删除的场景。