当前位置： 首页 > news >正文

深入浅出ArrayList：从线性表到洗牌算法，掌握Java集合核心

news 2026/5/29 2:38:20

在Java编程中，数据结构是构建高效程序的基石，而ArrayList作为最常用的集合类之一，理解其背后的原理和用法至关重要。本篇博客将带你全面了解ArrayList，从基本概念到实际应用，一步步掌握这个强大的动态数组实现。

一、数据结构基础：从线性表到顺序表

1.1 什么是线性表？

在开始学习ArrayList之前，我们需要理解其理论基础——线性表。线性表(Linear List)是n个具有相同特性的数据元素的有限序列，是实际编程中最常用的数据结构之一。常见的线性表包括：

  • 顺序表（如数组）

  • 链表

  • 栈

  • 队列

线性表在逻辑上是连续的线性结构，但在物理存储上不一定连续。它可以通过数组（顺序存储）或链式结构（链式存储）来实现。

1.2 顺序表：连续存储的实现

顺序表是线性表的一种实现方式，它使用一段物理地址连续的存储单元依次存储数据元素。简单来说，顺序表就是用数组实现的线性表，在数组上完成数据的增删查改操作。

顺序表的基本结构通常包含：

public class SeqList { private int[] array; // 存储数据的数组 private int size; // 当前有效元素个数 // 构造方法 SeqList(int initCapacity) { array = new int[initCapacity]; size = 0; } }

二、ArrayList：Java中的动态顺序表

2.1 ArrayList简介

ArrayList是Java集合框架中一个普通的类，实现了List接口。文档中明确指出了它的几个重要特性：

  1. 泛型实现：ArrayList以泛型方式实现，使用时必须先实例化

  2. 接口实现：

    • 实现RandomAccess接口，支持随机访问

    • 实现Cloneable接口，可以克隆

    • 实现Serializable接口，支持序列化

  3. 线程安全：ArrayList不是线程安全的，在单线程下使用，多线程中可选择Vector或CopyOnWriteArrayList

  4. 底层结构：ArrayList底层是一段连续的空间，可以动态扩容，是一个动态类型的顺序表

2.2 ArrayList的构造方法

文档中介绍了三种主要的构造方法：

方法

说明

ArrayList()

无参构造，创建空列表

ArrayList(Collection<? extends E> c)

利用其他集合构建ArrayList

ArrayList(int initialCapacity)

指定顺序表初始容量

使用示例：

// 推荐写法：使用List接口引用 List<Integer> list1 = new ArrayList<>(); // 空列表 List<Integer> list2 = new ArrayList<>(10); // 初始容量10 list2.add(1); list2.add(2); list2.add(3); // 利用已有列表构造新列表 ArrayList<Integer> list3 = new ArrayList<>(list2); // 避免使用原始类型（会有类型安全问题） List list4 = new ArrayList(); // 不推荐：可以存放任意类型 list4.add("111"); list4.add(100); // 混合类型，使用时需要强制转换，容易出错

2.3 ArrayList的常用操作

文档中列出了ArrayList的核心操作方法：

方法

功能说明

boolean add(E e)

尾部插入元素e

void add(int index, E element)

在index位置插入元素

E remove(int index)

删除index位置元素

boolean remove(Object o)

删除第一个匹配的元素o

E get(int index)

获取下标index位置的元素

E set(int index, E element)

设置下标index位置的元素

boolean contains(Object o)

判断元素o是否在线性表中

int indexOf(Object o)

返回第一个o的下标

List<E> subList(int from, int to)

截取子列表

实战示例：

List<String> list = new ArrayList<>(); list.add("JavaSE"); list.add("JavaWeb"); list.add("JavaEE"); list.add("JVM"); list.add("测试课程"); System.out.println(list); // 输出整个列表 System.out.println(list.size()); // 获取有效元素个数：5 System.out.println(list.get(1)); // 获取索引1的元素："JavaWeb" list.set(1, "JavaWEB"); // 设置索引1的元素 list.add(1, "Java数据结构"); // 在索引1处插入元素 list.remove("JVM"); // 删除指定元素 list.remove(list.size() - 1); // 删除最后一个元素 if (list.contains("测试课程")) { // 检查是否包含 list.add("测试课程"); } // 查找元素位置 list.add("JavaSE"); System.out.println(list.indexOf("JavaSE")); // 0 System.out.println(list.lastIndexOf("JavaSE")); // 5 // 截取子列表 List<String> subList = list.subList(0, 4);

2.4 ArrayList的遍历方式

文档展示了三种遍历ArrayList的方法：

List<Integer> list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); // 1. for循环+下标（最常用） 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<Integer> it = list.iterator(); while (it.hasNext()) { System.out.print(it.next() + " "); }

