java中ArrayList和LinkedList的区别详解

ArrayList和LinkedList都实现了List接口，有以下的不同点：

1、ArrayList是基于索引的数据接口，它的底层是数组。它可以以O(1)时间复杂度对元素进行随机访问。与此对应，LinkedList是以元素列表的形式存储它的数据，每一个元素都和它的前一个和后一个元素链接在一起，在这种情况下，查找某个元素的时间复杂度是O(n)。
2、相对于ArrayList，LinkedList的插入，添加，删除操作速度更快，因为当元素被添加到集合任意位置的时候，不需要像数组那样重新计算大小或者是更新索引。
3、LinkedList比ArrayList更占内存，因为LinkedList为每一个节点存储了两个引用，一个指向前一个元素，一个指向下一个元素。

ArrayList扩容：

总的来说就是分两步：

1、扩容

把原来的数组复制到另一个内存空间更大的数组中

2、添加元素

把新元素添加到扩容以后的数组中
无参构造：

public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

带参构造：

public ArrayList(int initialCapacity) {
  if (initialCapacity >0) {
    this.elementData =new Object[initialCapacity];
  }else if (initialCapacity ==0) {
    this.elementData = EMPTY_ELEMENTDATA;
  }else {
    throw new IllegalArgumentException("Illegal Capacity: "+
                      initialCapacity);
  }
}

在无参构造中，我们看到了在用无参构造来创建对象的时候其实就是创建了一个空数组，长度为0
在有参构造中，传入的参数是正整数就按照传入的参数来确定创建数组的大小，否则异常
接下来我们来看扩容，扩容的方法就是 add(E e)

public boolean add(E e) {
    ensureCapacityInternal(size + 1); // Increments modCount!!
    elementData[size++] = e;
    return true;
  }
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
  }
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
      return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
  }
private void ensureExplicitCapacity(int minCapacity) {
   modCount++;

   // overflow-conscious code
   if (minCapacity - elementData.length > 0)
     grow(minCapacity);
 }
private void grow(int minCapacity) {
   // overflow-conscious code
   int oldCapacity = elementData.length;
   int newCapacity = oldCapacity + (oldCapacity >> 1);
   if (newCapacity - minCapacity < 0)
     newCapacity = minCapacity;
   if (newCapacity - MAX_ARRAY_SIZE > 0)
     newCapacity = hugeCapacity(minCapacity);
   // minCapacity is usually close to size, so this is a win:
   elementData = Arrays.copyOf(elementData, newCapacity);
 }

int newCapacity = oldCapacity + (oldCapacity >> 1);
oldCapacity >> 1 右移运算符 原来长度的一半 再加上原长度也就是每次扩容是原来的1.5倍
之前的所有都是确定新数组的长度，确定之后就是把老数组copy到新数组中，这样数组的扩容就结束了
以上的一切都是ArrayList扩容的第一步，第二步就没啥说的了，就是把需要添加的元素添加到数组的最后一位

