首页 > 编程语言 >Java 中 ArrayList 和 LinkedList 有什么区别

Java 中 ArrayList 和 LinkedList 有什么区别

时间:2023-05-16 10:36:33浏览次数:36  
标签:Java LinkedList 删除 ArrayList 元素 数组 节点

在Java中,ArrayList和LinkedList是两种常见的集合类。它们都实现了List接口,提供了类似数组的功能,可以存储任意类型的对象。虽然它们都可以实现相同的功能,但是它们的底层实现方式有所不同,因此在性能和用途上也存在一些差异。

在这里插入图片描述

ArrayList

ArrayList是一个基于数组实现的动态数组,它可以自动扩展容量以容纳新的元素。在ArrayList中,元素存储在一个Object数组中,可以通过索引访问数组中的元素。

底层原理

ArrayList底层使用数组实现,每个ArrayList实例都包含一个Object类型的数组elementData,用于存储元素。当ArrayList中的元素数量超过数组容量时,ArrayList会自动扩容,创建一个新的数组,并将原数组中的元素复制到新数组中。

private transient Object[] elementData;

在ArrayList中,添加元素的操作可以分为两种情况:

  • 如果数组容量足够,直接将元素添加到数组末尾。
  • 如果数组容量不足,需要先对数组进行扩容,然后将元素添加到数组末尾。
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(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);
}

在ArrayList中,删除元素的操作可以分为两种情况:

  • 如果要删除的元素在数组中间,需要将后续的元素向前移动,覆盖要删除的元素。
  • 如果要删除的元素在数组末尾,直接将数组长度减一即可。
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0) {
        System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
    }
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

特点

  • ArrayList是一个基于数组实现的动态数组,可以自动扩容以容纳新的元素。
  • 在ArrayList中,元素可以通过索引访问,因此随机访问效率较高。
  • 在ArrayList中,插入和删除操作可能需要移动后续的元素,因此效率较低。

源码

ArrayList的源码可以在JDK中找到,位于java.util包中。

LinkedList

LinkedList是一个基于链表实现的双向链表,它可以动态地添加、删除元素。在LinkedList中,元素存储在一个节点(Node)中,每个节点包含一个元素和前后指针。

底层原理

LinkedList底层使用双向链表实现,每个LinkedList实例都包含一个Node类型的first和last节点,用于表示链表的头和尾。

java

Copy

private transient Node<E> first;
private transient Node<E> last;

在LinkedList中,添加元素的操作可以分为三种情况:

  • 如果链表为空,将新节点设置为first和last节点。
  • 如果要添加的元素在链表头部,将新节点设置为first节点,并将原first节点作为新节点的后继。
  • 如果要添加的元素在链表尾部,将新节点设置为last节点,并将原last节点作为新节点的前驱。
public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

在LinkedList中,删除元素的操作可以分为三种情况:

  • 如果要删除的元素是first节点,将first节点设置为原first节点的后继。
  • 如果要删除的元素是last节点,将last节点设置为原last节点的前驱。
  • 如果要删除的元素在链表中间,将要删除的节点的前驱和后继节点连接起来,然后将要删除的节点的前驱和后继节点分别指向要删除节点的前驱和后继节点。
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

特点

  • LinkedList是一个基于链表实现的双向链表,可以动态地添加、删除元素。
  • 在LinkedList中,元素不能通过索引访问,因此随机访问效率较低。
  • 在LinkedList中,插入和删除操作只需要改变相邻节点的指针,因此效率较高。

源码

LinkedList的源码可以在JDK中找到,位于java.util包中。

ArrayList和LinkedList的比较

从底层实现上来看,ArrayList和LinkedList有以下区别:

  • ArrayList底层使用数组实现,LinkedList底层使用链表实现。
  • 在ArrayList中,元素可以通过索引访问,因此随机访问效率较高,但是插入和删除操作效率较低。在LinkedList中,元素不能通过索引访问,因此随机访问效率较低,但是插入和删除操作效率较高。
  • 在ArrayList中,添加和删除操作需要移动后续的元素,因此效率较低。在LinkedList中,添加和删除操作只需要改变相邻节点的指针,因此效率较高。
  • 在ArrayList中,扩容时需要创建一个新的数组,并将原数组中的元素复制到新数组中,效率较低。在LinkedList中,不需要扩容,因为链表可以动态地添加、删除节点。

