目录一.什么是List 二.顺序表与ArrayList的关系2.1什么是顺序表2.2 ArrayListJava中的动态顺序表三.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 ArrayListJava中的动态顺序表ArrayList是List接口基于动态数组的实现。它比普通数组更灵活自动扩容当元素个数超过当前容量时会自动分配更大的数组并拷贝数据。丰富的API提供了一系列增删改查方法。泛型支持确保类型安全。同时实现了RandomAccess标记接口表示支持快速随机访问。Cloneable支持克隆Serializable支持序列化注意ArrayList不是线程安全的。多线程环境下使用Vector或CopyOnWriteArrayList。三.ArrayList的核心使用3.1构造方法ArrayList() :空参构造初始容量为10ArrayList(int initialCapacity) 指定初始容量ArrayList(Collection? extends E c) :用已有集合构造//推荐写法使用接口引用实现类——解耦合 ListInteger list1new ArrayList(); // 指定初始容量 ListInteger list2 new ArrayList(20); // 用另一个集合初始化 ArrayListInteger list3 new ArrayList(list2);注意不要使用裸类型new ArrayList()不加泛型否则可以任意添加不同类型允许时候容易出错。3.2常用方法方法描述boolean add(E e)尾部添加元素void add(int index,E element)在指定位置插入boolean addAll(Collection? extends E c)尾部添加集合中的所有元素E remove(int index)删除指定位置元素返回被删元素boolean remove(Object o)删除第一个匹配的元素E get(int index)获取指定位置元素E set(int index,E element)修改指定位置元素int indexOf(Object o)返回第一个匹配元素的索引int lastIndexOf(Object o)返回最后一个匹配元素的索引ListE subList(int fromIndex,int toIndex)截取子列表void clear()清空所有元素boolean contain(Object o)是否包含某元素int size()返回元素个数3.3三种遍历方式//三种遍历方式 List Integerlist2new ArrayList(); list2.add(1);list2.add(2);list2.add(3);list2.add(4); //方式一for循环下标 for(int i0;ilist2.size();i){ System.out.print(list2.get(i) ); } System.out.println(); //方式二for-each for (int x:list2) { System.out.print(x ); } System.out.println(); //方式三迭代器 IteratorInteger itlist2.iterator(); while (it.hasNext()){ System.out.print(it.next() ); }四,深入理解ArrayList扩容机制4.1问题引入下面代码会有性能问题吗ListInteger 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后续当sizecapacity时新容量旧容量旧容量/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 ListCard buyDeck() { ListCard 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(ListCard 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(ListCard 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) { ListCard deck buyDeck(); System.out.println(新牌 deck); shuffle(deck); System.out.println(洗后 deck); // 三人轮流抓5张牌 ListListCard 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)(Ai) 的牌 hands.get(i)); } } }5.2杨辉三角public ListListInteger generate(int numRows) { ListListInteger triangle new ArrayList(); for (int i 0; i numRows; i) { ListInteger 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.元素数量可评估或增长平缓七。常见面试题目Q1ArrayList的扩容因子为什么是1.51.5倍兼顾了空间和时间效率扩容倍数太大浪费内存太小则频繁扩容影响性能。1.5倍在大多数场景下是黄金折中。Q2ArrayList和LinkedList的区别特性ArrayListLinkedList底层结构动态数组双向链表随机访问O(1)O(N)插入/删除中间O(N)O(1)找到位置后内存占用连续内存可能有闲置每个节点额外存储前后指针Q3subList返回的列表和原列表是什么关系subList返回的是原列表的视图共用同一个底层数组。对子列表的修改会反映到原列表反之亦然。Q4为什么ArrayList的elementData被transient修饰ArrayList重写了序列化逻辑只序列化实际存储的元素size个而不序列化整个可能未使用的容量数组以节省空间。总结本文围绕List接口与ArrayList展开梳理了1.线性表——顺序表——ArrayList的概念脉络2.核心API的用法以及注意事项3.扩容源码的解读4.两个小项目的加深理解5.优缺点分析以及常见面试题
Java数据结构——List接口与ArrayList源码剖析
目录一.什么是List 二.顺序表与ArrayList的关系2.1什么是顺序表2.2 ArrayListJava中的动态顺序表三.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 ArrayListJava中的动态顺序表ArrayList是List接口基于动态数组的实现。它比普通数组更灵活自动扩容当元素个数超过当前容量时会自动分配更大的数组并拷贝数据。丰富的API提供了一系列增删改查方法。泛型支持确保类型安全。同时实现了RandomAccess标记接口表示支持快速随机访问。Cloneable支持克隆Serializable支持序列化注意ArrayList不是线程安全的。多线程环境下使用Vector或CopyOnWriteArrayList。三.ArrayList的核心使用3.1构造方法ArrayList() :空参构造初始容量为10ArrayList(int initialCapacity) 指定初始容量ArrayList(Collection? extends E c) :用已有集合构造//推荐写法使用接口引用实现类——解耦合 ListInteger list1new ArrayList(); // 指定初始容量 ListInteger list2 new ArrayList(20); // 用另一个集合初始化 ArrayListInteger list3 new ArrayList(list2);注意不要使用裸类型new ArrayList()不加泛型否则可以任意添加不同类型允许时候容易出错。3.2常用方法方法描述boolean add(E e)尾部添加元素void add(int index,E element)在指定位置插入boolean addAll(Collection? extends E c)尾部添加集合中的所有元素E remove(int index)删除指定位置元素返回被删元素boolean remove(Object o)删除第一个匹配的元素E get(int index)获取指定位置元素E set(int index,E element)修改指定位置元素int indexOf(Object o)返回第一个匹配元素的索引int lastIndexOf(Object o)返回最后一个匹配元素的索引ListE subList(int fromIndex,int toIndex)截取子列表void clear()清空所有元素boolean contain(Object o)是否包含某元素int size()返回元素个数3.3三种遍历方式//三种遍历方式 List Integerlist2new ArrayList(); list2.add(1);list2.add(2);list2.add(3);list2.add(4); //方式一for循环下标 for(int i0;ilist2.size();i){ System.out.print(list2.get(i) ); } System.out.println(); //方式二for-each for (int x:list2) { System.out.print(x ); } System.out.println(); //方式三迭代器 IteratorInteger itlist2.iterator(); while (it.hasNext()){ System.out.print(it.next() ); }四,深入理解ArrayList扩容机制4.1问题引入下面代码会有性能问题吗ListInteger 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后续当sizecapacity时新容量旧容量旧容量/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 ListCard buyDeck() { ListCard 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(ListCard 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(ListCard 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) { ListCard deck buyDeck(); System.out.println(新牌 deck); shuffle(deck); System.out.println(洗后 deck); // 三人轮流抓5张牌 ListListCard 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)(Ai) 的牌 hands.get(i)); } } }5.2杨辉三角public ListListInteger generate(int numRows) { ListListInteger triangle new ArrayList(); for (int i 0; i numRows; i) { ListInteger 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.元素数量可评估或增长平缓七。常见面试题目Q1ArrayList的扩容因子为什么是1.51.5倍兼顾了空间和时间效率扩容倍数太大浪费内存太小则频繁扩容影响性能。1.5倍在大多数场景下是黄金折中。Q2ArrayList和LinkedList的区别特性ArrayListLinkedList底层结构动态数组双向链表随机访问O(1)O(N)插入/删除中间O(N)O(1)找到位置后内存占用连续内存可能有闲置每个节点额外存储前后指针Q3subList返回的列表和原列表是什么关系subList返回的是原列表的视图共用同一个底层数组。对子列表的修改会反映到原列表反之亦然。Q4为什么ArrayList的elementData被transient修饰ArrayList重写了序列化逻辑只序列化实际存储的元素size个而不序列化整个可能未使用的容量数组以节省空间。总结本文围绕List接口与ArrayList展开梳理了1.线性表——顺序表——ArrayList的概念脉络2.核心API的用法以及注意事项3.扩容源码的解读4.两个小项目的加深理解5.优缺点分析以及常见面试题
