文章目录
ArrayList 和 LinkedList 对比
1. 数据结构
- ArrayList 基于数组实现，需要连续内存
- LinkedList 基于链表实现，不需要连续内存
2. 随机访问能力
ArrayList 随机访问能力快（根据下标访问）
LinkedList 随机访问能力慢（沿着链表访问）
源码
ArrayList 实现了 RandomAccess 接口
LinkedList 没有实现 RandomAccess 接口
RandomAccess 接口
代码性能对比
ArrayList 用时比 LinkedList 短
/** * StopWatch '': running time = 17100 ns * --------------------------------------------- * ns % Task name * --------------------------------------------- * 000004000 023% ArrayList * 000013100 077% LinkedList * * StopWatch '': running time = 6600 ns * --------------------------------------------- * ns % Task name * --------------------------------------------- * 000000700 011% ArrayList * 000005900 089% LinkedList * * StopWatch '': running time = 6200 ns * --------------------------------------------- * ns % Task name * --------------------------------------------- * 000000400 006% ArrayList * 000005800 094% LinkedList * * StopWatch '': running time = 8000 ns * --------------------------------------------- * ns % Task name * --------------------------------------------- * 000000300 004% ArrayList * 000007700 096% LinkedList */
注意
如果按 内容 进行查询LinkedList 和ArrayList 时间复杂度相同都是O ( n ) O(n)O(n)
3. 插入、删除性能
ArrayList：尾部插入、删除性能可以，其它部分插入、删除都会移动数据，因此性能会低
LinkedList：头尾插入、删除性能高（中间插入、删除性能低于ArrayList）
测试
头部插入性能对比（LinkedList胜）
/** * StopWatch '': running time = 29000 ns * --------------------------------------------- * ns % Task name * --------------------------------------------- * 000019000 066% ArrayList * 000010000 034% LinkedList * * StopWatch '': running time = 6200 ns * --------------------------------------------- * ns % Task name * --------------------------------------------- * 000004400 071% ArrayList * 000001800 029% LinkedList * * StopWatch '': running time = 4700 ns * --------------------------------------------- * ns % Task name * --------------------------------------------- * 000003200 068% ArrayList * 000001500 032% LinkedList * * StopWatch '': running time = 4900 ns * --------------------------------------------- * ns % Task name * --------------------------------------------- * 000003000 061% ArrayList * 000001900 039% LinkedList * * StopWatch '': running time = 2800 ns * --------------------------------------------- * ns % Task name * --------------------------------------------- * 000001900 068% ArrayList * 000000900 032% LinkedList */
尾部插入性能对比（不相伯仲）
/** * StopWatch '': running time = 35700 ns * --------------------------------------------- * ns % Task name * --------------------------------------------- * 000014800 041% ArrayList * 000020900 059% LinkedList * * StopWatch '': running time = 3500 ns * --------------------------------------------- * ns % Task name * --------------------------------------------- * 000002100 060% ArrayList * 000001400 040% LinkedList * * StopWatch '': running time = 2200 ns * --------------------------------------------- * ns % Task name * --------------------------------------------- * 000001200 055% ArrayList * 000001000 045% LinkedList * * StopWatch '': running time = 4100 ns * --------------------------------------------- * ns % Task name * --------------------------------------------- * 000002800 068% ArrayList * 000001300 032% LinkedList * * StopWatch '': running time = 2600 ns * --------------------------------------------- * ns % Task name * --------------------------------------------- * 000001400 054% ArrayList * 000001200 046% LinkedList */
中间插入性能对比（ArrayList胜）
/** * StopWatch '': running time = 100100 ns * --------------------------------------------- * ns % Task name * --------------------------------------------- * 000042800 043% ArrayList * 000057300 057% LinkedList * * StopWatch '': running time = 32500 ns * --------------------------------------------- * ns % Task name * --------------------------------------------- * 000007000 022% ArrayList * 000025500 078% LinkedList * * StopWatch '': running time = 32700 ns * --------------------------------------------- * ns % Task name * --------------------------------------------- * 000006700 020% ArrayList * 000026000 080% LinkedList * * StopWatch '': running time = 27900 ns * --------------------------------------------- * ns % Task name * --------------------------------------------- * 000005500 020% ArrayList * 000022400 080% LinkedList * * StopWatch '': running time = 38000 ns * --------------------------------------------- * ns % Task name * --------------------------------------------- * 000004500 012% ArrayList * 000033500 088% LinkedList */
4. 内存占用
ArrayList：占用内存少
LinkedList：占用内存多
测试
/** * ArrayList 总大小:[4976],array的数组长度:[1234],所有元素所占字节数::[16000] * LinkedList 总大小:[24080],一个Node节点的大小:[24],所有元素所占字节数:[16000] */
5. 测试代码
测试代码
import org.openjdk.jol.info.ClassLayout; import org.springframework.util.StopWatch; import java.lang.reflect.Field; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.List; import java.util.stream.Collectors; import static day01.sort.Utils.randomArray; @SuppressWarnings("all") // 需要添加VM参数 ：--add-opens java.base/java.util=ALL-UNNAMED public class ArrayListVsLinkedList { public static void main(String[] args) { int n = 1000; int insertIndex = n; for (int i = 0; i < 5; i++) { int[] array = randomArray(n); List<Integer> list1 = Arrays.stream(array).boxed().collect(Collectors.toList()); LinkedList<Integer> list2 = new LinkedList<>(list1); randomAccess(list1, list2, n / 2); // addFirst(list1,list2); // addMiddle(list1, list2, n / 2); // addLast(list1,list2); // arrayListSize((ArrayList<Integer>) list1); // linkedListSize(list2); } } static void linkedListSize(LinkedList<Integer> list) { try { long size = 0; ClassLayout layout = ClassLayout.parseInstance(list); // System.out.println(layout.toPrintable()); size += layout.instanceSize(); Field firstField = LinkedList.class.getDeclaredField("first"); firstField.setAccessible(true); Object first = firstField.get(list); // System.out.println(ClassLayout.parseInstance(first).toPrintable()); long nodeSize = ClassLayout.parseInstance(first).instanceSize(); size += (nodeSize * (list.size() + 2)); long elementSize = ClassLayout.parseInstance(list.getFirst()).instanceSize(); System.out.println("LinkedList 总大小:[" + size + "],一个Node节点的大小:[" + nodeSize + "],所有元素所占字节数:[" + elementSize * list.size() + "]"); } catch (Exception e) { e.printStackTrace(); } } static void arrayListSize(ArrayList<Integer> list) { try { long size = 0; ClassLayout layout = ClassLayout.parseInstance(list); // System.out.println(layout.toPrintable()); size += layout.instanceSize(); Field elementDataField = ArrayList.class.getDeclaredField("elementData"); elementDataField.setAccessible(true); Object elementData = elementDataField.get(list); // System.out.println(ClassLayout.parseInstance(elementData).toPrintable()); size += ClassLayout.parseInstance(elementData).instanceSize(); long elementSize = ClassLayout.parseInstance(list.get(0)).instanceSize(); System.out.println("ArrayList 总大小:[" + size + "],array的数组长度:[" + length(list) + "],所有元素所占字节数::[" + elementSize * list.size() + "]"); } catch (Exception e) { e.printStackTrace(); } } static void randomAccess(List<Integer> list1, LinkedList<Integer> list2, int mid) { StopWatch sw = new StopWatch(); sw.start("ArrayList"); list1.get(mid); sw.stop(); sw.start("LinkedList"); list2.get(mid); sw.stop(); System.out.println(sw.prettyPrint()); } private static void addMiddle(List<Integer> list1, LinkedList<Integer> list2, int mid) { StopWatch sw = new StopWatch(); sw.start("ArrayList"); list1.add(mid, 100); sw.stop(); sw.start("LinkedList"); list2.add(mid, 100); sw.stop(); System.out.println(sw.prettyPrint()); } private static void addFirst(List<Integer> list1, LinkedList<Integer> list2) { StopWatch sw = new StopWatch(); sw.start("ArrayList"); list1.add(0, 100); sw.stop(); sw.start("LinkedList"); list2.addFirst(100); sw.stop(); System.out.println(sw.prettyPrint()); } private static void addLast(List<Integer> list1, LinkedList<Integer> list2) { StopWatch sw = new StopWatch(); sw.start("ArrayList"); list1.add(100); sw.stop(); sw.start("LinkedList"); list2.add(100); sw.stop(); System.out.println(sw.prettyPrint()); } public static int length(ArrayList<Integer> list) { try { Field field = ArrayList.class.getDeclaredField("elementData"); field.setAccessible(true); return ((Object[]) field.get(list)).length; } catch (Exception e) { e.printStackTrace(); return 0; } } }
工具类
import java.util.Random; public class Utils { public static void swap(int[] array, int i, int j) { int t = array[i]; array[i] = array[j]; array[j] = t; } public static void shuffle(int[] array) { Random rnd = new Random(); int size = array.length; for (int i = size; i > 1; i--) { swap(array, i - 1, rnd.nextInt(i)); } } public static int[] randomArray(int n) { int lastVal = 1; Random r = new Random(); int[] array = new int[n]; for (int i = 0; i < n; i++) { int v = lastVal + Math.max(r.nextInt(10), 1); array[i] = v; lastVal = v; } shuffle(array); return array; } public static int[] evenArray(int n) { int[] array = new int[n]; for (int i = 0; i < n; i++) { array[i] = i * 2; } return array; } public static int[] sixteenArray(int n) { int[] array = new int[n]; for (int i = 0; i < n; i++) { array[i] = i * 16; } return array; } public static int[] lowSameArray(int n) { int[] array = new int[n]; Random r = new Random(); for (int i = 0; i < n; i++) { array[i] = r.nextInt() & 0x7FFF0002; } return array; } }
代码说明
day01.list.ArrayListVsLinkedList#randomAccess 对比随机访问性能
day01.list.ArrayListVsLinkedList#addMiddle 对比向中间插入性能
day01.list.ArrayListVsLinkedList#addFirst 对比头部插入性能
day01.list.ArrayListVsLinkedList#addLast 对比尾部插入性能
day01.list.ArrayListVsLinkedList#linkedListSize 打印一个 LinkedList 占用内存
day01.list.ArrayListVsLinkedList#arrayListSize 打印一个 ArrayList 占用内存