由于ArrayList和LinkedList的底层实现方式不同,因此它们适用的场景也不同:

  • 如果需要频繁访问集合中的元素,并且集合的大小不会经常改变,选择ArrayList会更加合适,因为ArrayList可以通过索引快速访问元素,效率较高。
  • 如果需要频繁添加、删除集合中的元素,选择LinkedList会更加合适,因为LinkedList可以快速地添加、删除节点,效率较高。

总结

ArrayList和LinkedList是Java中常见的集合类,它们都实现了List接口,提供了类似数组的功能,可以存储任意类型的对象。ArrayList底层使用数组实现,LinkedList底层使用链表实现。

标签:Java,LinkedList,删除,ArrayList,元素,数组,节点
From: https://www.cnblogs.com/jasonxu94/p/17404111.html

相关文章

  • Java中两个字符串进行大小比较
    一:大小比较:使用String.compareTo方法如果需要忽略大小写,使用compareToIgnoreCasecompareTo()的返回值是int,它是先比较对应字符的大小(ASCII码顺序)1、如果字符串相等返回值02、如果第一个字符和参数的第一个字符不等,结束比较,返回他们之间的差值(ascii码值)(负值表示前字符......
  • 汉字转换为拼音的JavaScript库的比较
    JSPinyin有提供了两个方法:<依赖mootools>1)一个是将汉字翻译为拼音,其中每一个字的首字母大写;1pinyin.getFullChars(this.value);2)一个是可以将每一个字的拼音的首字母提取出来,是大写的形式。1pinyin.getCamelChars(this.value);还可以设置是否判断多音字。只是功能比较简单,如......
  • Java生成缩略图之Thumbnailator
    Thumbnailator是一个为Java界面更流畅的缩略图生成库。从API提供现有的图像文件和图像对象的缩略图中简化了缩略过程,两三行代码就能够从现有图片生成缩略图,且允许微调缩略图生成,同时保持了需要写入到最低限度的代码量。同时还支持根据一个目录批量生成缩略图。 http://code.googl......
  • java获取目录下文件名称
    1.package2.import3.import4.import5.6./**7.*读取目录及子目录下指定文件名的路径,返回一个List8.*/9.10.publicclass11.privatestaticLoggerlogger=Logger.getLogger(FileViewer.class);12.13./**14.*@parampath15.......
  • 01-面试必会-JAVA基础篇
    1.Final有什么用?被final修饰的类不可以被继承被final修饰的方法不可以被重写被final修饰的变量不可以被改变,被final修饰不可变的是变量的引用,而不是引用指向的内容,引用指向的内容是可以改变的2.什么是重载(Overload)和重写(Override)?重载:发生在同一个类中,方法名相......
  • Java初学者之数据类型
    今天下午看了点数据类型的东西,来这里总结一下。顺便锻炼一下自己的思维能力.首先数据类型的分类:1. 基本数据类型2.引用数据类型基本数据类型有八种:整数型:byte(1B)short(2B)int(4B)long(8B),小数型:float(4B),double(8B),布尔值:true,false(1bit),字符型:char(2B)引用数......
  • java面向对象
    java面向对象编程面向对象思想:物以类聚,分类的思维模式。思考问题首先会解决问题需要那些分类适合处理复杂的问题,适合多人的协作问题面向对象的本质:以类的方式组织代码,以对象的组织(封装)数据特征:抽象三大特性:封装,继承,多态static加了static的方法可以通过类名直接调用......
  • lombok (java 驼峰规范导致的 JSON 序列化问题)
    1、问题描述有一个接收类,出于某种原因(调用第三方接口)会使用首字母大写的情况@DatapublicclassHelloModel{ privateStrigATest; privateStrigBTest;}当我使用这个类接收一个JSON格式的数据,转换为对应的这个HelloModel类时,会出现ATest和BTest都为null的情......
  • window 通过idea的java工程。生成bat文件
    参考两个大佬的。一、java工程,生成jar包。参考:https://www.cnblogs.com/blog5277/p/5920560.html重点:右键项目名--->选择OpenModuleSetting(默认快捷键F4)--->打开的弹框左侧选择Libraries--->弹框中间点击“+”号--->Java--->在弹出的选择框中选择所依赖的所有jar包(将所有jar......
  • Java通过反射获取Fields、Method、Constructor示例
    1.getFields()和getDeclaredFields()getFields能获取该类和父类(包括Object)public的属性,getDeclaredFields获取该类public和private的属性2.getMethods()和getDeclaredMethods()getMethods能获取该类和父类(包括Object)public的方法,getDeclaredMethods获取该类public和privat......