IT评测·应用市场-qidao123.com技术社区

标题: ArrayList 和LinkedList的区别比力 [打印本页]

作者: 河曲智叟 时间: 2024-12-30 03:42
标题: 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链表，插入删除快，查找修改慢。适用于频仍添加和删除的场景。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)