以上就是java中ArrayList和LinkedList的区别详解的详细内容，更多关于java ArrayList和LinkedList的区别的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • java 中ArrayList与LinkedList性能比较

    java 中ArrayList与LinkedList性能比较 今天看一框架的代码,看到有些 可以使用ArrayList的地方 使用的是 LinkedList,用到的情景是在一个循环里面进行顺序的插入操作. 众所周知java里面List接口有两个实现ArrayList 和 LinkedList,他们的实现原理分别是c语言中介绍的数组和链表. 正如学习数据结构时的认识,对于插入操作,链表的结构更高效,原因是可以通过修改节点的指针 就可以完成插入操作, 而不像数组, 需要把插入位置之后的数组元素依次后

  • JAVA LinkedList和ArrayList的使用及性能分析

    JAVA LinkedList和ArrayList的使用及性能分析

    第1部分 List概括List的框架图List 是一个接口,它继承于Collection的接口.它代表着有序的队列.AbstractList 是一个抽象类,它继承于AbstractCollection.AbstractList实现List接口中除size().get(int location)之外的函数.AbstractSequentialList 是一个抽象类,它继承于AbstractList.AbstractSequentialList 实现了"链表中,根据index索引值操作链表的全部函数

  • Java中ArrayList和LinkedList之间的区别_动力节点Java学院整理

    一.ArrayList ArrayList是一个可以处理变长数组的类型,这里不局限于"数"组,ArrayList是一个泛型类,可以存放任意类型的对象.顾名思义,ArrayList是一个数组列表,因此其内部是使用一个数组来存放对象的,因为Object是一切类型的父类,因而ArrayList内部是有一个Object类型的数组类存放对象.ArrayList类常用的方法有add().clear().get().indexOf().remove().sort().toArray().toStri

  • 浅谈 java中ArrayList、Vector、LinkedList的区别联系

    以前面试的时候经常会碰到这样的问题.,叫你写一下ArrayList.LinkedList.Vector三者之间的区别与联系:原先一直搞不明白,不知道这三者之间到底有什么区别?哎,惭愧,基础太差啊,木有办法啊委屈 现在得去说说这三者之间的区别与联系了:这三者都是实现了List接口,都拥有List接口里面定义的方法,并且同时拥有Collection接口的方法: ArrayList:采用的是数组的方式进行存储数据的,查询和修改速度快,但是增加和删除速度慢:线程是不同步 LinkedList:采用的是链

  • 区分Java中的ArrayList和LinkedList

    一:ArrayList和LinkedList的大致区别如下: 1.ArrayList是实现了基于动态数组的数据结构,ArrayList实现了长度可变的数组,在内存中分配连续的空间.遍历元素和随机访问元素的效率比较高 2.LinkedList基于链表的数据结构, 插入.删除元素时效率比较高  故:[插入.删除操作频繁时,可使用LinkedList来提高效率]LinkedList提供对头部和尾部元素进行添加和删除操作的方法,插入/删除第一个和最后一个效率比较高: 3:ArrayList和Linked

  • java 集合之实现类ArrayList和LinkedList的方法

    List 的方法列表 方法名 功能说明 ArrayList() 构造方法,用于创建一个空的数组列表 add(E e) 将指定的元素添加到此列表的尾部 get(int index) 返回此列表中指定位置上的元素 size() 返回此列表中的元素数 clear() 移除此列表中的所有元素 isEmpty() 如果此列表中没有元素,则返回true remove(int index) 移除此列表中指定位置上的元素 indextof(Object o) 返回此列表中首次出现的指定元素的索引,或如果此列表不

  • 分析Java中ArrayList与LinkedList列表结构的源码

    分析Java中ArrayList与LinkedList列表结构的源码

    一.ArrayList源码分析(JDK7) ArrayList内部维护了一个动态的Object数组,ArrayList的动态增删就是对这个对组的动态的增加和删除. 1.ArrayList构造以及初始化 ArrayList实例变量 //ArrayList默认容量 private static final int DEFAULT_CAPACITY = 10; //默认空的Object数组, 用于定义空的ArrayList private static final Object[] EMPTY_ELE

  • java中ArrayList与LinkedList对比详情

    java中ArrayList与LinkedList对比详情

    ArrayList,LinkedList都是Collection接口的通用实现方式,两者采用了不用的存储策略,用来适应不同场合的需要. 实现方式 ArrayList的内部采用集合的方式存储数据 唯一需要注意的是对于容量超过阈值的处理逻辑,数组的默认容量大小是10,最大容量是Integer.Max_Value,超过最大容量会抛内存溢出异常, 扩容机制看下面 扩容后的容量是原有容量的1.5倍 LinkedList的实现方式 内部采用双向链表Node内部类来存储数据,由于采用了双向链表,LinkedL

  • Java中ArrayList和LinkedList的遍历与性能分析

    前言 通过本文你可以了解List的五种遍历方式及各自性能和foreach及Iterator的实现,加深对ArrayList和LinkedList实现的了解.下面来一起看看吧. 一.List的五种遍历方式 1.for each循环 List<Integer> list = new ArrayList<Integer>(); for (Integer j : list) { // use j } 2.显示调用集合迭代器 List<Integer> list = new Ar

  • java中ArrayList和LinkedList的区别详解

    ArrayList和LinkedList都实现了List接口,有以下的不同点: 1.ArrayList是基于索引的数据接口,它的底层是数组.它可以以O(1)时间复杂度对元素进行随机访问.与此对应,LinkedList是以元素列表的形式存储它的数据,每一个元素都和它的前一个和后一个元素链接在一起,在这种情况下,查找某个元素的时间复杂度是O(n). 2.相对于ArrayList,LinkedList的插入,添加,删除操作速度更快,因为当元素被添加到集合任意位置的时候,不需要像数组那样重新计算大小或者

  • Java 中泛型 T 和 ? 的区别详解

    Java 中泛型 T 和 ? 的区别详解

    目录 泛型中 T 类型变量 和 ? 通配符 区别 Generic Types 类型变量 用法 2.声明通用的方法 – 泛型方法: 有界类型参数 Wildcards 通配符 1.上界通配符:? extend 上界类型 2.无界通配符:? 3.下界通配符:? super 子类 类型擦除 泛型中 T 类型变量 和 ? 通配符 区别 定义不同 :T 是类型变量,? 是通配符 使用范围不同: ? 通配符用作 参数类型.字段类型.局部变量类型,有时作为返回类型(但请避免这样做) T 用作 声明类的类型参数.

  • 基于Java中throw和throws的区别(详解)

    系统自动抛出的异常 所有系统定义的编译和运行异常都可以由系统自动抛出,称为标准异常,并且 Java 强烈地要求应用程序进行完整的异常处理,给用户友好的提示,或者修正后使程序继续执行. 语句抛出的异常 用户程序自定义的异常和应用程序特定的异常,必须借助于 throws 和 throw 语句来定义抛出异常. throw是语句抛出一个异常. 语法:throw (异常对象); throw e; throws是方法可能抛出异常的声明.(用在声明方法时,表示该方法可能要抛出异常) 语法:[(修饰符)](返回

  • Java中接口和抽象类的区别详解

    需求:接口是否可继承接口?抽象类是否可实现(implements)接口?抽象类是否可继承实体类(concrete class)?抽象类中是否可以有静态的main方法? 先说明二者的定义,然后聊聊需求,最后分析二者的区别. 含有abstract修饰符的类即为抽象类,抽象类不能创建实例对象.含有抽象方法的类必须定义为abstract class.在abstract class中,方法不必是抽象的,但是抽象方法必须在具体子类中实现,所以,不能有抽象构造方法或抽象静态方法.子类如果没有实现抽象父类中的所

  • Java中Exception和Error的区别详解

    Java中Exception和Error的区别详解

    世界上存在永远不会出错的程序吗?也许这只会出现在程序员的梦中.随着编程语言和软件的诞生,异常情况就如影随形地纠缠着我们,只有正确的处理好意外情况,才能保证程序的可靠性. java语言在设计之初就提供了相对完善的异常处理机制,这也是java得以大行其道的原因之一,因为这种机制大大降低了编写和维护可靠程序的门槛.如今,异常处理机制已经成为现代编程语言的标配. 今天我要问你的问题是,请对比Exception和Error,另外,运行时异常与一般异常有什么区别? 典型回答 Exception和Error都

  • Java中堆和栈的区别详解

    当一个人开始学习Java或者其他编程语言的时候,会接触到堆和栈,由于一开始没有明确清晰的说明解释,很多人会产生很多疑问,什么是堆,什么是栈,堆和栈有什么区别?更糟糕的是,Java中存在栈这样一个后进先出(Last In First Out)的顺序的数据结构,这就是java.util.Stack.这种情况下,不免让很多人更加费解前面的问题.事实上,堆和栈都是内存中的一部分,有着不同的作用,而且一个程序需要在这片区域上分配内存.众所周知,所有的Java程序都运行在JVM虚拟机内部,我们这里介绍的自然

  • java中SynchronizedList和Vector的区别详解

    前言 Vector是java.util包中的一个类. SynchronizedList是java.util.Collections中的一个静态内部类. 在多线程的场景中可以直接使用Vector类,也可以使用Collections.synchronizedList(List list)方法来返回一个线程安全的List. 那么,到底SynchronizedList和Vector有没有区别,为什么java api要提供这两种线程安全的List的实现方式呢? 首先,我们知道Vector和Arraylis

  • Java中ArrayList和LinkedList区别

    目录 1 前言 2 数据结构的区别 2.1 ArrayList 2.2 LinkedList 2.3 使用场景 3 源码分析 3.1 ArrayList核心源码 3.2 LinkedList核心源码 4 码农来洞见 4.1为什么ArrayList比LinkedList要快 4.2 注意ArrayList不同JDK版本源码 4.3 高并发下如何保证集合数据的同步 4.4 为什么Java的Vector类被认为是过时的或者废弃的 1 前言 许多语言,例如 Perl ,Python 和 Ruby ,都有

  • java线程中start和run的区别详解

    这篇文章主要介绍了java线程中start和run的区别详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 public class Test1 extends Thread { @Override public void run() { while (true) { System.out.println(Thread.currentThread().getName()); } } public static void main(String[

随机推荐