js arraylist 收藏 0

java.util.ArrayList 原理详细介绍

本文旨在介绍 java.util.ArrayList<E> 集合类的实现原理；

ArrayList 底层是基于数组实现的，集合所有的操作都是对数组的操作，即是由数组实现的各种方法功能。

内部封装了一个动态再分配的数组，即ArrayList 大小是可变的；

是非线程安全的，java.util.Vector<E> 是线程安全的；

ArrayList 不是 java 程序设计语言的一部分，是某人编写放进标准库的一个使用工具；

ArrayList 中元素是有序可重复的；

1、空构造函数

2、指定集合容量

指定的容量其实就是底层数组的大小；

3、指定集合构造 ArrayList

1）指定集合为空，则构造空数组的 ArrayList 对象；

2）指定集合类型是 ArrayList，则直接转成数组赋值给内部数组对象；

3）指定集合类型是非 ArrayList，则转成数组后，copy元素来创建内部数组对象；

1、添加元素 add(E e)

1）modCount 加 1；

2）容量超过数组大小则扩容；

3）在数组后面的空位置插入元素；

2、添加元素 add(int index, E element)

1）在指定索引位置插入指定的元素；

2）index 取值范围为 [0, size]，超出则抛下标越界异常；

3）其他同 add(E e) 方法；

3、查询元素 get(int index)

1）获取指定索引位置的元素；

4、替换元素 set(int index, E element)

1）替换指定索引位置的元素为指定的元素，并返回旧元素（即被替换的元素）；

5、删除元素 remove(int index)

1）删除指定索引位置的元素，并返回被删除的元素；

6、删除元素 remove(Object o)

1）删除集合中第一个和指定元素相等的元素；

2）入参对象可以为 null；

7、获取大小 size()

1）取集合大小，即集合中有多少个元素；

8、判断集合是否为空 isEmpty()

1）如果集合中元素个数为0，则表示集合是空的；

9、获取指定元素在集合中索引位置 indexOf(Object o)

1）入参对象可以为 null，为 null 时取内部数组中第一个为 null 的元素的索引；

2）入参对象不为 null 时，取内部数组中第一个和入参对象相等的元素的索引；

10、获取指定元素在集合中最后的索引位置 lastIndexOf(Object o)

1）从后往前找，从内部数组中找出第一个和指定元素相同的索引位置；

2）其他同 indexOf(Object o)；

11、集合中是否包含指定元素 contains(Object o)

1）调用了 indexOf(Object o) 方法，如果返回的索引值大于或等于0，则说明包含指定的元素；

2）入参对象可以为 null；

12、清空集合 clear()

1）其实就是循环内部数组，把前 size 个元素赋值为 null；

13、集合转数组 toArray()

1）把 ArrayList 集合转成 Object[] 集合；

2）返回类型是 Object[]；

3）其实是根据集合内部数组，复制出一个新的数组返回；

14、集合转数组 toArray(T[] a)

1）该方法会返回指定类型的元素数组；

2）传入的数组 T[] 的长度小于集合大小时，根据集合内部数组，复制出一个新的数组返回，并强转成类型 T[]，返回的数组和集合内部数组相同；

3）如果传入的数组的长度大于或等于集合大小时，把集合内部数组所有元素复制到数组 T[] 中，并返回 T[]；

15、取交集 retainAll(Collection<?> c)

1）a.retainAll(b) 把a集合中未出现在b集合中的元素删除，相当于取两个集合的交集；

16、获取迭代器 iterator()

1）java.util.ArrayList.Itr<E> 是 ArrayList 的内部类，实现了 java.util.Iterator<E> 迭代器接口；

17、获取子集 subList(int fromIndex, int toIndex)

1）java.util.ArrayList.SubList<E> 是 ArrayList 的内部类；

18、给集合中元素排序 sort(Comparator<? super E> c)

1）必须指定用于元素比较的比较器；

2）内部调用了 java.util.Arrays.sort(T[], int, int, Comparator<? super T>) 工具类排序方法；

19、replaceAll(UnaryOperator<E> operator)

1）把集合中所有的元素都进行相同的操作；

20、removeIf(Predicate<? super E> filter)

1）把集合中符合条件的元素全部删掉；

Java 中的 ArrayList 和 LinkedList：使用场景与案例

在 Java 编程中，ArrayList 和 LinkedList 是两个非常常用的集合类。虽然它们都可以用来存储元素，但它们的内部实现和使用场景却有很大不同。理解这两者的特性，能够帮助我们在编程时选择合适的集合，提升程序的效率。接下来，我们就通过一些简单的案例来看看这两者的区别以及适用场景。

• 内部实现：ArrayList 是用动态数组来实现的。它内部有一个数组来存储元素。
• 访问速度：由于是数组，随机访问元素非常快，比如通过索引获取元素的速度是 O(1)。
• 插入和删除：在数组末尾插入元素比较快（平均时间复杂度 O(1)），但在中间插入或删除元素时，就需要移动后面的元素，时间复杂度变成 O(n)。

