ArrayList 、 LinkedList 的优缺点和区别

客官°小女子只卖身不卖艺 2021-12-09 16:07 418阅读 0赞

ArrayList 与 LinkedList 区别

1、ArrayList

我们把他ArrayList拆开看，Array 和 List；说明他首先是一个数组，在Java中，创建数组时，会在内存中分配一块连续的空间，然后与数据存储的时候，会将数据按照顺序存储在这块连续的内存中，当要读取数据时，需要提供数组中的索引，然后数组根据索引内存中的数据取出来，返回给调用者。在Java中并不是所有的数据都能存到数组中，只有相同类型的数据才能一起存储到数组中；

优点：在存储时，会在内存中分配一块连续的空间，

读取数据时，CPU缓存会把一片连续的内存空间读入，因为数组结构是连续的内存地址，所以数组全部或者部分元素被连续存在CPU缓存里面，这样读取就很快；

CPU缓存比内存快，内存又比磁盘读取快；

无论是在已知下标的情况下进入单个元素查询，还是整体遍历，数组都比链表存在明显优势；

缺点：申请的内存大小固定，不适合动态存储，不方便动态添加、删除，

在连续内存中做增删时，后面所有的存储地址往前移动，以保持连续性，这样比较耗时间 ；在ArrayList中，删除元素后，会调用System.arraycopy()方法，数组复制，耗时；

源码分析参考，基于jdk1.8 ，参考帖子：

[https://blog.csdn.net/zxt0601/article/details/77281231][https_blog.csdn.net_zxt0601_article_details_77281231]

[https://www.cnblogs.com/ysocean/p/8622264.html][https_www.cnblogs.com_ysocean_p_8622264.html]

2、LinkedList

链表是一种屋里存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点组成，结点可以在运行时动态生成，LinkedList中有两个指针，前指针和后指针，是一个双向链表；

链表的增删由于不需要移动底层数组数据，其底层是链表实现的，只需要修改链表节点指针，所以效率较高。

通过下标获取某个节点的时候，会根据index处于前半段还是后半段进行一次折半，以提升查询效率；而改和查，都需要先定位到目标节点，所以效率较低；

Node<E> node(int index) {
            // assert isElementIndex(index);
    
            if (index < (size >> 1)) {
                Node<E> x = first;
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            } else {
                Node<E> x = last;
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
            }
        }

优点：可动态添加删除大小可变 ，内存可能是不连续内存，链式存储。

缺点：节点是分散在堆空间里面的，这时候CPU缓存帮不上忙，只能是去读取内存；

源码分析参考，基于jdk1.8 ，参考帖子：

[https://blog.csdn.net/zxt0601/article/details/77341098][https_blog.csdn.net_zxt0601_article_details_77341098]

[https_blog.csdn.net_zxt0601_article_details_77281231]: https://blog.csdn.net/zxt0601/article/details/77281231
[https_www.cnblogs.com_ysocean_p_8622264.html]: https://www.cnblogs.com/ysocean/p/8622264.html
[https_blog.csdn.net_zxt0601_article_details_77341098]: https://blog.csdn.net/zxt0601/article/details/77341098