设计一个手机网站平面多少钱,企业crm销售管理系统,小米发布会后多久可以买到新机,dede如何生成网站源码前言
ArrayList和LinkedList的主要区别在于它们的底层数据结构、性能特点以及适用场景。ArrayList和LinkedList从名字分析#xff0c;他们一个是Array#xff08;动态数组#xff09;的数据结构#xff0c;一个是Linked#xff08;链表#xff09;的数据结构#x…前言
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)/21也就是说每一次容量大概会增长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链表插入删除快查找修改慢。适用于频繁添加和删除的场景。