注意：ArrayList最常用的遍历方式是for循环+下标以及foreach循环。

三、ArrayList的扩容机制

3.1 为什么需要扩容？

考虑以下代码是否有问题：

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

这段代码完全正确！因为ArrayList是一个动态类型顺序表，在插入元素时会自动扩容。

3.2 扩容机制详解

从文档中的源码分析可以看出ArrayList的扩容流程：

  1. 容量检查：每次添加元素时，调用ensureCapacityInternal(size + 1)检查是否需要扩容

  2. 容量计算：

    • 如果当前数组是默认空数组，返回Math.max(DEFAULT_CAPACITY(10), minCapacity)

    • 否则返回所需最小容量

  3. 显式扩容检查：如果需要的最小容量大于当前数组长度，则调用grow()方法扩容

  4. 扩容计算：

    • 默认按1.5倍扩容：newCapacity = oldCapacity + (oldCapacity >> 1)

    • 如果用户所需大小超过1.5倍，按用户所需大小扩容

    • 检查是否超过最大数组大小限制

  5. 执行扩容：使用Arrays.copyOf()复制到新数组

扩容源码关键逻辑：

private void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍扩容 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 如果1.5倍还不够，使用所需容量 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 处理大容量情况 elementData = Arrays.copyOf(elementData, newCapacity); }

四、ArrayList实战应用

4.1 扑克牌洗牌算法

文档提供了一个完整的扑克牌示例，展示了ArrayList在实际问题中的应用：

// 1. 定义扑克牌类 class Card { public int rank; // 牌面值 public String suit; // 花色 @Override public String toString() { return String.format("[%s%d]", suit, rank); } } // 2. 买一副牌 public class CardDemo { public static final String[] SUITS = {"♠", "♥", "♣", "♦"}; private static List<Card> buyDeck() { List<Card> deck = new ArrayList<>(52); for (int i = 0; i < 4; i++) { // 4种花色 for (int j = 1; j <= 13; j++) { // 13个点数 Card card = new Card(); card.suit = SUITS[i]; card.rank = j; deck.add(card); } } return deck; } // 3. 洗牌算法 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(20190905); // 固定种子，便于测试 for (int i = deck.size() - 1; i > 0; i--) { int r = random.nextInt(i); swap(deck, i, r); } } // 4. 发牌 public static void main(String[] args) { List<Card> deck = buyDeck(); System.out.println("刚买回来的牌：" + deck); shuffle(deck); System.out.println("洗过的牌：" + deck); // 三人轮流抓5张牌 List<List<Card>> hands = new ArrayList<>(); hands.add(new ArrayList<>()); hands.add(new ArrayList<>()); hands.add(new ArrayList<>()); for (int i = 0; i < 5; i++) { for (int j = 0; j < 3; j++) { hands.get(j).add(deck.remove(0)); // 从牌堆顶部取牌 } } System.out.println("A手中的牌：" + hands.get(0)); System.out.println("B手中的牌：" + hands.get(1)); System.out.println("C手中的牌：" + hands.get(2)); System.out.println("剩余的牌：" + deck); } }

4.2 杨辉三角

这是一个经典的二维结构问题，可以使用ArrayList的列表嵌套来实现：

List<List<Integer>> triangle = new ArrayList<>(); // 每一行都是一个ArrayList<Integer>

五、ArrayList的优缺点与思考

5.1 ArrayList的优势

  1. 随机访问高效：支持O(1)时间复杂度的随机访问

  2. 尾部操作高效：在尾部添加元素平均时间复杂度为O(1)

  3. 缓存友好：连续内存存储，缓存命中率高

  4. 接口丰富：提供了完整的List接口实现

5.2 ArrayList的缺点

文档中明确指出了ArrayList的几个问题：

  1. 插入删除效率低：在任意位置插入或删除元素时，需要将后续元素整体移动，时间复杂度为O(N)

  2. 扩容有开销：增容需要申请新空间、拷贝数据、释放旧空间，消耗较大

  3. 空间浪费：增容通常按1.5倍增长，可能造成空间浪费

例如：当前容量为100，满后增容到200，再插入5个数据后，就浪费了95个空间。

5.3 解决方案思考

文档最后提出了一个思考题：如何解决这些问题？

