5.深入理解Java ArrayList：从底层源码到实战应用

目录一、从数据结构说起什么是线性表和顺序表1.1 线性表的概念1.2 顺序表ArrayList的底层灵魂二、ArrayList的家族地位三、ArrayList的使用从创建到操作3.1 三种构造方式3.2 核心操作方法3.3 三种遍历方式四、ArrayList的扩容机制源码级别的深入分析4.1 为什么要扩容4.2 扩容流程JDK 17源码分析4.3 扩容的关键结论4.4 一个常见的思考题五、实战案例洗牌算法5.1 定义牌类5.2 实现洗牌和发牌六、ArrayList的局限性6.1 主要问题6.2 什么时候不适合用ArrayList七、总结写在前面本文基于《ArrayList与顺序表》课程内容整理结合个人学习笔记和代码实践编写。文中所有示例代码均为独立编写旨在帮助读者深入理解ArrayList的工作原理。如需系统学习建议配合Oracle官方文档和JDK源码阅读。一、从数据结构说起什么是线性表和顺序表1.1 线性表的概念在正式开始讲ArrayList之前有必要先搞清楚两个基础概念线性表和顺序表。线性表是n个具有相同特性的数据元素的有限序列。听起来有点抽象其实生活中到处都是线性表排队买奶茶的队伍先进先出手机的通讯录列表可以上下滑动浏览书架上一排整齐的书每本书都有固定位置线性表在逻辑结构上是连续的像一条直线但在物理存储上不一定连续。常见的线性表包括顺序表、链表、栈、队列等。1.2 顺序表ArrayList的底层灵魂顺序表就是用一段物理地址连续的存储单元来依次存储数据元素的线性结构。通俗地说就是用数组来实现的线性表。顺序表的特点是元素在内存中是挨着放的可以通过下标快速访问任意位置的元素插入和删除需要移动大量元素ArrayList就是Java帮我们封装好的一个动态顺序表——它会自动扩容不用我们自己操心数组长度不够的问题。二、ArrayList的家族地位在Java集合框架中ArrayList的继承关系是这样的Iterable (可迭代) ↑ Collection (集合) ↑ List (列表) ↑ AbstractList (抽象类) ↑ ArrayList (最终实现)ArrayList还实现了几个重要的接口接口含义RandomAccess支持随机访问通过下标直接获取元素Cloneable支持克隆可以复制一份Serializable支持序列化可以写入文件或网络传输重要提醒ArrayList是线程不安全的。如果在多线程环境下使用需要考虑使用Vector或CopyOnWriteArrayList。三、ArrayList的使用从创建到操作3.1 三种构造方式// 方式一无参构造初始容量为0JDK 8第一次添加时扩容为10 ListInteger list1 new ArrayList(); // 方式二指定初始容量避免频繁扩容 ListInteger list2 new ArrayList(20); // 方式三用已有集合构造 ListInteger source Arrays.asList(1, 2, 3); ListInteger list3 new ArrayList(source);一个容易被忽视的点无参构造在JDK 8之后初始容量是0而不是10。只有在第一次添加元素时才会扩容到10。这是一种懒加载的思想节省内存。3.2 核心操作方法ListString list new ArrayList(); list.add(JavaSE); list.add(JavaWeb); list.add(JavaEE); list.add(JVM); // 获取元素个数 System.out.println(list.size()); // 4 // 获取指定位置的元素 System.out.println(list.get(1)); // JavaWeb // 修改指定位置的元素 list.set(1, JavaWEB); System.out.println(list.get(1)); // JavaWEB // 在指定位置插入元素后续元素后移 list.add(1, 数据结构); System.out.println(list); // [JavaSE, 数据结构, JavaWEB, JavaEE, JVM] // 删除指定元素删除第一个匹配的 list.remove(JVM); System.out.println(list); // [JavaSE, 数据结构, JavaWEB, JavaEE] // 删除指定位置的元素 list.remove(list.size() - 1); System.out.println(list); // [JavaSE, 数据结构, JavaWEB] // 判断是否包含某元素 System.out.println(list.contains(JavaSE)); // true // 查找元素位置 list.add(JavaSE); System.out.println(list.indexOf(JavaSE)); // 0第一个 System.out.println(list.lastIndexOf(JavaSE)); // 3最后一个 // 截取子列表注意是视图共享底层数组 ListString sub list.subList(0, 2); System.out.println(sub); // [JavaSE, 数据结构]3.3 三种遍历方式ListString list Arrays.asList(Java, Python, Go); // 方式一for循环 下标最常用 for (int i 0; i list.size(); i) { System.out.println(list.get(i)); } // 方式二增强for循环最简洁 for (String s : list) { System.out.println(s); } // 方式三迭代器适合遍历时删除 IteratorString it list.iterator(); while (it.hasNext()) { System.out.println(it.next()); }四、ArrayList的扩容机制源码级别的深入分析4.1 为什么要扩容ArrayList底层是一个Object[]数组。当我们不断往里面添加元素时总有一天数组会填满。这时候就需要一个更大的数组来容纳新元素。4.2 扩容流程JDK 17源码分析// 核心源码简化版 private Object[] elementData; // 存储元素的数组 private int size; // 当前元素个数 public boolean add(E e) { modCount; // 记录修改次数用于快速失败机制 add(e, elementData, size); return true; } private void add(E e, Object[] elementData, int s) { if (s elementData.length) { // 数组满了需要扩容 elementData grow(); } elementData[s] e; size s 1; } private Object[] grow() { return grow(size 1); } private Object[] grow(int minCapacity) { int oldCapacity elementData.length; if (oldCapacity 0 || elementData ! DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 新容量 旧容量 旧容量右移1位即1.5倍 int newCapacity ArraysSupport.newLength( oldCapacity, minCapacity - oldCapacity, // 最小增长量 oldCapacity 1 // 首选增长量旧容量的一半 ); return elementData Arrays.copyOf(elementData, newCapacity); } else { // 第一次添加分配默认容量10 return elementData new Object[Math.max(DEFAULT_CAPACITY, minCapacity)]; } }4.3 扩容的关键结论无参构造第一次添加时数组从0扩容到10后续扩容每次扩容为原来的1.5倍oldCapacity oldCapacity 1扩容代价需要创建新数组并将旧数组的所有元素拷贝过去时间复杂度O(n)空间浪费如果扩容到200只用了105个元素就浪费了95个位置4.4 一个常见的思考题ListInteger list new ArrayList(); for (int i 0; i 100; i) { list.add(i); }这段代码有什么问题答案是扩容次数太多。无参构造初始容量为0第一次扩容到10然后15→22→33→49→73→109一共经历了7次扩容。每次扩容都要拷贝全部已有元素性能损耗不小。优化方案如果能预知数据量最好指定初始容量ListInteger list new ArrayList(100); // 一次到位无需扩容五、实战案例洗牌算法把理论知识用在实践中我们来写一个完整的洗牌发牌程序。5.1 定义牌类public class Card { private int rank; // 牌面值1~13 private String suit; // 花色♠♥♣♦ public Card(int rank, String suit) { this.rank rank; this.suit suit; } Override public String toString() { return String.format([%s %d], suit, rank); } }5.2 实现洗牌和发牌import java.util.ArrayList; import java.util.List; import java.util.Random; public class PokerGame { private static final String[] SUITS {♠, ♥, ♣, ♦}; // 买一副新牌 private static ListCard buyDeck() { ListCard deck new ArrayList(52); for (int i 0; i 4; i) { for (int j 1; j 13; j) { deck.add(new Card(j, SUITS[i])); } } return deck; } // 交换两张牌 private static void swap(ListCard deck, int i, int j) { Card temp deck.get(i); deck.set(i, deck.get(j)); deck.set(j, temp); } // Fisher-Yates洗牌算法 private static void shuffle(ListCard deck) { Random random new Random(); for (int i deck.size() - 1; i 0; i--) { int r random.nextInt(i 1); // 生成[0, i]之间的随机数 swap(deck, i, r); } } public static void main(String[] args) { // 1. 买牌 ListCard deck buyDeck(); System.out.println(新买的牌 deck); // 2. 洗牌 shuffle(deck); System.out.println(洗过的牌 deck); // 3. 三个人轮流抓5张牌 ListListCard hands new ArrayList(); hands.add(new ArrayList()); hands.add(new ArrayList()); hands.add(new ArrayList()); for (int round 0; round 5; round) { for (int player 0; player 3; player) { // 从牌堆顶部取一张牌 hands.get(player).add(deck.remove(0)); } } // 4. 显示结果 System.out.println(\n 发牌结果 ); System.out.println(玩家A的手牌 hands.get(0)); System.out.println(玩家B的手牌 hands.get(1)); System.out.println(玩家C的手牌 hands.get(2)); System.out.println(\n剩余牌数 deck.size()); } }运行效果新买的牌[♠ 1, ♠ 2, ♠ 3, ..., ♦ 13] 洗过的牌[♣ 7, ♥ 3, ♦ 11, ..., ♠ 5] 发牌结果 玩家A的手牌[♣ 7, ♦ 5, ♥ 12, ♠ 4, ♣ 2] 玩家B的手牌[♥ 3, ♠ 8, ♣ 13, ♦ 9, ♠ 10] 玩家C的手牌[♦ 11, ♥ 7, ♠ 6, ♥ 9, ♦ 3] 剩余牌数37六、ArrayList的局限性尽管ArrayList非常强大但它并非万能。了解它的局限才能做出正确的技术选型。6.1 主要问题插入和删除效率低在中间位置插入或删除元素时需要移动大量元素时间复杂度O(n)扩容代价高扩容时需要拷贝整个数组空间浪费扩容通常是1.5倍可能造成内存浪费6.2 什么时候不适合用ArrayList频繁在列表头部或中间插入/删除元素 → 考虑LinkedList多线程环境 → 考虑CopyOnWriteArrayList或Vector需要频繁扩容且数据量巨大 → 预先指定合理容量七、总结知识点核心要点底层结构动态数组Object[]扩容机制无参首次扩容到10后续1.5倍随机访问O(1)支持RandomAccess接口插入删除O(n)需要移动元素线程安全不安全需外部同步适用场景读多写少尾部追加一句话总结ArrayList是Java中最常用的集合之一底层基于动态数组实现擅长随机访问和尾部操作但在频繁插入删除的场景下表现不佳。如果你觉得这篇文章对你有帮助欢迎点赞收藏。下一篇我们将深入LinkedList的源码看看链表结构是如何弥补ArrayList的不足的敬请期待注本文为个人学习总结所有代码示例均为独立编写。建议读者在学习过程中结合JDK官方文档和源码进行验证。