ArrayList和LinkedList对比

BlackFlagBin 发布于2019-08-16 11:06 / 2238人阅读

摘要：底层是链表实现的，对顺序访问进行了优化，插入和删除元素时间复杂度较好，但是随机访问需要遍历元素，所以效率比差。

次序是List最重要的特点；它保证维护元素特定的顺序
简单介绍：
ArrayList底层的实现是数组，随机访问所以用下标访问的速度比较快，但是插入和删除元素，会有移动元素的开销，所以速度比LinkedList差。
LikedList底层是链表实现的，对顺序访问进行了优化，插入和删除元素时间复杂度较LinkedList好，但是随机访问需要遍历元素，所以效率比ArrayList差。

例子如下：

import org.junit.Test;  
import java.util.ArrayList;  
import java.util.LinkedList;  
import java.util.List;  
  
public class ListAddTest {  
  
    List arrList = new ArrayList();  
    List lnkList = new LinkedList();  
  
    void add(List list) {  
  
        long startTime = System.currentTimeMillis();  
        System.out.println("开始的时间：" + startTime);  
        for (int i = 0; i < 100000; i++) {  
            list.add(0, String.valueOf(i));  
        }  
        long endTime = System.currentTimeMillis();  
        System.out.println("结束的时间：" + endTime);  
        System.out.println("总耗时：" + (endTime - startTime));  
  
    }  
  
    @Test  
    public void addTimeTest() {  
  
        add(arrList);  
        // 开始的时间：1487783199226  
        // 结束的时间：1487783199741  
        // 总耗时：515  
  
        add(lnkList);  
        // 开始的时间：1487783199741  
        // 结束的时间：1487783199756  
        // 总耗时：15  
  
    }  
  
}

分析

首先，阅读JDK的文档，我们从中可以知道，ArrayList实际上是一个可变长的数组，LinkedList则是由相互引用的节点组成的双向链表

紧接着我们就要知道，在增加数据时LinkedList和ArrayList分别在底层发生了什么？于是略读JDK源码我们就可以得出：
● 既然LinkedList是一个由相互引用的节点组成的双向链表，那么当把数据插入至该链表某个位置时，该数据就会被组装成一个新的节点，随后只需改变链表中对应的两个节点之间的引用关系，使它们指向新节点，即可完成插入（如下图）；同样的道理，删除数据时，只需删除对应节点的引用即可

● 而ArrayList是一个可变长数组，插入数据时，则需要先将原始数组中的数据复制到一个新的数组，随后再将数据赋值到新数组的指定位置（如下图）；删除数据时，也是将原始数组中要保留的数据复制到一个新的数组

结论

因此，在添加或删除数据的时候，ArrayList经常需要复制数据到新的数组，而LinkedList只需改变节点之间的引用关系，这就是LinkedList在添加和删除数据的时候通常比ArrayList要快的原因

云服务器 GPU云服务器 ArrayList和Vector LinkedList flink和spark对比专线和ipsec 网络对比

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71014.html

Week 2 - Java 容器 - 详细剖析 List 之 ArrayList, Vector,

摘要：底层使用的是双向链表数据结构之前为循环链表，取消了循环。快速随机访问就是通过元素的序号快速获取元素对象对应于方法。而接口就是用来标识该类支持快速随机访问。仅仅是起标识作用。，中文名为双端队列。不同的是，是线程安全的，内部使用了进行同步。前言学习情况记录时间：week 2 SMART子目标：Java 容器记录在学习Java容器知识点中，关于List的需要重点记录的知识点。...

MartinDai 2019-08-16 18:35 评论0 收藏0
常见的集合容器应当避免的坑

摘要：尽可能避免使用，会导致复制数组，降低效率。再额外提一点，我们常用的另一个容器也是推荐要初始化长度从而避免扩容。 showImg(https://segmentfault.com/img/remote/1460000019659723); 前言前不久帮同事一起 review 一个 job 执行缓慢的问题时发现不少朋友在撸码实现功能时还是有需要细节不够注意，于是便有了这篇文章。 Arra...

GraphQuery 2019-08-16 18:28 评论0 收藏0
1、List接口 2、Set接口 3、判断集合唯一性原理

摘要：接口的特点接口的特点它是一个元素存取有序的集合。导致迭代器并不知道集合中的变化，容易引发数据的不确定性。枚举已被迭代器替代。集合取出元素的方式可以采用迭代器增强。 01List接口的特点 A:List接口的特点: a:它是一个元素存取有序的集合。例如，存元素的顺序是11、22、33。那么集合中，元素的存储就是按照11、22、33的顺序完成的）。 b:它是一个带有索引的...

gnehc 2019-08-14 18:41 评论0 收藏0
Java常见集合知识详解

摘要：集合的种类常见的集合类分如下几个种类详解接口是和接口的父接口，也是集合类除外根接口。接口集合中元素的存放特点是元素有序，同一元素可重复。总结中集合是一个非常重要的知识点，在实际运用中也是常常会使用到。集合的种类常见的集合类分如下几个种类： Collection - List - ArrayList - LinkedList - Set - HashSet...

lewinlee 2019-08-15 18:19 评论0 收藏0
源码|jdk源码之LinkedList与modCount字段

摘要：迭代器迭代器迭代中表被修改考虑以下这段代码在迭代器创建之后，对表进行了修改。这样设计是因为，迭代器代表表中某个元素的位置，内部会存储某些能够代表该位置的信息。链表是对上一篇博文所说的顺序表的一种实现。与ArrayList思路截然不同，链表的实现思路是：不同元素实际上是存储在离散的内存空间中的。每一个元素都有一个指针指向下一个元素，这样整个离散的空间就被串成了一个有顺序的表。 ...

赵连江 2019-08-16 12:42 评论0 收藏0