ArrayList与LinkLIst

2023-12-16 21:04:03

ArrayList

在Java中,ArrayListjava.util包中的一个类,它实现了List接口,是一个动态数组,可以根据需要自动增长或缩小。下面是ArrayList的一些基本特性以及其底层原理的简要讲解:

ArrayList基本特性:

  1. 动态数组: ArrayList是一个动态数组,它可以根据需要自动调整大小。

  2. 允许重复元素: ArrayList允许存储相同的元素,可以包含重复的值。

  3. 随机访问: 通过索引,可以以常数时间复杂度进行元素的访问,这是由于底层是数组实现。

  4. 不同步: ArrayList不是线程安全的,如果多个线程同时访问一个ArrayList实例,而至少有一个线程修改了列表结构,那么它必须保持外部同步。

API

boolean add(E element):将指定的元素添加到列表的末尾。
void add(int index, E element):在指定的位置插入指定的元素。
E get(int index)回列表中指定位置的元素。
int size():返回列表中的元素数。
boolean remove(Object o)从列表中删除指定的元素(如果存在)
E remove(int index)删除列表中指定位置的元素。
boolean contains(Object o)如果列表包含指定的元素,则返回 true。
void clear():从列表中删除所有元素。
boolean isEmpty():如果列表不包含元素,则返回 true。

ArrayList底层原理:

  1. 基于数组: ArrayList的底层是一个数组。当你创建一个ArrayList时,它会初始化一个数组来保存元素。初始时,默认大小是0的数组。当添加第一个元素的时候,底层会创建一个长度为10的数组

  2. 自动扩容: 当元素数量超过当前数组容量时,ArrayList会创建一个新的数组,将元素复制到新数组中,并更新引用。通常,新数组的大小是原数组的1.5倍。如果一次添加多个元素1.5倍放不下,则新建数组长度以实际长度为准

  3. 容量增长: ArrayList的容量增长不是按需一次性增长的,而是按照一定的策略进行递增。这样可以减少频繁扩容的开销。

  4. 元素的添加和删除: 在数组中,添加和删除元素可能涉及到移动其他元素,这可能导致性能开销。在某些情况下,特别是在大量操作的情况下,可能会考虑使用LinkedList,因为在链表中添加和删除元素的开销较小。

// 示例代码
import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        // 创建ArrayList
        ArrayList<String> arrayList = new ArrayList<>();

        // 添加元素
        arrayList.add("Java");
        arrayList.add("Python");
        arrayList.add("C++");

        // 访问元素
        System.out.println("First element: " + arrayList.get(0));

        // 删除元素
        arrayList.remove("Python");

        // 打印所有元素
        System.out.println("All elements: " + arrayList);
    }
}

总体而言,ArrayList是一个灵活且性能良好的集合类,适用于大多数元素的存储和检索场景。


LinkList

LinkedList是Java集合框架中的另一种实现List接口的类,它基于链表数据结构。相比于ArrayListLinkedList在一些操作上有不同的性能特点。

LinkedList的基本特性:

  1. 基于链表: LinkedList使用双向链表实现,每个元素都包含一个指向前一个元素和一个指向后一个元素的引用。这使得在链表中插入和删除元素更为高效,因为不需要移动其他元素。

  2. 不适合随机访问: 由于是链表结构,LinkedList在随机访问元素时效率较低。访问某个特定位置的元素需要从头或尾开始遍历链表。

  3. 元素添加和删除高效: 在链表中插入和删除元素的操作相对较快,因为只需要更新相邻元素的引用,而不需要像数组一样移动大量元素。

  4. 不同步: LinkedList也是非线程安全的,如果需要在多线程环境中使用,需要进行外部同步。

API

boolean add(E element)将指定的元素添加到列表的末尾。
void add(int index, E element)在指定的位置插入指定的元素
E get(int index):返回列表中指定位置的元素
E getFirst()返回列表中的第一个元素
E getLast():返回列表中的最后一个元素。
boolean remove(Object o)从列表中删除指定的元素(如果存在)
E remove(int index):删除列表中指定位置的元素。
E removeFirst():删除并返回列表的第一个元素
E removeLast()删除并返回列表的最后一个元素
boolean contains(Object o)如果列表包含指定的元素,则返回 true。
void clear()从列表中删除所有元素
E set(int index, E element):用指定的元素替换列表中指定位置的元素。
boolean isEmpty():如果列表不包含元素,则返回 true。
int indexOf(Object o)返回列表中第一次出现的指定元素的索引;如果列表不包含此元素,则返回
boolean offer(E e)将指定的元素添加到列表的末尾(队尾)。
E poll():检索并删除列表的头部(队首)元素。
void push(E e):将元素推入列表所表示的堆栈(在列表的头部)。
E pop():从列表所表示的堆栈中弹出第一个元素。
Object[] toArray():返回包含列表中所有元素的数组。

示例代码:

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // 创建LinkedList
        LinkedList<String> linkedList = new LinkedList<>();

        // 添加元素
        linkedList.add("Java");
        linkedList.add("Python");
        linkedList.add("C++");

        // 访问元素
        System.out.println("First element: " + linkedList.getFirst());

        // 删除元素
        linkedList.remove("Python");

        // 打印所有元素
        System.out.println("All elements: " + linkedList);
    }
}

适用场景:

  • 当需要频繁执行插入和删除操作时,特别是在列表的中间位置。
  • 当对列表进行迭代操作而不是随机访问时。

总体而言,LinkedListArrayList各有优势,选择取决于具体的使用场景。ArrayList适用于随机访问和大量元素的存储,而LinkedList适用于频繁插入和删除的场景。

文章来源:https://blog.csdn.net/m0_62645012/article/details/135036748
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。