java中ArrayList与LinkedList的原理及区别 - CSDN博客
java中ArrayList与LinkedList的原理及区别
ArrayList实现原理就是动态数组，为什么叫动态数组呢，就是当ArrayList容量扩大时，底层的数组的容量会自动扩大50%,并且ArrayList是线程不安全的。
其优点是查询消耗的时间短，属于随机查询。而相对于LinkedList而言它的添加、删除操作要更耗时。
对于ArrayList在存储大量数据时会大量浪费很多空间，原因就是数组的起始容量为10，当数组要增长时增长公式（newcapacity=(oldcapacity*3)/2+1），相当于增加的50%，这样就会浪费大量空间，如果在你知道你要存储数据的容量前提下，最好声明容量大小。也可以使用trimToSize去掉多余的空间。
LinkedList
LinkedList的实现原理基于链表。其优点就是方便添加和删除元素，而arraylist的优点恰恰的LinkedList的缺点，其查询方法消耗的时间要大于arraylist。
总体上来看，如果你需要做大量的查询工作建议你使用ArrayList,如果需要做大量的添加、删除工作建议使用LinkedList.
本文已收录于以下专栏：
相关文章推荐
ArrayList实现可变数组的原理：
　　当元素超出数组内容，会产生一个新数组，将原来数组的数据复制到新数组中，再将新的元素添加到新数组中。
　　ArrayList:是按照原数组的50%来延长，...
LinkedList与ArrayList的区别
一般大家都知道ArrayList和LinkedList的大致区别：
     1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
     2.对...
1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2.对于元素的查找，ArrayList觉得优于LinkedList，因为LinkedList要移动指针...
在百度知道里获得这个问题的答案，感觉写的非常好。所以贴出来分享：
一·ArrayList,LinkedList,Vestor这三个类都实现了java.util.List接口，但它们有各自不同...
java面试中经常被问到list常用的类以及内部实现机制，平时开发也经常用到list集合类，因此做一个源码级别的分析和比较之间的差异。
首先看一下List接口的的继承关系：
list接口继承Col...
Java中ArrayList和LinkedList区别
一般大家都知道ArrayList和LinkedList的大致区别：
     1.ArrayList是实现了基于动态数组的数据...
一般大家都知道ArrayList和LinkedList的大致区别： 
     1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。 
     2.对于...
