ArrayList和LinkedList的区别

ArrayList和LinkedList的区别

ArrayList
  1.基于数组，需要连续内存
  2.随机访问快(指根据下标访问，不是根据内容访问)
  3.尾部插入，删除性能可以，其它部分插入，删除都会移动数据，因此性能会低
  4.可以利用cpu缓存，局部性原理

linkedList
  1.基于双向链表，无需连续内存
  2.随机访问慢(要沿着链表遍历)
  3.头尾插入删除性能高
  4.占用内存多
  关于往头部，中间，尾部add的 demo代码：

  public static void main(String[] args) {
        int n = 1000;
        int insertIndex = n;
        for (int i = 0; i < 1; i++) {
           //randomArray生面随机数组，这里意思是1000个随机数
            int[] array = randomArray(n);
            List list1 = 
        Arrays.stream(array).boxed().collect(Collectors.toList());
            linkedList list2 = new linkedList<>(list1);
            addFirst(list1,list2);
            addMiddle(list1, list2, n / 2);
            addLast(list1,list2);
            arrayListSize((ArrayList) list1);
            linkedListSize(list2);
        }
    }
 private static void addMiddle(List list1, linkedList 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 list1, linkedList 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 list1, linkedList 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());
    }

执行往头部addFirst插入的运行截图如下：linkedList的效率比ArrayList的效率好很多

Connected to the target VM, address: '127.0.0.1:59369', transport: 'socket'
StopWatch '': running time = 81898 ns
---------------------------------------------
ns         %     Task name
---------------------------------------------
000073599  090%  ArrayList
000008299  010%  linkedList

Disconnected from the target VM, address: '127.0.0.1:59369', transport: 'socket'

Process finished with exit code 0

执行往中间addMiddle插入的运行结果: linkedList效率并不是很高，因为插入前要遍历

Connected to the target VM, address: '127.0.0.1:62319', transport: 'socket'
StopWatch '': running time = 5230109099 ns
---------------------------------------------
ns         %     Task name
---------------------------------------------
1677949199  032%  ArrayList
3552159900  068%  linkedList

往最后插入运行截图：

ns         %     Task name
---------------------------------------------
000027600  087%  ArrayList
000004200  013%  linkedList