码上焚香

Yahocen

细说 ArrayList

6
2024-09-07

ArrayList 是基于动态数组实现的。动态数组是一种可以在运行时动态调整大小的数组结构。下面是关于 ArrayList 的一些关键特性和如何基于动态数组实现的解释

ArrayList 的特点

  1. 动态调整大小

    1. ArrayList 会在需要的时候自动调整其内部数组的大小,这意味着当你添加或删除元素时,ArrayList 会自动管理底层数组的扩容或缩减

  2. 线程非安全

    1. ArrayList 的实现是非线程安全的,这意味着在多线程环境下直接修改 ArrayList 的内容可能会导致数据不一致的问题。如果需要线程安全的行为,可以考虑使用 Vector 或者通过 Collections.synchronizedList 包装 ArrayList

  3. 索引访问

    1. ArrayList 提供了快速的随机访问(O(1) 时间复杂度),因为它是基于数组实现的。你可以通过索引来访问或修改元素

  4. 插入和删除操作

    1. 插入和删除操作的时间复杂度取决于插入或删除的位置。如果在数组的中间插入或删除元素,所有后面的元素都需要向前或向后移动一位,因此这些操作的时间复杂度为 O(n)。

ArrayList 的内部实现

底层数组

ArrayList 内部维护了一个数组(通常是 Object 类型的数组),用于存储实际的数据。这个数组在创建时会被初始化为一定的大小,当数组空间不足时,ArrayList 会创建一个新的更大的数组,并将旧数组中的所有元素复制到新数组中。

扩容机制

ArrayList 需要添加元素而内部数组已满时,它会创建一个新的数组,通常新的数组大小比原数组大 50%(即扩容因子,默认情况下,ArrayList 的容量每次扩大 1.5 倍)。然后,将旧数组中的所有元素复制到新数组中,并将引用指向新数组。

主要是方法

  • add(E e):向 ArrayList 的末尾添加一个元素。

  • get(int index):返回指定位置的元素。

  • set(int index, E element):替换指定位置的元素。

  • remove(int index):移除指定位置的元素。

  • size():返回 ArrayList 中的元素数量。

  • isEmpty():判断 ArrayList 是否为空。

  • clear():清空 ArrayList 中的所有元素。