他的最新文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)君，已阅读到文档的结尾了呢~~
一般大家都知道ArrayList和LinkedList的大致区别: 1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构. 2.对于随机访问get和set,ArrayList觉得...
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
Java中ArrayList和LinkedList区别
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口一般大家都知道ArrayList和LinkedList的大致区别：&&&&& 1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。&&&&& 2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。&&&&& 3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。&ArrayList和LinkedList是两个集合类，用于存储一系列的对象引用(references)。例如我们可以用ArrayList来存储一系列的String或者Integer。那么ArrayList和LinkedList在性能上有什么差别呢？什么时候应该用ArrayList什么时候又该用LinkedList呢？
一．时间复杂度&首先一点关键的是，ArrayList的内部实现是基于基础的对象数组的，因此，它使用get方法访问列表中的任意一个元素时(random access)，它的速度要比LinkedList快。LinkedList中的get方法是按照顺序从列表的一端开始检查，直到另外一端。对LinkedList而言，访问列表中的某个指定元素没有更快的方法了。&假设我们有一个很大的列表，它里面的元素已经排好序了，这个列表可能是ArrayList类型的也可能是LinkedList类型的，现在我们对这个列表来进行二分查找(binary search)，比较列表是ArrayList和LinkedList时的查询速度，看下面的程序：
1 package com.mangocity.
2 import java.util.LinkedL
3 import java.util.L
4 import java.util.R
5 import java.util.ArrayL
6 import java.util.A
7 import java.util.C
8 public class TestList ...{
public static final int N=50000;
public static L
static...{
Integer vals[]=new Integer[N];
Random r=new Random();
for(int i=0,currval=0;i&N;i++)...{
vals=new Integer(currval);
currval+=r.nextInt(100)+1;
values=Arrays.asList(vals);
static long timeList(List lst)...{
long start=System.currentTimeMillis();
for(int i=0;i&N;i++)...{
int index=Collections.binarySearch(lst, values.get(i));
if(index!=i)
System.out.println("***错误***");
return System.currentTimeMillis()-
public static void main(String args[])...{
System.out.println("ArrayList消耗时间："+timeList(new ArrayList(values)));
System.out.println("LinkedList消耗时间："+timeList(new LinkedList(values)));
我得到的输出是：ArrayList消耗时间：15&&&&&&&&&&&&&&&&& LinkedList消耗时间：2596&这个结果不是固定的，但是基本上ArrayList的时间要明显小于LinkedList的时间。因此在这种情况下不宜用LinkedList。二分查找法使用的随机访问(random access)策略，而LinkedList是不支持快速的随机访问的。对一个LinkedList做随机访问所消耗的时间与这个list的大小是成比例的。而相应的，在ArrayList中进行随机访问所消耗的时间是固定的。&这是否表明ArrayList总是比LinkedList性能要好呢？这并不一定，在某些情况下LinkedList的表现要优于ArrayList，有些算法在LinkedList中实现时效率更高。比方说，利用Collections.reverse方法对列表进行反转时，其性能就要好些。&看这样一个例子，加入我们有一个列表，要对其进行大量的插入和删除操作，在这种情况下LinkedList就是一个较好的选择。请看如下一个极端的例子，我们重复的在一个列表的开端插入一个元素：&
package com.mangocity.
import java.util.*;
public class ListDemo {
static final int N=50000;
static long timeList(List list){
long start=System.currentTimeMillis();
Object o = new Object();
for(int i=0;i&N;i++)
list.add(0, o);
return System.currentTimeMillis()-
public static void main(String[] args) {
System.out.println("ArrayList耗时："+timeList(new ArrayList()));
System.out.println("LinkedList耗时："+timeList(new LinkedList()));
&这时我的输出结果是：ArrayList耗时：2463
&&&&&&&&&&&&&&& &&&&&&&&&& LinkedList耗时：15&这和前面一个例子的结果截然相反，当一个元素被加到ArrayList的最开端时，所有已经存在的元素都会后移，这就意味着数据移动和复制上的开销。相反的，将一个元素加到LinkedList的最开端只是简单的未这个元素分配一个记录，然后调整两个连接。在LinkedList的开端增加一个元素的开销是固定的，而在ArrayList的开端增加一个元素的开销是与ArrayList的大小成比例的。
二．空间复杂度&在LinkedList中有一个私有的内部类，定义如下：
private static class Entry {
每个Entry对象reference列表中的一个元素，同时还有在LinkedList中它的上一个元素和下一个元素。一个有1000个元素的LinkedList对象将有1000个链接在一起的Entry对象，每个对象都对应于列表中的一个元素。这样的话，在一个LinkedList结构中将有一个很大的空间开销，因为它要存储这1000个Entity对象的相关信息。&ArrayList使用一个内置的数组来存储元素，这个数组的起始容量是10.当数组需要增长时，新的容量按如下公式获得：新容量=(旧容量*3)/2+1，也就是说每一次容量大概会增长50%。这就意味着，如果你有一个包含大量元素的ArrayList对象，那么最终将有很大的空间会被浪费掉，这个浪费是由ArrayList的工作方式本身造成的。如果没有足够的空间来存放新的元素，数组将不得不被重新进行分配以便能够增加新的元素。对数组进行重新分配，将会导致性能急剧下降。如果我们知道一个ArrayList将会有多少个元素，我们可以通过构造方法来指定容量。我们还可以通过trimToSize方法在ArrayList分配完毕之后去掉浪费掉的空间。
三．总结&ArrayList和LinkedList在性能上各有优缺点，都有各自所适用的地方，总的说来可以描述如下：&1．对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。
2．在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。
3．LinkedList不支持高效的随机元素访问。
4．ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间
可以这样说：当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了。
阅读(...) 评论()Java中arraylist和linkedlist的区别_厦门达内JAVA培训
Java中arraylist和linkedlist的区别
来源：慕课网
& & 厦门达内java培训专家说一下arraylist和linkedlist有哪些区别。
& & 1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
& & 2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
& & 3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
& & ArrayList和LinkedList是两个集合类，用于存储一系列的对象引用(references)。例如我们可以用ArrayList来存储一系列的String或者Integer。那么ArrayList和LinkedList在性能上有什么差别呢？什么时候应该用ArrayList什么时候又该用LinkedList呢？
& & ArrayList和LinkedList在性能上各有优缺点，都有各自所适用的地方，总的说来可以描述如下：
& & 1．对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。
& & 2．在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。&
& & 3．LinkedList不支持高效的随机元素访问。
& & 4．ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间
& & 达内java培训专家总结：当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了。
原文链接：/article/5425
达内教育蝉联荣登“2016百度数字资产榜单”职业教育类第一名
795万高校毕业生创历史新高，2017届毕业生就业近况几何？
恭喜达内获得《产学合作协同育人项目合作伙伴奖》
随着IT行业的迅速发展，我们正从一个以计算为主的时代进入到以数据为主的时代，大数据的趋势已逐步从概念走向落地，目前大数据已经渗透到我们生活的各行各业中。而Java大数据是一门编程语言，可以编写各种各样的计算机指令。通过Java语言组织成各种各样的命令可以完成现实生活中许多的事情。当Java大数据通过用户相关数据信息创造越来越多的商业价值时，各大企业对大数据高端人才的需求也越来越紧迫。根据智联招聘显示，2017年2月全国与大数据相关的职位需求量大约为42436个，而仅仅北京地区与大数据相关的职位需求量就有9553个。据有关专家预测，到2020年，大数据全球市场规模有望达到611.6亿美元，复合年增长率将达到26%。与此相对应的是，Java工程师()的薪水也随之水涨船高，月薪普遍8k-30k之间。
Copyright (C)
All Rights Reserved
选择城市和中心
达内北京亦庄大学生实训基地
达内北京网络营销中心
达内北京会计中心博客分类：
一般大家都知道ArrayList和LinkedList的大致区别：
1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2.对于随机访问get和set，ArrayList绝对优于LinkedList，因为LinkedList要从前到后移动指针。
3.对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。
其实，Linkedlist相较于Arraylist的唯一优势在于集合前段部分的数据的插入，中后段的数据插入效率依然不如ArrayList。
Java中，对于集合的循环常见形式有：下标For循环、ForEach循环、普通迭代循环(list.iterator())、针对List的迭代循环(list.listIterator())、以及相应的While循环。
1. 循环效率(针对数组实现的集合)
各循环效率的对比，其实要看循环的数据量的数量级，以及集合包含的单个对象的大小。
一般而言，while循环与for循环的效率上的区别并不大。
对于线性数组集合而言，如果循环的数量级越大，下标循环的效率越高。请看以下10次执行平均值数据(ArrayList(Integer))，时间单位为nanosecond。
循环数量级
listForLoop(下标)
listForEach
listForIterator
listForListIterator
listWhileLoop(下标)
listWhileIterator
listWhileListIterator
由表格数据可以看出，下标循环的优势是显而易见的，在千万级的数据量时，反而这种差距会缩小。因为ArrayList本身就是使用数组实现的，所以用下标来取其中的元素，是一种很直接的方式，开销也小。但是下标循环和foreach循环都是不支持在循环过程中改变集合，而普通迭代与list迭代都是支持改变集合的。
所以一般不推荐使用foreach循环，因为不仅效率低，而且循环过程中，改变集合会报异常(ConcurrentModificationException)。如果是在多线程编程中，一般减少使用下标循环，而使用foreach和迭代循环，会比较安全。
2. 测试过程中的循环代码如下：
a. listForLoop：
public long listForLoop(ArrayList&Integer& list) {
long start =0L,end=0L;
@SuppressWarnings("unused")
Integer s =
start=System.nanoTime();
for (int i = 0,len = list.size(); i & i++) {
s = list.get(i);
end = System.nanoTime();
return end-
b. listForEach：
public long listForEach(ArrayList&Integer& list) {
long start =0L,end=0L;
@SuppressWarnings("unused")
Integer s =
start=System.nanoTime();
for (Integer i : list) {
end = System.nanoTime();
return end-
c. listForIterator：
public long listForIterator(ArrayList&Integer& list) {
long start =0L,end=0L;
@SuppressWarnings("unused")
Integer s =
start=System.nanoTime();
for (Iterator it = list.iterator(); it.hasNext();) {
s = (Integer) it.next();
end = System.nanoTime();
return end-
d. listForListIterator：
public long listForListIterator(ArrayList&Integer& list) {
long start =0L,end=0L;
@SuppressWarnings("unused")
Integer s =
start=System.nanoTime();
for (Iterator it = list.listIterator(); it.hasNext();) {
s = (Integer) it.next();
end = System.nanoTime();
return end-
e. listWhileLoop：
public long listWhileLoop(ArrayList&Integer& list) {
long start =0L,end=0L;
@SuppressWarnings("unused")
Integer s =
int len = list.size();
start=System.nanoTime();
int i = 0;
while (i&len) {
s=list.get(i);
end = System.nanoTime();
return end-
listWhileIterator：
public long listWhileIterator(ArrayList&Integer& list) {
long start =0L,end=0L;
@SuppressWarnings("unused")
Integer s =
start=System.nanoTime();
Iterator it = list.iterator();
while (it.hasNext()) {
s=(Integer) it.next();
end = System.nanoTime();
return end-
g. listWhileListIterator：
public long listWhileListIterator(ArrayList&Integer& list) {
long start =0L,end=0L;
@SuppressWarnings("unused")
Integer s =
start=System.nanoTime();
Iterator it = list.listIterator();
while (it.hasNext()) {
s=(Integer) it.next();
end = System.nanoTime();
return end-
3. 具体list.iterator()与list.listIterator(迭代的区别如下：
a、ListIterator有add()方法，可以向List中添加对象，而Iterator不能。
b、ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历。但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历。Iterator就不可以。
c、ListIterator可以定位当前的索引位置，nextIndex()和previousIndex()可以实现。Iterator 没有此功能。
d、都可实现删除对象，但是ListIterator可以实现对象的修改，set()方法可以实现。Iterator仅能遍历，不能修改对象的引用。
浏览: 1449 次
来自: 杭州
第一次写博客，哈哈
(window.slotbydup=window.slotbydup || []).push({
id: '4773203',
container: s,
size: '200,200',
display: 'inlay-fix'