• 内部实现：LinkedList 是用链表来实现的。每个元素都有一个指向下一个元素的引用（双向链表），所以内存不一定是连续的。
• 访问速度：随机访问速度较慢，时间复杂度是 O(n)，因为需要从头开始遍历链表。
• 插入和删除：在链表的头部或尾部插入或删除元素非常快，时间复杂度是 O(1)，但在中间位置操作时，还是需要遍历链表，时间复杂度是 O(n)。

• 场景一：快速随机访问

如果你需要频繁访问某些元素，ArrayList 是更好的选择。比如，你在做一个商品管理系统，用户需要根据索引快速查找商品信息。

案例：商品管理系统

在这个例子中，ArrayList 让我们可以快速地通过索引获取产品信息。

• 场景二：需要频繁访问和迭代

当需要反复遍历并且访问速度很重要时，ArrayList 是个好选择。例如，加载一批用户数据进行分析。

在这种情况下，ArrayList 的顺序存储让迭代变得高效。

• 场景一：频繁插入和删除

当你需要频繁在列表中间插入或删除元素时，LinkedList 更加合适。例如，维护一个待办事项列表，用户可能会经常添加或删除任务。

案例：待办事项列表

在这个例子中，LinkedList 让添加和删除任务变得更高效，特别是在列表中间进行操作时。

• 场景二：实现队列或栈

LinkedList 也很适合用来实现队列或栈的数据结构，因为它可以快速在头部和尾部插入和删除元素。

案例：实现一个简单的队列

在这个示例中，LinkedList 被用作队列，允许我们高效地在头部和尾部插入和删除元素。

• 选择 ArrayList 的场景：
• 当你需要快速访问元素时。
• 当需要频繁进行遍历操作时。
• 当主要是在列表末尾插入或删除元素时。
• 选择 LinkedList 的场景：
• 当需要频繁在中间插入和删除元素时。
• 当需要实现队列或栈等数据结构时。

通过这些简单的案例，你应该能清楚地了解 ArrayList 和 LinkedList 的特点及适用场景。记住，选择合适的集合类，可以大大提高你程序的性能和可维护性。希望这篇文章能帮助你更好地理解和使用这两种集合！

详细介绍一下Java中的ArrayList？

ArrayList是在Java中最为常用的动态数组类，其位于java.util包中，与传统意义上的数组不同，ArrayList中提供了一个可以进行动态大小调整的数组操作，在运行时可以完成动态元素的增删改查，与固定的数组操作比较更加的灵活。

ArrayList是非同步的，不适合多线程环境，如果想要在多线程环境中使用，我们可以通过Collections.synchronizedList方法获得线程安全版本的动态数组操作。

下面我们就来总结一下在Java中的ArrayList的相关操作。

在ArrayList中提供了如下的几个构造方法，用来创建ArrayList。

• 无参构造方法：通过这个构造方法，我们可以初始化一个默认容量为10的空列表，如下所示。

• 指定容量的构造方法：当然除了默认的容量，我们还可以创建一个指定初始容量的ArrayList，从而避免了因频繁扩容带来的性能损耗。

• 通过集合初始化：我们也可以通过一个已有集合来初始化ArrayList。

添加元素

• add(E e)：在列表末尾添加元素。

• add(int index, E e)：在指定位置插入元素。

获取元素

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

修改元素

• set(int index, E element)：更新指定位置的元素。

删除元素

• remove(int index)：删除指定位置的元素。

• remove(Object o)：删除首次出现的指定元素。

其他常用方法

• size()：返回列表的元素数量。
• isEmpty()：判断列表是否为空。
• contains(Object o)：判断列表是否包含指定元素。
• indexOf(Object o) 和 lastIndexOf(Object o)：返回元素首次和最后一次出现的位置。
• clear()：清空列表中的所有元素。

动态扩容原理

当 ArrayList 中的元素数量超过其容量时，会自动扩容，新的容量通常是旧容量的 1.5 倍。扩容需要将所有元素复制到新数组中，因此扩容操作相对耗时，最好在创建 ArrayList 时指定容量，减少扩容频率。

元素存储

ArrayList使用数组Object[] elementData 存储元素。添加、删除、访问元素时，ArrayList的大多数操作都是基于这个数组。

ArrayList支持多种遍历方式

for-each 循环

传统 for 循环（通过索引访问）

迭代器

优点

• 支持动态扩容，存储容量灵活。
• 支持随机访问，通过索引查找元素速度快（时间复杂度为 O(1)）。

缺点

• 扩容需要重新分配内存并复制元素，效率相对较低。
• 插入和删除元素可能需要移动大量元素（尤其在列表开头或中间位置插入和删除），时间复杂度为 O(n)。
• 线程不安全，若在多线程环境中使用，需要额外处理同步问题。

与其他集合的区别

与 LinkedList：LinkedList是双向链表，适合频繁插入和删除元素的操作，而ArrayList更适合随机访问和遍历操作。

与 Vector：Vector是线程安全的动态数组实现，而ArrayList是非同步的，性能更高。

ArrayList是Java中基于动态数组实现的集合类，提供了大小可变的数组，支持按索引快速访问元素。它允许存储重复元素和null值，且在元素添加、删除时会自动扩容。ArrayList的主要优点是随机访问速度快（O(1)），但在列表开头或中间插入、删除元素的效率较低（O(n)）。它是非线程安全的，适合单线程环境中需要频繁访问元素的场景。

本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com