Java数据结构——List接口与ArrayList源码剖析

目录

一.什么是List ？

二.顺序表与ArrayList的关系

2.1什么是顺序表？

2.2 ArrayList：Java中的动态顺序表

三.ArrayList的核心使用

3.1构造方法

3.2常用方法

3.3三种遍历方式

四,深入理解ArrayList扩容机制

4.1问题引入

4.2源码分析（JDK 17）

五.案例

5.1简单的洗牌算法

5.2杨辉三角

六.ArrayList的优缺点与适用场景

七。常见面试题目

总结：

一.什么是List ？

在集合框架中，List是一个接口，继承自Collection。它代表一个有序，可重复的元素序列，允许我们通过索引（下标）来精确访问，插入或删除元素。

List在数据结构视角下就是线性表——n个具有相同类型元素的有限序列。

List接口的常用实现类有：

ArrayList：底层动态数组，随机访问快

LinkedList：底层双向链表，插入/删除快

Collection 接口中定义了容器的通用方法，比如size(),add(), remove() ,contain()等。而List在继承这些方法的基础上，又增加了与索引相关的操作（如get(int index)），set(int index ,E element)。

二.顺序表与ArrayList的关系

2.1什么是顺序表？

顺序表是用一段物理地址连续的存储单元一次存储数据元素的线性结构。在Java中，最典型的顺序表就是数组。

顺序表支持随机访问——通过下标计算内存地址，时间复杂度O(1)。但插入和删除元素时，需要移动大量数据，时间复杂度O(n)。

2.2 ArrayList：Java中的动态顺序表

ArrayList是List接口基于动态数组的实现。它比普通数组更灵活：

自动扩容：当元素个数超过当前容量时，会自动分配更大的数组并拷贝数据。

丰富的API：提供了一系列增删改查方法。

泛型支持：确保类型安全。

同时实现了：

RandomAccess：标记接口，表示支持快速随机访问。

Cloneable：支持克隆

Serializable：支持序列化

注意：ArrayList不是线程安全的。多线程环境下使用Vector或CopyOnWriteArrayList。

三.ArrayList的核心使用

3.1构造方法

ArrayList() :空参构造，初始容量为10

ArrayList(int initialCapacity) ：指定初始容量

ArrayList(Collection<? extends E> c) :用已有集合构造

//推荐写法：使用接口引用实现类——解耦合 List<Integer> list1=new ArrayList<>(); // 指定初始容量 List<Integer> list2 = new ArrayList<>(20); // 用另一个集合初始化 ArrayList<Integer> list3 = new ArrayList<>(list2);

注意：不要使用裸类型（new ArrayList()不加泛型），否则可以任意添加不同类型，允许时候容易出错。

3.2常用方法

3.3三种遍历方式

//三种遍历方式 List <Integer>list2=new ArrayList<>(); list2.add(1);list2.add(2);list2.add(3);list2.add(4); //方式一：for循环+下标 for(int i=0;i<list2.size();i++){ System.out.print(list2.get(i)+" "); } System.out.println(); //方式二：for-each for (int x:list2) { System.out.print(x+" "); } System.out.println(); //方式三：迭代器 Iterator<Integer> it=list2.iterator(); while (it.hasNext()){ System.out.print(it.next()+" "); }

四,深入理解ArrayList扩容机制

4.1问题引入

下面代码会有性能问题吗？

List<Integer> list = new ArrayList<>(); // 初始容量为0？不对，是10（延迟初始化） for (int i = 0; i < 100; i++) { list.add(i); }

答案：ArrayList采用懒加载策略，无参构造时底层数组组织向一个空数组（DEFAULTCAPACITY_EMPTY_ELEMENTDATA）。第一次add时才会分配容量为10的数组。当元素个数超过当前容量时，会进行1.5倍扩容。

4.2源码分析（JDK 17）

// 无参构造 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } // add方法核心 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)]; } }

扩容总结：第一次add：分配容量10

后续当size==capacity时，新容量=旧容量+旧容量/2（即1.5倍）。

扩容本质是Arrays.copyOf()，会创建新数组并拷贝原数据，代价比较高。建议在大概知道元素数量时，使用带初始容量的构造方法。

五.案例

5.1简单的洗牌算法

import java.util.ArrayList; import java.util.List; import java.util.Random; class Card { public int rank; // 点数 1~13 public String suit; // 花色 "♠","♥","♣","♦" @Override public String toString() { return String.format("[%s %d]", suit, rank); } } public class Demo2 { private static final String[] SUITS = {"♠", "♥", "♣", "♦"}; // 买一副新牌（52张） private static List<Card> buyDeck() { List<Card> deck = new ArrayList<>(52); for (String suit : SUITS) { for (int rank = 1; rank <= 13; rank++) { Card card = new Card(); card.rank = rank; card.suit = suit; deck.add(card); } } return deck; } // 洗牌（Fisher-Yates 算法） private static void shuffle(List<Card> deck) { Random random = new Random(); for (int i = deck.size() - 1; i > 0; i--) { int r = random.nextInt(i + 1); swap(deck, i, r); } } 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); } 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("剩余牌数：" + deck.size()); for (int i = 0; i < hands.size(); i++) { System.out.println("玩家" + (char)('A'+i) + "的牌：" + hands.get(i)); } } }

5.2杨辉三角

public List<List<Integer>> generate(int numRows) { List<List<Integer>> triangle = new ArrayList<>(); for (int i = 0; i < numRows; i++) { List<Integer> row = new ArrayList<>(); for (int j = 0; j <= i; j++) { if (j == 0 || j == i) { row.add(1); } else { int val = triangle.get(i-1).get(j-1) + triangle.get(i-1).get(j); row.add(val); } } triangle.add(row); } return triangle; }

六.ArrayList的优缺点与适用场景

优点：1.随机访问极快：O(1)时间复杂度

2.尾部增删高效：均摊O(1)（扩容时短暂O(N)）

3.内存连续：cpu缓存友好

4。实现简单，API丰富

缺点：1.中间插入/删除慢：需要移动元素，O(N)

2.扩容有代价：涉及数组拷贝和内粗浪费（1.5倍扩容）

3.不适合频繁修改的场景

适用场景：1.频繁按索引访问元素

2.主要进行尾部操作（如读文件后逐行添加）

3.元素数量可评估或增长平缓

七。常见面试题目

Q1：ArrayList的扩容因子为什么是1.5？

1.5倍兼顾了空间和时间效率，扩容倍数太大浪费内存，太小则频繁扩容影响性能。1.5倍在大多数场景下是黄金折中。

Q2：ArrayList和LinkedList的区别？

Q3：subList返回的列表和原列表是什么关系？

subList返回的是原列表的视图，共用同一个底层数组。对子列表的修改会反映到原列表，反之亦然。

Q4：为什么ArrayList的elementData被transient修饰？

ArrayList重写了序列化逻辑，只序列化实际存储的元素（size个），而不序列化整个可能未使用的容量数组，以节省空间。

总结：

本文围绕List接口与ArrayList展开，梳理了：

1.线性表——>顺序表——>ArrayList的概念脉络

2.核心API的用法以及注意事项

3.扩容源码的解读

4.两个小项目的加深理解

5.优缺点分析以及常见面试题