从顺序表到ArrayList，吃透动态数组的底层逻辑

Java集合精讲：从顺序表到ArrayList，吃透动态数组的底层逻辑

在Java开发中，集合是日常编码的核心工具，而ArrayList更是高频使用的“明星类”。它本质是动态顺序表，底层基于数组实现，既保留了数组随机访问的高效性，又解决了数组长度固定的痛点。今天咱们从线性表、顺序表的基础概念讲起，一步步拆解ArrayList的使用、扩容机制，最后聊聊它的优缺点与应用场景，新手也能轻松看懂！

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

要理解ArrayList，先搞懂两个核心基础概念——线性表和顺序表。

1. 线性表：数据的“直线队列”

线性表是n个相同类型数据元素的有限序列，逻辑上是一条连续的“直线”，就像排队的人群，每个元素都有唯一的前驱和后继（首尾元素除外）。

常见的线性表分为两类：

• 顺序存储：物理内存连续，比如顺序表、ArrayList；
• 链式存储：物理内存不连续，靠指针/引用关联，比如链表。

2. 顺序表：连续内存的数组封装

顺序表是线性表的一种，用物理地址连续的存储单元存数据，底层就是数组。核心特点：逻辑连续、物理也连续。

顺序表的核心操作（自定义实现思路）

我们可以手动写一个简单的顺序表类SeqList，核心属性就两个：

• array：底层数组，存实际数据；
• size：有效元素个数（区别于数组容量）。

核心方法包括：尾插、指定位置插入、删除、查找、判空、清空等，核心逻辑围绕数组的增删查改展开。

关键痛点：顺序表插入/删除时，需要移动后续元素，时间复杂度O(N)；数组长度固定，满了就无法新增元素——而ArrayList完美解决了这个问题。

二、ArrayList：Java自带的动态顺序表

ArrayList是Java集合框架的核心类，实现了List接口，底层基于动态数组实现，是顺序表的“升级版”。

1. 核心特性（一眼看懂）

• ✅泛型支持：编译期类型检查，避免类型转换异常；
• ✅随机访问：实现RandomAccess接口，通过下标访问效率极高（O(1)）；
• ✅可克隆/序列化：实现Cloneable和Serializable，支持对象复制和网络传输；
• ❌非线程安全：单线程场景优先用，多线程需用Vector或CopyOnWriteArrayList；
• ✅自动扩容：数组满了自动扩容，无需手动管理长度。

2. ArrayList的3种构造方法

日常开发常用3种初始化方式，推荐指定泛型+默认/初始容量的写法：

