个人主页
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。