可能的解决方案：

  1. 频繁插入删除：考虑使用LinkedList

  2. 空间浪费：可以使用trimToSize()方法裁剪容量

  3. 预分配空间：如果能预估数据量，创建时指定合适初始容量

  4. 替代方案：根据场景选择合适数据结构

    • 需要快速查找：ArrayList

    • 需要频繁插入删除：LinkedList

    • 需要线程安全：CopyOnWriteArrayList或Vector

    • 需要去重：HashSet

六、总结

ArrayList作为Java集合框架的核心组件，理解其内部机制对于编写高效Java程序至关重要。通过本文的学习，你应该掌握：

  1. 理论基础：线性表和顺序表的概念

  2. 基本使用：构造、增删改查、遍历

  3. 核心原理：扩容机制和实现细节

  4. 实战应用：洗牌算法等实际场景

  5. 选型思考：根据需求选择合适的数据结构

记住，没有最好的数据结构，只有最适合场景的数据结构。ArrayList在随机访问和遍历场景下表现出色，但在频繁插入删除时可能不是最佳选择。理解每种数据结构的特性，才能在实际编程中做出明智的选择。

最佳实践建议：

  • 如果能预估数据量，创建时指定初始容量避免频繁扩容

  • 使用List<E>接口类型引用，提高代码灵活性

  • 避免在列表中间频繁插入删除大量数据

  • 多线程环境使用合适的线程安全替代方案

希望这篇博客能帮助你深入理解ArrayList，在未来的Java编程中更加得心应手！

http://www.jsqmd.com/news/607201/

相关文章：

  • 别再手动调色了！用Matlab的ColorCopy插件，5分钟搞定Nature级柱状图配色
  • TMSpeech：Windows本地实时语音识别工具完整使用指南
  • 逆向工程实战：从exe4j打包的GUI程序中提取并反编译Java源码
  • 从电网电压到数字信号：深入浅出图解DQ锁相环（PLL）的四种工作模式
  • Android音效库集成全攻略：如何快速接入Dolby Atmos等第三方音效
  • 2026年福建知名的豪宅设计机构排名，泉州众升建筑装饰设计榜上有名 - mypinpai
  • 9.8分高分推荐！恒鑫旺废旧物资回收｜2026 全国机械设备回收厂家 TOP10 权威榜单 - 深度智识库
  • 从理想公式到真实波形：运放方波振荡电路的非理想特性全解析（压摆率、偏置电流、温漂）
  • 别再死记硬背了！用一张图搞懂射频功放P1dB、P3dB和Psat到底啥关系
  • Z-Image-Turbo-辉夜巫女部署案例：GPU算力优化下的低显存高效文生图方案
  • 终极Windows任务栏美化神器：TranslucentTB完全使用指南
  • 如何通过胡桃工具箱提升你的原神游戏体验：Windows平台开源助手终极指南
  • 3步解锁网易云加密音乐：ncmdump工具的完整使用指南
  • 2026年湖南保温好的落地窗品牌推荐，皓思门窗性价比高值得选 - 工业品牌热点
  • 3步掌握WeChatExporter：让微信聊天记录导出变得如此简单
  • SpringBoot项目实战：用jodconverter+LibreOffice实现Word转PDF（附常见报错解决方案）
  • TLA+形式化验证：如何用数学证明分布式系统正确性
  • Qwen3-ForcedAligner-0.6B批量处理指南：高效处理大量语音文件
  • 5个步骤彻底清理Windows驱动垃圾：DriverStore Explorer完全指南
  • 贵阳高端面部抗衰与全身美疗怎么选？2026媞傲美科技美肤官方联系方式及服务解析 - 精选优质企业推荐榜
  • Win11彻底卸载Anaconda3的3个隐藏坑（附2024最新重装指南）
  • 专业网页资源嗅探工具Cat-Catch：如何高效捕获网页媒体资源的完整指南
  • 机器学习中的惩罚函数：L1和L2正则化到底怎么选？
  • 分期乐购物额度回收避坑指南：认准这几点，安全变现不踩雷 - 团团收购物卡回收
  • OWASP ZAP实战进阶：从自动化扫描到企业级CI/CD安全左移
  • FigmaCN：让中文设计师效率提升3倍的界面汉化开源工具
  • 手把手教你用RM500Q-GL模块搭建5G通信系统（含M.2 B Key接口详解）
  • 突破传统限制：Cellpose-SAM引领细胞分割技术革新
  • 2026年长沙性价比高的门窗源头工厂，能根据户型定制的推荐 - 工业推荐榜
  • ​Problem - 2149F - Codeforces​