JAVA数据结构 DAY4-ArrayList

本系列可作为JAVA学习系列的笔记，文中提到的一些练习的代码，小编会将代码复制下来，大家复制下来就可以练习了，方便大家学习。

点赞关注不迷路！您的点赞、关注和收藏是对小编最大的支持和鼓励！ 

系列文章目录

JAVA初阶———已更完

JAVA数据结构 DAY1-集合和时空复杂度

JAVA数据结构 DAY2-包装类和泛型

JAVA数据结构 DAY3-List接口

JAVA数据结构 DAY4-ArrayList

目录

目录

系列文章目录

目录

前言

一、基础铺垫：线性表与顺序表

1. 线性表

2. 顺序表

二、ArrayList 核心解析

1. ArrayList 类结构与特性

2. 构造方法

3. 常用操作

4. 遍历方式

（1）for 循环 + 下标（最常用）

（2）foreach 循环（简洁）

（3）迭代器（Iterator）

三、深度剖析：ArrayList 扩容机制

1. 核心源码解析

2. 扩容流程总结

3. 扩容相关问题

四、实战案例：ArrayList 的实际应用

1. 扑克牌游戏（洗牌与发牌）

实现步骤：

代码实现：

核心知识点：

2. 杨辉三角（基于 ArrayList 构建）

代码实现：

输出结果：

五、ArrayList 的局限性与优化思考

1. 核心局限性

2. 优化思路

六、总结

总结

前言

小编作为新晋码农一枚，会定期整理一些写的比较好的代码，作为自己的学习笔记，会试着做一下批注和补充，如转载或者参考他人文献会标明出处，非商用，如有侵权会删改！欢迎大家斧正和讨论！

在 Java 开发中，ArrayList 是使用频率极高的集合类。它基于动态数组实现，兼顾了随机访问的高效性与灵活扩容的特性，成为存储和操作数据的首选工具之一。本文将从线性表基础概念出发，全面剖析 ArrayList 的底层原理、核心用法、扩容机制，并通过实战案例加深理解，最后探讨其局限性与优化思路。

一、基础铺垫：线性表与顺序表

要理解 ArrayList，首先需要明确两个核心概念：线性表和顺序表。

1. 线性表

线性表（linear list）是 n 个具有相同特性的数据元素的有限序列，是一种逻辑结构上呈线性（连续一条直线）的数据结构。它在实际开发中应用广泛，常见的线性表包括顺序表、链表、栈、队列等。

关键特性：

• 逻辑结构连续：元素之间存在 “一对一” 的相邻关系
• 物理结构灵活：存储时不一定连续，通常以数组（顺序存储）或链式结构（离散存储）实现

2. 顺序表

顺序表是线性表的一种具体实现，它使用一段物理地址连续的存储单元依次存储数据元素，本质上是基于数组的线性结构。我们可以通过自定义顺序表理解其核心设计：

public class SeqList {
private int[] array; // 底层存储数组
private int size; // 有效元素个数

// 构造方法：默认构造、指定初始容量构造
SeqList() {}
SeqList(int initcapacity) {}

// 核心操作：增删查改
public void add(int data) {} // 尾插元素
public void add(int pos, int data) {} // 指定位置插入
public boolean contains(int toFind) { return true; } // 包含判断
public int indexOf(int toFind) { return -1; } // 查找元素位置
public int get(int pos) { return -1; } // 获取指定位置元素
public void set(int pos, int value) {} // 修改指定位置元素
public void remove(int toRemove) {} // 删除元素
public int size() { return 0; } // 获取长度
public void clear() {} // 清空表
public void display() {} // 打印（测试用）
}

顺序表的核心优势是支持随机访问（通过下标直接定位元素），但短板也很明显：插入删除需要移动后续元素，效率较低。

二、ArrayList 核心解析

ArrayList 是 Java 集合框架中顺序表的实现类，在日常开发中几乎无处不在。下面从类结构、构造方法、常用操作、遍历方式四个维度全面解析。

