原创

LinkedList Vs ArrayList


这道题应该说是一道经典的面试题,很多人说arrayList查询快,增删慢,LInkedList反之,但事实真的是这样嘛

我们先来看它们两个的底层实现

ArrayList

    transient Object[] elementData; 

LinkedList

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

ArrayList底层是一个数组,而LinkedList是一个双向链表,根据数组和链表的特性,乍一看,好像上面那句“arrayList查询快,增删慢,LinkedList反之”好像没错,确实是这样,站在单纯数据结构,单纯特定操作这就话是没错的,但对于一个集合来说,就有点不全面了

首先先确定一点,我们说的查询,是随机访问,也就是根据某一个索引去找元素,而不是根据元素去找,如果是根据元素去找,就没有讨论的必要了,无论是数组还是链表都要一个一个去找,都是o(n)的复杂度,那么确定这一点之后,我们来分别讨论增删改查的性能比较

查询

查询的话,肯定是ArrayList快的,因为数组嘛,可以根据下标去直接找到对应index,当然很快,时间复杂度为O(1),链表就不一样了,必须得挨个去数,时间复杂度O(n)

新增

这里的新增其实分为好几种情况

第一,尾插法,尾插法其实也就是我们平时用的最多的,就是add()方法嘛,对于数组,不考虑扩容的情况下,直接向尾部增加一个元素,并不会涉及其他元素移动,当然了,链表是一样的,所以尾插法,arraylist和linkedlist打个平手

第二,头插法,头插法的话,对于linkedlist直接新增一个元素,设置为头结点,并且指向原先的头结点就可以了,但arraylist就不一样了,把元素插入到头部后,他会移动整个数组,这个操作是非常耗费性能的,所以这一局linkedlist胜

第三,中间插入,对于arraylist,他可以直接定位到index,接着将元素插入进去,但他还是会移动后面元素,也是比较耗费性能的,linkedlist的话,他首先要遍历到index,再进行插入,虽然不需要移动元素,但需要一个o(n)的查询操作,所以两者的插入,是不能简单说谁快谁慢的,那我们就来测试一下

public static void main(String[] args) {
        array();
        linked();
    }
    public static void linked() {
        List<Integer> linked = new LinkedList<>();

        for (int i = 0; i < 10000; i++) {
            linked.add(i);
        }

        long t = System.nanoTime();
        linked.remove(5000);

        System.out.println(System.nanoTime() - t);
    }

    public static void array() {
        List<Integer> array = new ArrayList<>();
        for (int i = 0; i < 10000; i++) {
            array.add(i);
        }

        long l = System.nanoTime();
        array.remove(5000);
        System.out.println(System.nanoTime() - l);
    }

这里是10000个元素,往中间删除(新增同理),输出如下

15900
47400
Process finished with exit code 0

可以看见,arraylist是比linkedlist要快的,所以以后不要说linkedlist增删比arraylist快了,linkedlist的作者在推特上都说linkedlist性能大多数操作都是不如arraylist的

我们再来从以下方面讨论讨论,代码除了性能,还有什么是最重要的呢,当然是内存啦

那么arraylist和linkedlist两者在相同元素个数的情况下,你觉得谁的内存占有要大呢 毫无疑问,linkedlist,为什么呢,我从两点讨论

1.本身的数据结构

linkedlist是一个双向链表

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

他每一个节点都会去存储他的前驱和后继节点的引用,所以他的内存占有肯定是比arraylist要大的

2.内存离散

我们都知道数组元素是挨在一起的,而链表不一样,所以他的内存其实是离散的,当然内存的利用率就低咯

哈哈,根据上面的,好想我就把linkedlist说的一无是处一样,当然啦,他也有他自己的应用场景,比如头插法,要把元素不断加入到集合首部,那linkedlist毫无疑问是吊打arraylist的,

除此之外,linkedlist在API层面也是比ArrayList丰富不少的,他除了实现了List接口外,他还实现了Deque接口

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>

里面实现了很多额外的方法,比如队列,栈的一些常用方法,push,pop,offer之类的,

看完这篇文章,有没有对两者有一个新的认识呢

Java
  • 作者:刘柄岐
  • 发表时间: 2022-08-23 21:10
  • 版权声明:自由转载-非商用