探秘 Java ArrayList 集合：解锁数据存储新姿势_arraylist的存储

个人主页

JAVA专栏

文章目录

• • 个人主页
  • JAVA专栏
  • 一、引言
  • 二、为什么需要集合
  • • 2.1 数组的弊端
    • 2.2 集合的优势
    • 2.3 集合存储数据类型的特点
    • • 2.3.1 数组存储类型
      • 2.3.2 集合存储类型
    • 2.4 集合和数组的对比
  • 三、集合：ArrayList
  • • 3.1 ArrayList 概述
    • 3.2 创建 ArrayList 对象
    • 3.3 ArrayList 底层实现原理
    • 3.4 ArrayList 成员方法
    • • 3.4.1 添加元素
      • 3.4.2 删除元素
      • 3.4.3 修改元素
      • 3.4.4 获取元素
      • 3.4.5 删除指定索引的元素
      • 3.4.6 获取集合长度
      • 3.4.7 遍历集合
  • 四、ArrayList 的性能分析
  • • 4.1 时间复杂度
    • 4.2 空间复杂度
  • 五、总结
  • • 4.2 空间复杂度
  • 五、总结

一、引言

在 Java 编程中，我们经常需要处理多个元素的数据。数组是一种基本的数据存储方式，但它存在一些局限性，比如长度固定。为了更灵活地处理数据，Java 提供了集合框架，它能根据元素的添加或删除自动调整大小，并且提供了丰富的操作方法。

二、为什么需要集合

2.1 数组的弊端

当我们想要同时存储多个元素时，首先会想到数组。例如：

int[] arr = new int[3];

数组的优点是可以快速访问元素，通过索引可以直接定位到元素。然而，数组的长度是固定的。一旦数组创建，其长度就不能再改变。如果我们需要存储更多的元素，就需要创建一个新的数组，并将原数组的元素复制过去，这无疑增加了代码的复杂性和性能开销。

2.2 集合的优势

集合的出现解决了数组长度固定的问题。集合的长度是可变的，可以随着元素的添加自动扩容。例如，我们可以使用 ArrayList 来存储多个元素，而无需担心长度的限制。

2.3 集合存储数据类型的特点

2.3.1 数组存储类型

数组既可以存储基本数据类型，也可以存储引用数据类型。例如：

int[] arr1 = new int[3]; // 存储基本数据类型class User { String name; int age; public User(String name, int age) { this.name = name; this.age = age; }}User u1 = new User(\"小红\", 13);User u2 = new User(\"小明\", 13);User[] userArr = new User[2];userArr[0] = u1;userArr[1] = u2; // 存储引用数据类型

2.3.2 集合存储类型

集合只能存储引用数据类型。如果要存储基本数据类型，需要将其转换为对应的包装类。这是因为 Java 集合框架是基于泛型实现的，而泛型只能接受引用类型。例如，要存储整数，我们需要使用 Integer 包装类：

import java.util.ArrayList;ArrayList<Integer> list = new ArrayList<>();list.add(1); // 自动装箱，将 int 类型的 1 转换为 Integer 类型

2.4 集合和数组的对比

对比项 数组 集合 长度 长度固定，创建后不能改变 长度可变，可根据元素数量自动调整 存储类型 可以存储基本数据类型和引用数据类型 只能存储引用数据类型，存储基本数据类型需使用包装类 操作灵活性 操作相对简单，主要通过索引访问和修改元素 提供了丰富的操作方法，如添加、删除、修改、查找等

三、集合：ArrayList

3.1 ArrayList 概述

ArrayList 是 Java 集合框架中最常用的类之一，它实现了 List 接口，底层基于数组实现。ArrayList 允许存储重复元素，并且可以根据需要动态调整大小。

3.2 创建 ArrayList 对象