1. ArrayList 类结构与特性

ArrayList 的类继承关系如下：Iterable <- Collection <- AbstractCollection <- List <- AbstractList <- ArrayList

同时实现了三个关键接口，赋予其特殊能力：

• RandomAccess：支持随机访问，可通过下标快速获取元素
• Cloneable：支持克隆，可通过 clone () 方法创建副本
• Serializable：支持序列化，可在网络传输或文件存储中使用

核心特性总结：

• 泛型实现：使用时需指定元素类型（如List<Integer>），避免类型转换错误
• 非线程安全：单线程环境使用，多线程需选择 Vector 或 CopyOnWriteArrayList
• 动态扩容：底层是连续空间，容量不足时自动扩容
• 基于数组：本质是动态数组，继承了数组随机访问的优势

2. 构造方法

ArrayList 提供三种构造方式，满足不同使用场景：

注意事项：

• 推荐使用泛型指定元素类型，避免使用无泛型的原始类型（如List list = new ArrayList()），否则可能存储任意类型元素，引发类型转换异常
• 指定初始容量适用于已知数据量的场景，可减少扩容次数，提升性能

3. 常用操作

ArrayList 提供了丰富的方法用于数据操作，核心常用方法如下：

示例代码：

public static void main(String[] args) {
List<String> list = new ArrayList<>();
// 尾插元素
list.add("JavaSE");
list.add("JavaWeb");
list.add("JavaEE");
System.out.println(list); // [JavaSE, JavaWeb, JavaEE]

// 获取有效元素个数
System.out.println(list.size()); // 3

// 获取和修改元素
System.out.println(list.get(1)); // JavaWeb
list.set(1, "JavaWEB");
System.out.println(list.get(1)); // JavaWEB

// 指定位置插入
list.add(1, "Java数据结构");
System.out.println(list); // [JavaSE, Java数据结构, JavaWEB, JavaEE]

// 删除元素
list.remove("JavaEE");
System.out.println(list); // [JavaSE, Java数据结构, JavaWEB]
list.remove(list.size() – 1);
System.out.println(list); // [JavaSE, Java数据结构]

// 包含判断与查找
System.out.println(list.contains("JavaSE")); // true
list.add("JavaSE");
System.out.println(list.indexOf("JavaSE")); // 0
System.out.println(list.lastIndexOf("JavaSE")); // 2

// 截取子列表
List<String> subList = list.subList(0, 2);
System.out.println(subList); // [JavaSE, Java数据结构]

// 清空
list.clear();
System.out.println(list.size()); // 0
}

4. 遍历方式

ArrayList 支持三种遍历方式，各有适用场景：

（1）for 循环 + 下标（最常用）

利用数组随机访问特性，效率最高，适用于需要下标操作的场景：

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}

（2）foreach 循环（简洁）

语法简洁，无需关注下标，适用于仅遍历元素的场景：

for (Integer num : list) {
System.out.print(num + " ");
}

（3）迭代器（Iterator）

集合通用遍历方式，支持遍历过程中删除元素（需使用迭代器的 remove 方法）：

Iterator<Integer> it = list.listIterator();
while (it.hasNext()) {
System.out.print(it.next() + " ");
}

注意：遍历过程中避免使用集合的 remove 方法，可能引发 ConcurrentModificationException 异常，如需删除应使用迭代器的 remove 方法。

三、深度剖析：ArrayList 扩容机制

ArrayList 的 “动态” 特性核心在于扩容机制 —— 当底层数组容量不足时，自动申请更大的空间，拷贝原有数据，实现容量动态增长。

1. 核心源码解析

先看 ArrayList 扩容相关的核心源码（JDK8）：

// 底层存储元素的数组
transient Object[] elementData;
// 默认空数组（无参构造初始化用）
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;
// 最大数组容量（避免OOM）
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8;

