`
stanxl
  • 浏览: 4414 次
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

ArrayList与LinkedList底层实现与增删查效率比较

 
阅读更多

我们知道ArrayList是List接口的一个实现类,它的特点是查询效率高,增删效率低,线程不安全
原因是因为ArrayList底层是封装了一个数组,它是用数组实现的。
看下图,数组在内存中的存储方式:

这里写图片描述

现在定义一个int[] a数组,假设它的首地址是2000,int类型占4个字节,所以a[0]的首地址是2000,a[1]的首地址就是2004,以此类推….到a[n]
所以上面的这张图,就很形象的解释了,为什么ArrayList的查询效率高,每次只需要一个偏移量就可查到
但是它的增删效率为什么会低呢?
再往下看:

这里写图片描述

如果想在这个数组的中间或是第一项前插入一项,它的插入过程是以迭代的方式,让它后面的每一项依次往后挪,就如图上的要在第二项的位置上插入一项,其实这个过程是比较慢的,如果是你每次都在最后插入,这是个例外,因为它不用再去影响其它的元素,直接插在最后面;当然删也是同一个道理
看完了ArrayList,我们再去研究一下LinkedList
它的特点是:增删效率比较高,而查询效率低
LinkedList是底层用双向循环链表实现的List,链表的存储特点是不挨着,它存储的每个元素分为三段:上一项的地址、下一项的地址、元素的内容,而数组却没有上一项,下一项这种情况 ,因为数组只需要根据一个偏移量,就可以找到下一项或上一项

双向链表的底层结构图:

这里写图片描述

每个元素在内存中的排列像是随机的,中间没有连续性,通过地址来找到上一项或下一项,从图上应该可以理解了
那么现在问题来了,如果查询LinkedList中的某一项,肿么办?
没有好办法,只能把元素全部过一遍,这样就会比较的慢
而它的好处体现在它的增删效率非常的快,为什么呢?
看下面的图解:

这里写图片描述

假如我把右上的一个元素删掉,可以看到左上和右下的两个元素会直接连上,至于它们两个是怎么牵上手的,这里不多讲了,你懂的…………….
同理,在下面增加一个的时候,也是同一个道理,也就是说,当你增加或删除一个元素的时候,在LinkedList里,它最多只会影响两个元素,而不像ArrayList里,当在中间插入一个元素时,它后面的所有的元素都要受到影响,那么这样在一定程度上LinkedList的增删效率就会明显的高于ArrayList的

我们拿代码来证明一下吧:
之前我用过模版方法设计模式来测试过for、while、do-while三种循环的效率问题
这里也可以用到这个设计模式来测试ArrayList与LinkedList的增删查的效率

import java.util.*;
abstract class Template{
    public abstract void test();
    public void template(){
        long start = System.currentTimeMillis();
        test();
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }
}
public class Test{
    public static void main(String[] args){
        Template t1 = new Template(){
            public void test(){
                List list = new ArrayList();
                for(int i = 1; i < 10000 ; i++){
                    //测试ArrayList的增
                    list.add(0,"a");
                }
            }
        };
        Template t2 = new Template(){
            public void test(){
                List list = new LinkedList();
                for(int i = 1; i < 10000 ; i++){
                    //测试LinkedList的增
                    list.add(0,"a");
                }
            }
        };
        Template t3 = new Template(){
            public void test(){
                List list = new ArrayList();
                for(int i = 1; i < 10000 ; i++){
                    list.add("a");
                }
                for(int i = 1; i< 10000 ; i++){
                    //测试ArrayList的查
                    list.get(list.size()/2);
                }
            }
        };
        Template t4 = new Template(){
            public void test(){
                List list = new LinkedList();
                for(int i = 1; i < 10000 ; i++){
                    list.add("a");
                }
                for(int i = 1; i< 10000 ; i++){
                    //测试LinkedList的查
                    list.get(list.size()/2);
                }
            }
        };
        t1.template();
        t2.template();
        t3.template();
        t4.template();
    }
}

输出结果:

这里写图片描述

可以看到最终的结果:
测试ArrayList的增的时间:37ms;
测试LinkedList的增的时间:4ms;(差10倍耶!!!有木有)
测试ArrayList的查的时间:3ms;(差n倍耶!!!有木有)
测试LinkedList的查的时间:77ms;

就先写到这里……

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>

版权声明:本文为博主原创文章,未经博主允许不得转载。

分享到:
评论

相关推荐

    对ArrayList和LinkedList底层实现原理详解

    ArrayList和LinkedList底层实现原理详解 ArrayList 底层实现方式的知识点: 1. ArrayList 底层实现方式:ArrayList 通过数组实现,一旦我们实例化 ArrayList 无参数构造函数默认为数组初始化长度为 10。 2. add ...

    从底层数据结构和CPU缓存两方面剖析LinkedList的查询效率为什么比ArrayList低.docx

    首先,从底层数据结构方面,ArrayList 的查询效率高于 LinkedList,因为 ArrayList 底层数据结构是动态数组,可以根据索引值直接推导出某个索引位置对应的内存地址,而 LinkedList 底层数据结构是双向链表,需要递进...

    关于arraylist和linkedList的区别

    在Java编程语言中,`ArrayList`与`LinkedList`都是`List`接口的具体实现类,用于存储元素集合。虽然它们都实现了同样的接口并且提供了相同的基本功能,但在内部实现机制、性能特点以及适用场景等方面存在显著差异。 ...

    Arraylist与LinkedList区别

    2,随机访问的时候,ArrayList的效率比较高,因为LinkedList要移动指针,而ArrayList是基于 3,索引(index)的数据结构,可以直接映射到。 4,插入、删除数据时,LinkedList的效率比较高,因为ArrayList要移动数据。 ...

    ArrayList Vector LinkedList 区别与用法.

    ### ArrayList、Vector、LinkedList 的区别与用法详解 在Java编程中,选择合适的数据结构对于程序的性能至关重要。本文将深入探讨ArrayList、Vector和LinkedList三种集合类的特点与使用场景,帮助开发者更好地理解...

    ArrayList-LinkedList-源码.rar

    《ArrayList与LinkedList源码解析》 在Java编程中,ArrayList和LinkedList是两种常见的动态数组,它们都是Java集合框架的一部分,提供了对元素存储和操作的功能。本篇将深入探讨ArrayList和LinkedList的内部实现...

    java基础--list(ArrayList、LinkedList、匿名类).docx

    - **核心方法**:LinkedList底层基于双向链表实现,插入和删除元素在任何位置都相对高效,但随机访问速度慢。 - **List与数组互转**:同样支持List与数组之间的转换,但效率相比ArrayList较低。 - **List排序**:...

    Map+List+ArrayList+LinkedList Java源码

    Java编程语言中的`Map`, `List`, `ArrayList` 和 `LinkedList` 是四个核心的数据结构,它们在实际开发中被广泛使用。了解它们的源码对于深入理解Java集合框架的内部工作原理至关重要,尤其是对初学者而言,这有助于...

    深入浅析ArrayList 和 LinkedList的执行效率比较

    ArrayList 和 LinkedList 的执行效率比较 ArrayList 和 LinkedList 是 Java 中两个最常用的 List 实现,分别采用数组和链表作为底层数据结构。它们之间的执行效率比较是开发者们经常关心的问题。本文将深入浅析 ...

    java中容器类ArrayList(底层数组实现)和数组存取效率简单测试

    本篇文章将深入探讨ArrayList的工作原理,以及它与普通数组在存取效率上的差异。 ArrayList的核心是内部的数组对象,它在初始化时会创建一个默认大小(通常是10)的数组。当添加元素超过当前数组容量时,ArrayList...

    ArrayList-LinkedList:ArrayList和LinkedList的完整演示

    在Java编程语言中,ArrayList和LinkedList是两种常用的集合类,它们都实现了List接口,用于存储和操作有序的数据序列。这两个类各有特点,适用于不同的场景。本文将深入探讨ArrayList和LinkedList的内部实现、性能...

    ArrayList的实现原理

    ArrayList是Java集合框架中常用的动态数组,它是List接口的一个实现,允许存储包括null在内的所有元素。ArrayList的主要特点是通过数组来存储元素,提供了丰富的操作方法,包括添加、删除、修改和查询等。下面是...

    java集合类的效率测试

    本测试着重探讨了Java集合类中的Set接口实现类(如HashSet)以及List接口实现类(如ArrayList和LinkedList)在进行增、删、改、查操作时的性能差异。 首先,我们来看ArrayList。ArrayList是一个基于数组实现的列表...

    java中ArrayList 、LinkList区别.doc

    在Java编程语言中,ArrayList和LinkedList都是集合框架中两种重要的数据结构,它们分别基于不同的底层实现,具有不同的特性和性能特点。以下是对这两个类的详细分析: 1. **ArrayList 实现**: - ArrayList 实现了...

    ArrayList底层原理

    ArrayList是Java编程语言中常用的集合类之一,它实现了List接口,并且其底层数据结构基于数组。ArrayList的主要特点是允许用户按索引访问元素,且提供了动态扩容的能力。在深入理解ArrayList的底层原理之前,我们先...

    对java基础集合部分(List、HashMap、HashSet、ArrayList等)底层源码的分析与总结

    LinkedList是双向链表实现,支持快速的插入和删除,但随机访问效率较低。在JDK 1.7和1.8中,其底层源码没有显著变化。 Set接口不允许有重复元素,HashSet是基于哈希表实现的,它不保证元素顺序,但在无冲突的情况下...

    毕业设计源码之ArrayList,LinkList链表接口实现.zip

    在Java编程语言中,ArrayList和LinkedList是两种常用的集合类,它们都实现了List接口,用于存储一系列有序的对象。这篇毕业设计的源码深入探讨了这两种数据结构的实现,并提供了实际的代码示例。以下是对这两个核心...

    深入Java集合学习系列:ArrayList的实现原理

    ArrayList的增删改查操作主要依赖于其底层的数组。添加元素(add)时,如果数组还有空位,则直接插入;否则,进行扩容并复制元素。删除元素(remove)时,需要找到要删除的元素,然后将后续元素前移以填补空位。查找...

    集合底层结构.docx

    ArrayList 和 LinkedList 都实现了 List 接口,它们之间的主要区别在于底层实现和操作效率: 1. ArrayList 底层是一个可变大小的数组,插入和删除操作在数组末尾相对高效,但在中间或开头插入和删除则需要移动大量...

Global site tag (gtag.js) - Google Analytics