一说到ArrayList和LinkedList,大部分Java开发程序员就会想到:
1. ArrayList 底层 结构是数组,查询快,增删慢。
2. LinkedList 底层结构是链表,增删快,查询慢。
网上关于ArrayList和LinkedList的区别和解释有许多博客,类似的解释我就不做说明了。
我想搬运一下,最近看到的一种关于数组和链表的解释,对本人有一定的启发。
内存的存储形式分:
内存存储形式
连续存储
离散存储
数组
链表
ArrayList的底层是数组,而数组存储形式是连输存储的,LinkedList 底层是链表,链表是离散存储的,为了能把相关联的数据连续起来,那么实现链表就必须在前一块数据的存储空间中记录下下一块的数据存储空间的地址,这样才能达到所有的数据环环相扣,联系起来成为一个整体。
下面的说明性解析,建议读者先看一下ArrayList和LinkedList的底层源码,这样便于理解下面说的内容。
以下个人理解(请各位带着放大镜查看,欢迎指正)
现在回过头来看:
- ArrayList的查询快,是基于它数据的存储形式是连续的,当知道第一个元素的下标时,我们就能很快根据已知元素的位置,而LinkedList的数据的存储形式时离散存储的,数据是非连续(离散)的,我们需要找到第一个元素后才能拿到下一个元素的地址,才能跳到下一个元素再拿到下一个元素,如此反复操作,所花的时间是远大于连输存储数据查询时间所花的时间,从这一点也能说明LinkedList查询数据慢,而ArrayList查询快的原因。
- ArrayList 增删慢,由于数据是连续存储的,那么插入和删除势必导致部分或整体数据的位置偏移,仅仅插入一个数据,却需要操作非插入元素的其他元素的位置的变动,而LinkedList 增删快,是因为数据存储是离散的链表结构,增加元素无需操作其他元素,只需将需要插入元素,然后将上一块元素和下一块元素的关于下一块数据的存储地址变更换成插入元素的存储地址即可,删除操作同理,避免操作非插入或删除的元素上下元素的其他元素,效率上远远大于ArrayList增删操作。
以上内容是阅读相关资料后的个人理解,欢迎各位指正,共同进步。
转载请显示注明本博客原文地址,谢谢!
声明:本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。