// 尾插元素时触发扩容检查
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 检查是否需要扩容
elementData[size++] = e;
return true;
}

// 计算最小所需容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 无参构造创建的空数组，首次扩容时使用默认容量10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

// 确认是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 结构修改计数器（用于快速失败机制）
// 所需容量超过当前数组长度，触发扩容
if (minCapacity – elementData.length > 0) {
grow(minCapacity);
}
}

// 扩容核心方法
private void grow(int minCapacity) {
int oldCapacity = elementData.length; // 旧容量
int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍扩容（右移1位等价于除以2）

// 若1.5倍扩容后仍不足，直接使用所需容量
if (newCapacity – minCapacity < 0) {
newCapacity = minCapacity;
}

// 若容量超过最大值，使用Integer.MAX_VALUE或MAX_ARRAY_SIZE
if (newCapacity – MAX_ARRAY_SIZE > 0) {
newCapacity = hugeCapacity(minCapacity);
}

// 拷贝原有数据到新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}

// 处理超大容量需求
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) {
throw new OutOfMemoryError(); // 内存溢出
}
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

2. 扩容流程总结

3. 扩容相关问题

问题：以下代码是否有缺陷？

List<Integer> list = new ArrayList<>();
for (int i = 0; i < 100; i++) {
list.add(i);
}

分析：无参构造的 ArrayList 初始容量为 10，添加第 11 个元素时触发第一次扩容（10→15），添加第 16 个元素时触发第二次扩容（15→22）…… 直到容量满足 100 个元素需求。多次扩容会产生多次数组拷贝，存在性能开销。

优化方案：已知数据量时，使用指定初始容量的构造方法（new ArrayList<>(100)），避免多次扩容。

四、实战案例：ArrayList 的实际应用

理论结合实践，通过两个经典案例掌握 ArrayList 的使用场景。

1. 扑克牌游戏（洗牌与发牌）

需求：创建一副扑克牌，实现洗牌功能，然后分给 3 个人，每人 5 张牌。

实现步骤：

代码实现：

// 扑克牌类
class Card {
public int rank; // 牌面值（1-13）
public String suit; // 花色

@Override
public String toString() {
return String.format("[%s %d]", suit, rank);
}
}

public class CardDemo {
// 四种花色
public static final String[] SUITS = {"♠", "♥", "♣", "♦"};

// 购买一副牌（52张）
private static List<Card> buyDeck() {
List<Card> deck = new ArrayList<>(52);
for (int i = 0; i < 4; i++) { // 遍历花色
for (int j = 1; j <= 13; j++) { // 遍历牌面值
Card card = new Card();
card.suit = SUITS[i];
card.rank = j;
deck.add(card);
}
}
return deck;
}

// 交换元素（洗牌核心）
private static void swap(List<Card> deck, int i, int j) {
Card temp = deck.get(i);
deck.set(i, deck.get(j));
deck.set(j, temp);
}

// 洗牌算法（从后往前随机交换）
private static void shuffle(List<Card> deck) {
Random random = new Random();
for (int i = deck.size() – 1; i > 0; i–) {
int randomIndex = random.nextInt(i); // 生成[0, i)之间的随机数
swap(deck, i, randomIndex);
}
}

public static void main(String[] args) {
// 1. 买牌
List<Card> deck = buyDeck();
System.out.println("刚买回来的牌：");
System.out.println(deck);

// 2. 洗牌
shuffle(deck);
System.out.println("\\n洗过的牌：");
System.out.println(deck);

// 3. 发牌（3人，每人5张）
List<List<Card>> hands = new ArrayList<>();
hands.add(new ArrayList<>()); // A玩家
hands.add(new ArrayList<>()); // B玩家
hands.add(new ArrayList<>()); // C玩家

for (int i = 0; i < 5; i++) { // 发5轮
for (int j = 0; j < 3; j++) { // 分给3个玩家
hands.get(j).add(deck.remove(0)); // 移除第一张牌分给玩家
}
}

// 4. 展示结果
System.out.println("\\n剩余的牌：");
System.out.println(deck);
System.out.println("\\nA手中的牌：");
System.out.println(hands.get(0));
System.out.println("B手中的牌：");
System.out.println(hands.get(1));
System.out.println("C手中的牌：");
System.out.println(hands.get(2));
}
}

