arraylist和linkedlist重大区别?
一、基本区别:
1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。
3.对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。
二、ArrayList和LinkedList在性能上各有优缺点,都有各自所适用的地方,总的说来可以描述如下:
1.对ArrayList和LinkedList而言,在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言,主要是在内部数组中增加一项,指向所添加的元素,偶尔可能会导致对数组重新进行分配;而对LinkedList而言,这个开销是统一的,分配一个内部Entry对象。
2.在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动;而在LinkedList的中间插入或删除一个元素的开销是固定的。
3.LinkedList不支持高效的随机元素访问。
4.ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间
ArrayList和LinkedList的大致区别如下:
1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。
3.对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。
LinkedList链表由一系列表项连接而成。一个表项总是包含3个部分:元素内容,前驱表和后驱表,如图所示:
在下图展示了一个包含3个元素的LinkedList的各个表项间的连接关系。在JDK的实现中,无论LikedList是否为空,链表内部都有一个header表项,它既表示链表的开始,也表示链表的结尾。表项header的后驱表项便是链表中第一个元素,表项header的前驱表项便是链表中最后一个元素。
拓展资料
ArrayList就是动态数组,用MSDN中的说法,就是Array的复杂版本,它提供了动态的增加和减少元素,实现了ICollection和IList接口,灵活的设置数组的大小等好处。
List 接口的大小可变数组的实现,位于API文档的java.util.ArrayList。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List 接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。
每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素,其容量也自动增长。并未指定增长策略的细节,因为这不只是添加元素会带来分摊固定时间开销那样简单。
注意,迭代器的快速失败行为无法得到保证,因为一般来说,不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。
参考资料:百度百科-ArrayList词条
1. ArrayList是实现了基于动态数组的数据结构,而LinkedList是基于链表的数据结构;
2. 对于随机访问get和set,ArrayList要优于LinkedList,因为LinkedList要移动指针;
3. 对于添加和删除操作add和remove,一般大家都会说LinkedList要比ArrayList快,因为ArrayList要移动数据。但是实际情况并非这样,对于添加或删除,LinkedList和ArrayList并不能明确说明谁快谁慢
研究源码可以看出,ArrayList想要get(int index)元素时,直接返回index位置上的元素,而LinkedList需要通过for循环进行查找,虽然LinkedList已经在查找方法上做了优化,比如index < size / 2,则从左边开始查找,反之从右边开始查找,但是还是比ArrayList要慢。这点是毋庸置疑的。
ArrayList想要在指定位置插入或删除元素时,主要耗时的是System.arraycopy动作,会移动index后面所有的元素;LinkedList主耗时的是要先通过for循环找到index,然后直接插入或删除。这就导致了两者并非一定谁快谁慢
测试:
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
/*
* @description 测试ArrayList和LinkedList插入的效率
* @eson_15
*/
public class ArrayOrLinked {
static List<Integer> array=new ArrayList<Integer>();
static List<Integer> linked=new LinkedList<Integer>();
public static void main(String[] args) {
//首先分别给两者插入10000条数据
for(int i=0;i<10000;i++){
array.add(i);
linked.add(i);
}
//获得两者随机访问的时间
System.out.println("array time:"+getTime(array));
System.out.println("linked time:"+getTime(linked));
//获得两者插入数据的时间
System.out.println("array insert time:"+insertTime(array));
System.out.println("linked insert time:"+insertTime(linked));
}
public static long getTime(List<Integer> list){
long time=System.currentTimeMillis();
for(int i = 0; i < 10000; i++){
int index = Collections.binarySearch(list, list.get(i));
if(index != i){
System.out.println("ERROR!");
}
}
return System.currentTimeMillis()-time;
}
//插入数据
public static long insertTime(List<Integer> list){
/*
* 插入的数据量和插入的位置是决定两者性能的主要方面,
* 我们可以通过修改这两个数据,来测试两者的性能
*/
long num = 10000; //表示要插入的数据量
int index = 1000; //表示从哪个位置插入
long time=System.currentTimeMillis();
for(int i = 1; i < num; i++){
list.add(index, i);
}
return System.currentTimeMillis()-time;
}
}
主要有两个因素决定他们的效率,插入的数据量和插入的位置。我们可以在程序里改变这两个因素来测试它们的效率。
当数据量较小时,测试程序中,大约小于30的时候,两者效率差不多,没有显著区别;当数据量较大时,大约在容量的1/10处开始,LinkedList的效率就开始没有ArrayList效率高了,特别到一半以及后半的位置插入时,LinkedList效率明显要低于ArrayList,而且数据量越大,越明显。比如我测试了一种情况,在index=1000的位置(容量的1/10)插入10000条数据和在index=5000的位置以及在index=9000的位置插入10000条数据的运行时间如下:
在index=1000出插入结果:
array time:4
linked time:240
array insert time:20
linked insert time:18
在index=5000处插入结果:
array time:4
linked time:229
array insert time:13
linked insert time:90
在index=9000处插入结果:
array time:4
linked time:237
array insert time:7
linked insert time:92
从运行结果看,LinkedList的效率是越来越差。
所以当插入的数据量很小时,两者区别不太大,当插入的数据量大时,大约在容量的1/10之前,LinkedList会优于ArrayList,在其后就劣与ArrayList,且越靠近后面越差。所以个人觉得,一般首选用ArrayList,由于LinkedList可以实现栈、队列以及双端队列等数据结构,所以当特定需要时候,使用LinkedList,当然咯,数据量小的时候,两者差不多,视具体情况去选择使用;当数据量大的时候,如果只需要在靠前的部分插入或删除数据,那也可以选用LinkedList,反之选择ArrayList反而效率更高。
数组是定长的,每一次添加删除元素实际是长度在变化,对应都会开辟新的内存空间创建新的对象,并复制原有的数组在添加删除后存储到新开辟内存中,而在底层开辟内存空间创建复制对象都是非常耗费时间和资源的;
而修改实际考验的是查询的效率,数组查找元素靠索引,效率非常高;链表只能重头到尾或者从尾到头,挨个挨个找
数据结构不同
效率不同
自由性不同
主要控件开销不同
数据结构不同
效率不同
自由性不同
arraylist和数组有什么区别
两者区别在于动态扩展性、类型安全性不同。1、动态扩展性:数组在创建时需要指定其长度,并且一旦初始化后,长度是固定的,需要改变数组的大小,则必须创建一个新的数组,并将原有数组中的元素复制过来。ArrayList是可动态扩容的容器,当添加更多的元素并且当前容量不足以容纳时,会自动增大内部数组的大小。
ArrayList和List有什么区别?
ArrayList和List两者有以下主要区别:实现方式:ArrayList是List接口的一个实现类,而List是一个接口。这意味着ArrayList可以作为List的实例使用,但反之则不成立。内部数据结构:ArrayList底层是用动态数组实现的,而List底层可能是链表或者动态数组。这使得ArrayList在随机访问元素时(即通过索引访问元素)速度更...
arraylist和linkedlist的区别
1、arraylist的空间浪费主要体现在在list结尾预留了一定的容量空间。2、而linkedlist的空间浪费则体现在它的每一个元素都要消耗一定的空间。三、原理不同。1、arraylist是基于动态数组实现的非线程安全集合。2、linkedlist是基于链表实现的非线程安全集合。四、删除元素。1、arraylist在新增和删除元素时,可能...
ArrayList与LinkedList的扩容
ArrayList和LinkedList是Java中常见的两种列表数据结构,它们在扩容机制上有着本质的不同。1. ArrayList的扩容机制:- 首先,ArrayList的底层是一个动态数组,它可以在需要时自动增加其容量。- 扩容过程:当数组中的元素达到其容量上限时,ArrayList会创建一个新的、更大的数组,并将现有元素复制到这个新数组...
数组ArrayList和List之间的主要区别是什么?
数组可以具有多个维度,而 ArrayList或 List< T> 始终只具有一个维度。但是,您可以轻松创建数组列表或列表的列表。特定类型(Object 除外)的数组的性能优于 ArrayList的性能。 这是因为 ArrayList的元素属于 Object 类型;所以在存储或检索值类型时通常发生装箱和取消装箱操作。不过,在不需要重新分配时(即...
arraylist和linkedlist的区别
1. LinkedList和ArrayList的差别主要来自于Array和LinkedList数据结构的不同。ArrayList是基于数组实现的,LinkedList是基于双链表实现的。另外LinkedList类不仅是List接口的实现类,可以根据索引来随机访问集合中的元素,除此之外,LinkedList还实现了Deque接口,Deque接口是Queue接口的子接口,它代表一个双向队列,...
java中ArrayList和LinkedList有什么区别,分别怎么使用呢
ArrayList与LinkList两者的区别:ArrayList是基于索引的数据接口,它的底层是数组。它可以以O(1)时间复杂度对元素进行随机访问。相对于ArrayList,LinkedList的插入,添加,删除操作速度更快,因为当元素被添加到集合任意位置的时候,不需要像数组那样重新计算大小或者是更新索引。LinkedList比ArrayList更占内存,...
Java中List和ArrayList的区别
List有两个重要的实现类:ArrayList 和 LinkedList ArrayList:我们可以将其看作是能够自动增长容量的数组。利用ArrayList的toArray()返回一个数组。Arrays.asList()返回一个列表。1.ArrayList底层采用数组实现,当使用不带参数的构造方法生成ArrayList对象时,实际上会在底层生成一个长度为10的Object类型数组 ...
ArrayList和数组的区别
而对于ArrayList,可以用add(Object)的形式让它自行管理大小。3、数组使用的是特殊的语法;ArrayList是个普通对象,所以不会有特殊的语法。其实ArrayList的底层数据结构就是一个数组,所以在已知所要创建数组需要的长度的前提下,使用数组在性能上可以有一定的提升。参考书籍:《Head First Java》
arraylist 和 linkedlist 的区别
1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。3.对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。这一点要看实际情况的。若只对单条数据插入或删除,ArrayList的速度...
却花洁尔: 一般大家都知道ArrayList和LinkedList的大致区别: 1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构. 2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针. 3.对于新增和删除操作add...
邕宁区17522737958: arraylist和linklist的区别 - ?
却花洁尔: arraylist底层数据结构是数组,linkedlist底层数据结构是链表结构.共同点:有序(存取顺序一致),存储的数据可重复.线程不安全,效率高
邕宁区17522737958: arraylist和linkedlist的区别和使用场景 - ?
却花洁尔: 1、ArrayList是基于数组实现的,其构造函数为:private transient Object[] elementData;private int size;ArryList初始化时,elementData数组大小默认为10;每次add()时,先调用ensureCapacity()保证数组不会溢出,如果此时已满,会...
邕宁区17522737958: ArrayList和LinkedList的区别 - ?
却花洁尔: ArrayList 采用的是数组形式来保存对象的,这种方式将对象放在连续的位置中,所以最大的缺点就是插入删除时非常麻烦 LinkedList 采用的将对象存放在独立的空间中,而且在每个空间中还保存下一个链接的索引 但是缺点就是查找非常麻烦 要...
邕宁区17522737958: ArrayList、linklist、list的区别?
却花洁尔: List是一个接口,ArrayList和LinkedList是两个实现类,他们实现的方式不一样,其实LinkedList才是真正的链表(如果不清楚什么是链表,需要了解一下相关数据结构的知识,这不是一两句话能说清楚的),而ArrayList是用数组实现的,它不是...
邕宁区17522737958: ArrayList 和LinkdList的区别是什么??
却花洁尔: ArrayList 实现List接口 ,随着向 ArrayList 中不断添加元素,其容量也自动增长 对于处理一列数据项,Java提供了两个类ArrayList和LinkedList, ArrayList的内部实现是基于内部数组Object[], 所以从概念上讲,它更象数组,但LinkedList的内部实...
邕宁区17522737958: java.util中ArrayList、LinkedList以及Vector它们三者的区别与联系! - ?
却花洁尔: ArrayList,LinkedList,Vestor这三个类都实现了java.util.List接口,但它们有各自不同的特性,主要如下:一、同步性 ArrayList,LinkedList是不同步的,而Vestor是的.所以如果要求线程安全的话,可以使用ArrayList或LinkedList,可以节省为同步而...
邕宁区17522737958: ArrayList和LinkedList区别,举例说明下 - ?
却花洁尔: 学习一下数据结构你就明白了,ArrayList和LinkedList都是属于线性表,不同的是ArrayList底层用数组来实现,LinkedList使用链表来实现.两者对于不同的运算效率差别很大,比如ArrayList访问元素就比LinkedList快得多,但是对于插入删除运算,LinkedList就好的多.
邕宁区17522737958: LinkedList和ArrayList的区别 - ?
却花洁尔: ArrayList和LinkedList在性能上各有优缺点,都有各自所适用的地方,总的说来可以描述如下: 1.对ArrayList和LinkedList而言,在列表末尾增加一个元素所花的开销都是固定的.对ArrayList而言,主要是在内部数组中增加一项,指向所添加的元...
邕宁区17522737958: ArrayList和LinkedList底层实现的区别 - ?
却花洁尔: ArrayList和LinkedList都实现了List接口,ArrayList的实现用的是数组,LinkedList是基于链表,ArrayList适合查找,LinkedList适合增删.ArrayList与LinkList两者的区别:ArrayList是基于索引的数据接口,它的底层是数组.它可以以O(1)时间复...