importjava.util.ArrayList;importjava.util.List;publicclassArrayListDemo{publicstaticvoidmain(String[]args){// 1. 无参构造：默认初始容量为10（JDK17）List<Integer>list1=newArrayList<>();// 2. 指定初始容量：避免频繁扩容（推荐，已知数据量时用）List<Integer>list2=newArrayList<>(20);// 3. 用已有集合构造：复制另一个集合的元素List<Integer>list3=newArrayList<>(list2);}}

避坑提醒：别写List list = new ArrayList()！不指定泛型会变成Object类型，能存任意数据，后续强转极易报错。

3. 常用方法：增删查改全覆盖

ArrayList的方法虽多，但日常高频用的就这些，直接看代码示例：

importjava.util.ArrayList;importjava.util.List;publicclassArrayListMethod{publicstaticvoidmain(String[]args){List<String>list=newArrayList<>();// 1. 新增：尾插、指定位置插list.add("JavaSE");// 尾插list.add(1,"数据结构");// 下标1处插入System.out.println("新增后："+list);// [JavaSE, 数据结构]// 2. 查询：下标获取、元素查找System.out.println("下标0元素："+list.get(0));// JavaSESystem.out.println("是否包含JavaSE："+list.contains("JavaSE"));// trueSystem.out.println("JavaSE下标："+list.indexOf("JavaSE"));// 0// 3. 修改：指定下标赋值list.set(0,"Java进阶");System.out.println("修改后："+list);// [Java进阶, 数据结构]// 4. 删除：按下标删、按元素删list.remove(1);// 按下标删list.remove("Java进阶");// 按元素删System.out.println("删除后："+list);// []// 5. 其他：获取长度、清空System.out.println("元素个数："+list.size());// 0list.clear();// 清空所有元素}}

4. 三种遍历方式：简单高效

遍历ArrayList常用3种方式，for循环+下标和foreach最常用：

importjava.util.ArrayList;importjava.util.Iterator;importjava.util.List;publicclassArrayListTraverse{publicstaticvoidmain(String[]args){List<Integer>list=newArrayList<>();list.add(1);list.add(2);list.add(3);// 方式1：for循环+下标（支持修改元素）for(inti=0;i<list.size();i++){System.out.print(list.get(i)+" ");}System.out.println();// 方式2：foreach（简洁，只读，不能改元素）for(Integernum:list){System.out.print(num+" ");}System.out.println();// 方式3：迭代器（适合遍历中删除元素）Iterator<Integer>it=list.iterator();while(it.hasNext()){System.out.print(it.next()+" ");}}}

三、核心重点：ArrayList的扩容机制

ArrayList最核心的优势是自动扩容，不用手动管数组长度，底层源码（JDK17）扩容逻辑如下：

1. 初始容量

• 无参构造：默认初始容量10；
• 指定初始容量：按传入值初始化；
• 空集合构造：初始容量为0，第一次add时扩容到10。

2. 扩容触发时机

当有效元素个数size == 底层数组长度capacity时，再add元素就会触发扩容。

3. 扩容规则（1.5倍扩容）

1. 计算新容量：新容量 = 旧容量 × 1.5（右移1位等价于除以2，旧容量 + 旧容量/2）；
2. 数据拷贝：用Arrays.copyOf()把旧数组数据复制到新数组；
3. 替换数组：底层数组指向新数组，旧数组被GC回收。

4. 源码核心逻辑（简化版）

// 添加元素publicbooleanadd(Ee){modCount++;add(e,elementData,size);returntrue;}// 实际添加逻辑privatevoidadd(Ee,Object[]elementData,ints){// 数组满了，触发扩容if(s==elementData.length)elementData=grow();elementData[s]=e;size=s+1;}// 扩容方法：1.5倍扩容privateObject[]grow(){returngrow(size+1);}

总结：默认初始10，满了就1.5倍扩容，扩容会拷贝数据，有性能开销。

四、实战案例：用ArrayList实现简单洗牌

学完理论，来个实战——用ArrayList实现扑克牌洗牌+发牌，代码简单易懂：

importjava.util.ArrayList;importjava.util.List;importjava.util.Random;// 扑克牌类classCard{Stringsuit;// 花色：♠♥♣♦intrank;// 牌面值：1-13@OverridepublicStringtoString(){returnsuit+rank;}}// 洗牌发牌工具类publicclassCardGame{// 花色数组privatestaticfinalString[]SUITS={"♠","♥","♣","♦"};// 买一副牌（52张）privatestaticList<Card>buyDeck(){List<Card>deck=newArrayList<>(52);for(Stringsuit:SUITS){for(intrank=1;rank<=13;rank++){Cardcard=newCard();card.suit=suit;card.rank=rank;deck.add(card);}}returndeck;}// 交换两张牌privatestaticvoidswap(List<Card>deck,inti,intj){Cardtemp=deck.get(i);deck.set(i,deck.get(j));deck.set(j,temp);}// 洗牌算法privatestaticvoidshuffle(List<Card>deck){Randomrandom=newRandom();// 从后往前随机交换for(inti=deck.size()-1;i>0;i--){intr=random.nextInt(i);swap(deck,i,r);}}publicstaticvoidmain(String[]args){// 1. 买牌+洗牌List<Card>deck=buyDeck();System.out.println("洗牌前："+deck);shuffle(deck);System.out.println("洗牌后："+deck);// 2. 3个人，每人发5张牌List<List<Card>>players=newArrayList<>();players.add(newArrayList<>());// 玩家Aplayers.add(newArrayList<>());// 玩家Bplayers.add(newArrayList<>());// 玩家Cfor(inti=0;i<5;i++){for(List<Card>player:players){player.add(deck.remove(0));// 从牌堆顶部发牌}}// 3. 打印结果System.out.println("玩家A手牌："+players.get(0));System.out.println("玩家B手牌："+players.get(1));System.out.println("玩家C手牌："+players.get(2));System.out.println("剩余牌："+deck);}}

五、优缺点总结：什么时候用ArrayList？

✅ 优点

1. 随机访问快：下标访问O(1)，查询效率极高；
2. 遍历高效：连续内存，CPU缓存命中率高；
3. 使用简单：API丰富，日常开发首选。

❌ 缺点

1. 插入/删除慢：中间增删需移动元素，O(N)；
2. 扩容有开销：扩容时拷贝数据，消耗时间和内存；
3. 空间浪费：扩容后容量往往大于实际元素个数。

✅ 适用场景

• 频繁查询、遍历，很少中间插入/删除；
• 数据量不大，或能预估初始容量；
• 单线程环境（多线程用CopyOnWriteArrayList）。

六、最后总结

ArrayList是动态顺序表，底层数组+自动扩容，完美平衡了数组的高效查询和动态长度需求。核心要点：

1. 本质：顺序表，物理内存连续；
2. 扩容：默认10，1.5倍扩容；
3. 特性：查询快、增删慢、非线程安全；
4. 场景：查询遍历为主，单线程。

掌握ArrayList，不仅能熟练用集合，更能理解底层数据结构的设计思想——这对Java进阶至关重要！