核心知识点：

• ArrayList 的批量添加、删除、修改操作
• 洗牌算法的实现（随机交换元素）
• 嵌套 List 的使用（存储多个玩家的牌）

2. 杨辉三角（基于 ArrayList 构建）

杨辉三角的特点：

• 第 n 行有 n 个元素
• 每行的首尾元素都是 1
• 中间元素 = 上一行相邻两个元素之和

代码实现：

public class YangHuiTriangle {
public static List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();

// 第一行（只有1）
triangle.add(new ArrayList<>());
triangle.get(0).add(1);

// 生成第2行到第numRows行
for (int i = 1; i < numRows; i++) {
List<Integer> currentRow = new ArrayList<>();
List<Integer> prevRow = triangle.get(i – 1);

// 每行第一个元素为1
currentRow.add(1);

// 中间元素：上一行相邻两个元素之和
for (int j = 1; j < i; j++) {
currentRow.add(prevRow.get(j – 1) + prevRow.get(j));
}

// 每行最后一个元素为1
currentRow.add(1);

triangle.add(currentRow);
}

return triangle;
}

public static void main(String[] args) {
List<List<Integer>> result = generate(5);
// 打印杨辉三角
for (List<Integer> row : result) {
System.out.println(row);
}
}
}

输出结果：

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]

五、ArrayList 的局限性与优化思考

ArrayList 虽好用，但并非万能，其底层实现决定了它存在以下局限性：

1. 核心局限性

• 插入删除效率低：任意位置插入 / 删除元素时，需要移动后续元素，时间复杂度为 O (N)
• 扩容开销大：扩容时需要申请新空间、拷贝数据、释放旧空间，频繁扩容会影响性能
• 空间浪费：扩容通常按 1.5 倍增长，可能导致部分空间闲置（如容量 200 但仅存储 105 个元素，浪费 95 个空间）
• 线程不安全：多线程环境下并发修改可能导致数据不一致或 ConcurrentModificationException 异常

2. 优化思路

针对以上问题，可通过以下方式优化：

• 已知数据量时，初始化指定初始容量，减少扩容次数
• 批量添加元素时，使用addAll方法，避免多次触发扩容
• 频繁插入删除操作时，改用 LinkedList（基于链表实现，插入删除效率 O (1)）
• 多线程环境下，使用 Vector（线程安全，效率较低）或 CopyOnWriteArrayList（读写分离，适合读多写少场景）
• 若空间紧张，可手动调用trimToSize()方法，将数组容量缩减为当前有效元素个数（注意：后续添加元素会再次触发扩容）

六、总结

ArrayList 是 Java 中最基础、最常用的集合类，其本质是动态扩容的顺序表，核心优势是随机访问效率高（O (1)），适用于读多写少、需要频繁访问元素的场景。

本文从基础概念出发，依次讲解了线性表与顺序表的定义、ArrayList 的类结构与核心用法、扩容机制的底层实现，通过扑克牌和杨辉三角两个实战案例巩固应用，最后分析了其局限性与优化方向。

掌握 ArrayList 的核心原理，不仅能在开发中灵活运用，更能理解数据结构中 “顺序存储” 的设计思想，为后续学习链表、栈、队列等数据结构打下基础。在实际开发中，应根据业务场景选择合适的集合类 —— 没有最好的集合，只有最适合的集合！

总结

以上就是今天要讲的内容，本文简单记录了java数据结构，仅作为一份简单的笔记使用，大家根据注释理解，您的点赞关注收藏就是对小编最大的鼓励！