import java.util.ArrayList;public class ArrayListExample { public static void main(String[] args) { // 1. 创建集合的对象 // 泛型：限定集合中存储的数据类型 ArrayList<String> list = new ArrayList<String>(); // JDK 7 以后，泛型的类型可以省略，但是前后必须一致，就是右边  里面可以不写 // 此时我们创建的是 ArrayList 的对象，而 ArrayList 是 Java 已经写好的一个类 // 这个类在底层做了一些处理，打印对象不是地址值，而是集合中的内容 // 在展示的时候，它会拿 [] 把里面的内容给框起来 System.out.println(list); }}// 运行结果: []

在上述代码中，我们创建了一个 ArrayList 对象，并指定了泛型类型为 String，表示该集合只能存储 String 类型的元素。

3.3 ArrayList 底层实现原理

ArrayList 底层使用一个动态数组来存储元素。当我们创建一个 ArrayList 对象时，会默认分配一个初始容量（通常为 10）。当添加元素时，如果数组的容量不足，ArrayList 会自动进行扩容。扩容的过程是创建一个新的数组，其容量通常是原数组的 1.5 倍，然后将原数组的元素复制到新数组中。

3.4 ArrayList 成员方法

方法名 说明 boolean add (E e) 添加元素，返回值表示是否添加成功 boolean remove (E e) 删除指定元素，返回值表示是否删除成功 E set (int index , E e) 修改指定索引下的元素，返回原来的元素 E get (int index) 获取指定索引的元素 E remove (int index) 删除指定索引下的元素，返回原来的元素 int size () 集合的长度，也就是集合中元素的个数

3.4.1 添加元素

import java.util.ArrayList;public class ArrayListAddExample { public static void main(String[] args) { ArrayList<String> list = new ArrayList<>(); boolean b1 = list.add(\"aaa\"); list.add(\"bbb\"); list.add(\"ccc\"); System.out.println(list); System.out.println(b1); }}

add(E e) 方法用于向集合中添加元素，返回值表示是否添加成功。在 ArrayList 中，该方法通常返回 true，因为它总是可以成功添加元素。

3.4.2 删除元素

import java.util.ArrayList;public class ArrayListRemoveExample { public static void main(String[] args) { ArrayList<String> list = new ArrayList<>(); list.add(\"aaa\"); list.add(\"bbb\"); list.add(\"ccc\"); list.remove(\"aaa\"); System.out.println(list); }}

remove(E e) 方法用于删除指定元素，返回值表示是否删除成功。如果集合中存在该元素，则删除并返回 true；否则返回 false。

3.4.3 修改元素

import java.util.ArrayList;public class ArrayListSetExample { public static void main(String[] args) { ArrayList<String> list = new ArrayList<>(); list.add(\"aaa\"); list.add(\"bbb\"); list.set(0, \"ddd\"); System.out.println(list); }}

set(int index, E e) 方法用于修改指定索引下的元素，返回原来的元素。

3.4.4 获取元素

import java.util.ArrayList;public class ArrayListGetExample { public static void main(String[] args) { ArrayList<String> list = new ArrayList<>(); list.add(\"aaa\"); list.add(\"bbb\"); String s = list.get(0); System.out.println(s); }}

get(int index) 方法用于获取指定索引的元素。

3.4.5 删除指定索引的元素

import java.util.ArrayList;public class ArrayListRemoveIndexExample { public static void main(String[] args) { ArrayList<String> list = new ArrayList<>(); list.add(\"aaa\"); list.add(\"bbb\"); String removed = list.remove(0); System.out.println(list); System.out.println(removed); }}

remove(int index) 方法用于删除指定索引下的元素，返回原来的元素。

3.4.6 获取集合长度

import java.util.ArrayList;public class ArrayListSizeExample { public static void main(String[] args) { ArrayList<String> list = new ArrayList<>(); list.add(\"aaa\"); list.add(\"bbb\"); int size = list.size(); System.out.println(size); }}

size() 方法用于获取集合的长度，即集合中元素的个数。

3.4.7 遍历集合

import java.util.ArrayList;public class ArrayListTraversalExample { public static void main(String[] args) { ArrayList<String> list = new ArrayList<>(); list.add(\"aaa\"); list.add(\"bbb\"); list.add(\"ccc\"); // 普通 for 循环遍历 for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)); } // 增强 for 循环遍历 for (String element : list) { System.out.println(element); } // 使用迭代器遍历 java.util.Iterator<String> iterator = list.iterator(); while (iterator.hasNext()) { System.out.println(iterator.next()); } }}

在上述代码中，我们展示了三种遍历 ArrayList 的方式：普通 for 循环、增强 for 循环和迭代器。不同的遍历方式适用于不同的场景，例如，普通 for 循环可以在遍历过程中修改元素，而增强 for 循环和迭代器则更简洁。

四、ArrayList 的性能分析

4.1 时间复杂度

• 添加元素：在列表末尾添加元素的时间复杂度为 (O(1))，但在中间或开头添加元素需要移动后续元素，时间复杂度为 (O(n))。
• 删除元素：删除末尾元素的时间复杂度为 (O(1))，删除中间或开头元素需要移动后续元素，时间复杂度为 (O(n))。
• 查找元素：通过索引查找元素的时间复杂度为 (O(1))，通过元素值查找元素需要遍历列表，时间复杂度为 (O(n))。
• 修改元素：通过索引修改元素的时间复杂度为 (O(1))。

4.2 空间复杂度

ArrayList 的空间复杂度主要取决于存储的元素数量和数组的容量。在扩容时，会额外分配一定的空间，因此空间复杂度为 (O(n))。

五、总结

复杂度为 (O(1))，删除中间或开头元素需要移动后续元素，时间复杂度为 (O(n))。

• 查找元素：通过索引查找元素的时间复杂度为 (O(1))，通过元素值查找元素需要遍历列表，时间复杂度为 (O(n))。
• 修改元素：通过索引修改元素的时间复杂度为 (O(1))。

4.2 空间复杂度

ArrayList 的空间复杂度主要取决于存储的元素数量和数组的容量。在扩容时，会额外分配一定的空间，因此空间复杂度为 (O(n))。

五、总结

ArrayList 是 Java 集合框架中一个非常实用的类，它提供了动态数组的功能，方便我们存储和操作多个元素。通过了解 ArrayList 的底层实现原理、成员方法和性能特点，我们可以在实际开发中更加合理地使用它，提高代码的性能和可维护性。同时，我们也应该注意 ArrayList 在某些场景下的局限性，例如在频繁插入和删除元素的场景下，性能可能不如其他集合类，如 LinkedList。