锐客网

  1. 首页 > it技术 > >

【Java】ArrayList、LinkedList原理及相关面试题

ArrayList、LinkedList都是List的实现类。
一、数据结构 ArrayList是数组实现的，LinkedList是链表。
ArrayList内部有个Object[]类型的数组elementData保存数据，同时有个整型size表示列表的大小。如果没有特别设置，elementData数组初始化长度为10，随着使用可能会进行扩容。
LinkedList内部有个Node类，代表一个链表节点。同时使用整型size来保存链表的长度。
二、增删改查 1. 增 往ArrayList添加数据时，会先检查是否需要扩容。
当size == elementData.length时，表示数据数量已经超过了数组容量，需要进行扩容；扩容后的新数组长度为原数组的1.5倍。
当扩容检查完毕后，将新添加进来的值赋给elementData[size]，并将size++；
往LinkedList中添加数据时，会创建一个新的Node节点，直接添加到链表尾部。
2. 删 ArrayList：
将序号为i的元素删除时，ArrayList会将elementData中序号i + 1 .. size - 1的元素移动到i .. size - 2，即将右侧所有元素往左移动一位；这一步的时间复杂度为O(n)。
LinkedList：
在链表中删除这个节点。
3. 改 ArrayList：
直接修改数组元素。
LinkedList：
循环i次找到这个元素，并修改。这一步的时间复杂度为O(n)。
4. 查 ArrayList：
直接查找数组下标。
LinkedList：
循环i次找到这个元素。这一步的时间复杂度为O(n)。
5. 小结 ArrayList与LinkedList效率对比：
ArrayList查找元素快，而删除元素慢；
LinkedList查找元素慢，而删除元素快。
三、相关面试题 1. ArrayList添加元素和删除元素的效率如何？时间复杂度是多少？ArrayList和LinkedList如何选择？ 【【Java】ArrayList、LinkedList原理及相关面试题】添加元素
如果添加元素到List末尾，即直接调用add(E)方法，且不用扩容的话，那么时间复杂度为O(1)；
如果要扩容的话，时间复杂度为O(n)；
如果添加元素到List中间，即调用add(index, E)方法，需要将该位置右侧所有的元素向右移动一位。所以时间复杂度决定于插入的位置，越往右越快，最好时间复杂度为O(1)，最坏为O(n)，平均O(n)。
删除元素
删除元素会使数组中右侧的所有元素往左移动一位，用时取决于删除元素的位置，越往右越快；最好时间复杂度为O(1)，最坏为O(n)，平均为O(n)。
事实上，ArrayList扩容消耗的时间是很小的，主要耗时的问题出在往数组添加或删除元素，并且这个耗时取决于元素在数组中的位置，越往左耗时越长。
由于LinkedList中的元素需要额外包裹Node节点，并且LinkedList在指定序号增删元素的时间复杂度也是O(n)（需要先查找），所以绝大多数情况下优先采用ArrayList，除非经常在奇怪的位置插入元素，比如一会儿头插，一会儿尾插，这种情况用LinkedList比较好。如果插入和删除操作都在List的末尾，使用ArrayList即可。
2. ArrayList线程安全吗？为什么？如何解决多线程问题？ ArrayList线程不安全，因为方法没有同步，操作没有原子性，在多线程环境下会出现变量读写异常。比如size++这一步是非原子的，如果两个线程同时执行，可能两个线程分别读了size的值，再分别执行size++，最后size的值变成了size+1而非size+2。
多线程环境使用CopyOnWriteArrayList保证线程安全，或者使用Collections.synchronizedList(list)，或者给有多线程的操作加锁，或者使用Vector。
3. ArrayList与Vector的区别？ArrayList效率高于Vector吗？ Vector是线程安全版的ArrayList，两者原理相同，不过Vector的方法使用synchronized修饰。另外，Vector扩容是2倍，ArrayList是1.5倍。
理论上，单线程下Vector的效率是低于ArrayList的，因为使用synchronized加锁必定影响效率。
然而实际情况下，两者的效率相差无几，这是因为JVM对synchronized加锁进行了优化，在单线程的条件下其对效率的影响可以忽略不计（【Java】锁升级）。
甚至，由于Vector扩容更快的缘故，以下代码Vector运行时间比ArrayList更短：

List arrList = new ArrayList<>(); List vector = new Vector<>(); long start = System.nanoTime(); for (int i = 0; i < 10000000; i++) { arrList.add(1); } System.out.println("arrlist use " + (System.nanoTime() - start)); start = System.nanoTime(); for (int i = 0; i < 10000000; i++) { vector.add(1); } System.out.println("vector use " + (System.nanoTime() - start));

    推荐阅读


    上一篇：【塔罗案例】我未来全年的感情运势！

    下一篇：杀神白起