一、快速排序算法核心分治思想与高效实现快速排序Quick Sort是经典的分治排序算法凭借O(n log n)的平均时间复杂度、空间效率高、原地排序等优势在工程实践中被广泛应用。它的核心是通过“基准数定位双指针交换递归分治”的逻辑将大数组拆解为小数组逐层完成排序。核心分治思想与游标移动逻辑快速排序的核心是分治策略将待排序数组拆分为“基准数左侧子数组右侧子数组”左侧子数组均小于基准数右侧均大于基准数再对左右子数组递归执行同样的操作直至子数组不可再拆分长度为1。这一过程依赖基准数定位和双指针交换机制。双指针交换是快速排序的核心操作目的是让左右指针相向移动找到“左侧大于基准数、右侧小于基准数”的元素对并交换最终将基准数归位到正确的位置完成一次分区。指针移动逻辑 I指针左指针从左向右移动寻找第一个大于基准数的元素若找到则停止若未找到I超过J直接进入最终交换。 J指针右指针从右向左移动寻找第一个小于基准数的元素若找到则停止若未找到J超过I直接进入最终交换。交换时机当I和J均找到符合条件的元素后交换二者对应的数组元素之后继续移动指针。 最终归位当I和J相遇时无论相遇位置的元素是大于还是小于基准数都将基准数与相遇位置的元素交换此时基准数就位于了分区后的正确位置。递归终止条件分区完成后数组被拆分为左侧子数组left到pivotIndex-1和右侧子数组pivotIndex1到right此时需要对这两个子数组递归执行相同的分区、交换操作直至子数组的长度为1此时数组自然有序无需排序。递归终止条件当待排序区间的左边界left大于等于右边界right时说明该区间长度小于等于1直接终止递归。 递归核心递归的本质是“分而治之”通过不断拆分大区间为小区间直到小区间无需排序最终将所有小区间有序合并得到完整有序的数组。完整快速排序代码import java.util.Arrays; public class QuickSortComplete { // 快速排序入口方法 public void quickSort(int[] array, int left, int right) { // 递归出口区间长度1直接返回 if (left right) { return; } // 1. 分区获取基准数归位后的下标 int pivotIndex partition(array, left, right); // 2. 递归排序左侧子数组 [left, pivotIndex-1] quickSort(array, left, pivotIndex - 1); // 3. 递归排序右侧子数组 [pivotIndex1, right] quickSort(array, pivotIndex 1, right); } // 分区方法同上述单次分区逻辑 private int partition(int[] array, int left, int right) { int pivot array[left]; int i left; int j right; while (i j) { while (i j array[j] pivot) { j--; } while (i j array[i] pivot) { i; } if (i j) { int temp array[i]; array[i] array[j]; array[j] temp; } } array[left] array[i]; array[i] pivot; return i; } public static void main(String[] args) { QuickSortComplete sorter new QuickSortComplete(); int[] arr {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}; System.out.println(排序前数组 Arrays.toString(arr)); sorter.quickSort(arr, 0, arr.length - 1); System.out.println(排序后数组 Arrays.toString(arr)); // 输出排序后数组按升序排列 } }内存执行流程与变量作用域快速排序的递归过程依赖JVM的栈结构理解栈帧变化和变量作用域能帮助我们更清晰地掌握算法的执行逻辑避免陷入递归的“思维迷宫”。栈帧变化模拟递归的本质是方法的嵌套调用每次递归调用都会在JVM的栈空间中创建一个新的栈帧用于存储当前方法的参数、局部变量和返回地址递归结束后栈帧出栈释放内存。以数组[3,1,4,2]为例快速排序的栈帧变化流程如下首次调用调用quickSort(array, 0, 3)创建第一个栈帧存储参数left0、right3执行分区后基准数3归位到下标2递归调用quickSort(array,0,1)和quickSort(array,3,3)。左子递归入栈调用quickSort(array,0,1)创建第二个栈帧分区后基准数1归位到下标0递归调用quickSort(array,0,-1)和quickSort(array,1,1)。左子递归的子调用入栈quickSort(array,0,-1)触发递归出口直接出栈quickSort(array,1,1)也触发出口出栈第二个栈帧执行完毕出栈。右子递归入栈回到首次调用执行quickSort(array,3,3)触发出口出栈。首次调用出栈首次调用执行完毕栈帧出栈完成整个排序过程。核心要点栈帧遵循“先进后出”的原则递归调用时栈帧入栈递归出口触发时栈帧出栈递归深度不能超过JVM栈的容量否则会抛出栈溢出异常StackOverflowError。变量作用域快速排序的方法中变量的作用域决定了变量的生命周期需要重点关注局部变量和数组引用的差异 局部变量如temp局部变量存储在当前方法的栈帧中当方法执行结束、栈帧出栈时局部变量会自动销毁内存被回收。例如分区方法中的temp仅在单次分区过程中存在分区结束后就被销毁不会影响其他方法的执行。 数组引用的共享性数组是引用类型array这个引用变量指向堆中的数组对象。在递归过程中虽然每个栈帧都有自己独立的array引用但指向同一个堆中的数组因此对数组的修改是全局生效的。例如在分区方法中修改数组元素所有递归方法中看到的数组都是修改后的状态这也是快速排序能实现原地排序的核心原因。二、ArrayList底层数据结构与扩容机制数组的核心痛点是长度固定无法动态扩容当数据量超过数组容量时需要手动创建新数组并复制数据开发效率低且易出错。ArrayList作为Java中最常用的可变数组通过封装动态扩容的数组解决了这一痛点同时提供了高效的增删改查操作是日常开发中的“高频工具类”。底层封装与扩容策略ArrayList的核心是封装一个动态扩容的数组通过合理的扩容策略平衡内存占用和性能开销其底层实现围绕初始容量、扩容触发条件和扩容规则展开。默认容量与扩容触发条件ArrayList采用“懒加载”策略初始时底层数组为空当首次添加元素时才会初始化底层数组。 默认初始容量若创建ArrayList时未指定初始容量底层数组的默认初始容量为10JDK 1.8。 扩容触发条件当ArrayList中元素的个数size属性记录有效数据的数量等于底层数组的容量时再次添加元素会触发扩容操作。例如底层数组容量为10当size为10时添加第11个元素就会触发扩容。扩容倍数规则扩容的核心是创建新数组并复制数据ArrayList的扩容规则兼顾了性能和内存利用率具体规则为 新容量约为原容量的1.5倍。 计算公式新容量 原容量 原容量右移1位等价于原容量1.5。例如原容量为10右移1位是5新容量为10515原容量为15右移1位是7新容量为15722。扩容流程计算新容量创建新数组容量为新容量将原数组的所有元素复制到新数组将ArrayList的底层数组引用指向新数组后续添加元素直接在新数组中进行。代码ArrayList扩容逻辑import java.util.Arrays; public class ArrayListSimulation { // 模拟ArrayList的核心属性底层数组、有效元素个数 private Object[] elementData; private int size; // 构造方法默认容量10 public ArrayListSimulation() { this.elementData new Object[10]; this.size 0; } // 构造方法指定初始容量 public ArrayListSimulation(int initialCapacity) { if (initialCapacity 0) { throw new IllegalArgumentException(初始容量不能为负数); } this.elementData new Object[initialCapacity]; this.size 0; } // 添加元素触发扩容的核心逻辑 public void add(Object e) { // 扩容检查如果有效元素个数等于数组容量需要扩容 if (size elementData.length) { // 计算新容量原容量 * 1.5通过位运算实现效率高 int newCapacity elementData.length (elementData.length 1); // 创建新数组 Object[] newArray new Object[newCapacity]; // 复制原数组元素到新数组 System.arraycopy(elementData, 0, newArray, 0, size); // 指向新数组 elementData newArray; System.out.println(触发扩容原容量 (newCapacity - (newCapacity - elementData.length)) , 新容量 newCapacity); } // 在size位置添加元素然后size elementData[size] e; size; } // 获取有效元素个数 public int size() { return size; } // 获取底层数组用于测试 public Object[] getElementData() { return elementData; } public static void main(String[] args) { ArrayListSimulation list new ArrayListSimulation(); // 添加11个元素观察扩容过程 for (int i 0; i 11; i) { list.add(i); } System.out.println(有效元素个数 list.size()); System.out.println(最终数组容量 list.getElementData().length); // 输出添加第11个元素时触发扩容原容量10新容量15最终数组容量15有效元素个数11 } }增删改查的底层逻辑ArrayList基于动态数组实现了高效的增删改查操作核心是通过size属性控制有效数据的范围避免操作底层数组的无效空间同时针对不同操作优化了实现逻辑。插入操作Add插入操作的核心是“先检查扩容再在指定位置插入最后更新size”分为在末尾插入和在指定位置插入两种情况其中在指定位置插入需要移动后续元素。末尾插入直接将元素放在elementData[size]位置然后size时间复杂度O(1)。指定位置插入检查插入位置的合法性位置必须在0到size之间检查是否需要扩容将插入位置及之后的元素整体向后移动一位从后往前移动避免元素覆盖在插入位置放入新元素size时间复杂度O(n)移动元素开销。代码指定位置插入逻辑public class ArrayListAddSimulation { private Object[] elementData new Object[10]; private int size 0; // 指定位置插入元素 public void add(int index, Object e) { // 1. 检查索引合法性0 index size if (index 0 || index size) { throw new IndexOutOfBoundsException(索引越界允许范围[0, size ]); } // 2. 检查扩容 if (size elementData.length) { int newCapacity elementData.length (elementData.length 1); Object[] newArray new Object[newCapacity]; System.arraycopy(elementData, 0, newArray, 0, size); elementData newArray; } // 3. 移动元素从size位置到index位置依次后移一位从后往前遍历避免覆盖 for (int i size; i index; i--) { elementData[i] elementData[i - 1]; } // 4. 插入元素 elementData[index] e; // 5. 更新size size; } // 获取元素辅助方法 public Object get(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(索引越界); } return elementData[index]; } // 转换为字符串仅打印有效元素 Override public String toString() { if (size 0) return []; StringBuilder sb new StringBuilder([); for (int i 0; i size; i) { sb.append(elementData[i]); if (i ! size - 1) sb.append(,); } sb.append(]); return sb.toString(); } public static void main(String[] args) { ArrayListAddSimulation list new ArrayListAddSimulation(); list.add(0, A); list.add(1, B); list.add(1, C); // 在索引1插入C原B后移 System.out.println(list); // 输出[A,C,B]说明插入后元素正确后移 } }删除操作Remove删除操作分为删除指定位置元素和删除指定元素核心是“移动后续元素覆盖待删除元素再更新size”同时需要注意遍历方向对删除结果的影响。删除指定位置元素检查索引合法性将待删除位置之后的所有元素整体向前移动一位从前往后移动将最后一个元素置为null帮助JVM回收避免内存泄漏size--时间复杂度O(n)移动元素开销。删除指定元素 问题若从前往后遍历删除元素后索引会发生变化可能导致漏删。例如数组[1,2,2,3]从前往后删除2第一次删除索引1的2后后续元素前移原索引2的2变为索引1下一次遍历到索引2会跳过这个2导致漏删。解决方案从后往前遍历删除元素后后续元素的位置不影响前面的遍历可避免漏删。因为从后往前删除时删除元素的位置之前的元素索引不会发生变化能保证所有符合条件的元素都被删除。代码示例public class ArrayListRemoveSimulation { private Object[] elementData new Object[10]; private int size 0; // 添加元素辅助方法 public void add(Object e) { if (size elementData.length) { int newCapacity elementData.length (elementData.length 1); elementData new Object[newCapacity]; } elementData[size] e; } // 删除所有指定元素从后往前遍历避免漏删 public void remove(Object e) { // 从后往前遍历找到等于e的元素并删除 for (int i size - 1; i 0; i--) { if (elementData[i] e || (elementData[i] ! null elementData[i].equals(e))) { // 移动元素将i之后的元素向前移动一位 for (int j i; j size - 1; j) { elementData[j] elementData[j 1]; } // 最后一个元素置null避免内存泄漏 elementData[size - 1] null; size--; } } } Override public String toString() { if (size 0) return []; StringBuilder sb new StringBuilder([); for (int i 0; i size; i) { sb.append(elementData[i]); if (i ! size - 1) sb.append(,); } sb.append(]); return sb.toString(); } public static void main(String[] args) { ArrayListRemoveSimulation list new ArrayListRemoveSimulation(); list.add(1); list.add(2); list.add(2); list.add(3); System.out.println(删除前 list); // 输出[1,2,2,3] list.remove(2); System.out.println(删除后 list); // 输出[1,3]所有2都被删除无漏删 } }打印重写ToStringArrayList重写了toString()方法核心是仅遍历0到size-1的有效元素而不是遍历整个底层数组避免打印底层数组中预留的默认值如null或0确保输出结果只包含用户添加的有效元素。原因底层数组的容量可能大于size例如扩容后容量为15但size为11剩余位置是未使用的默认值为null对象数组如果遍历整个数组会输出大量无意义的null影响可读性。实现逻辑重写toString()时通过循环遍历索引0到size-1的元素拼接字符串仅展示有效数据。示例import java.util.ArrayList; public class ArrayListToStringDemo { public static void main(String[] args) { ArrayListInteger list new ArrayList(); list.add(1); list.add(2); list.add(3); // ArrayList重写toString仅打印有效元素 System.out.println(list); // 输出[1, 2, 3] // 若直接打印底层数组假设获取到会包含null Object[] arr new Object[10]; arr[0] 1; arr[1] 2; arr[2] 3; System.out.println(Arrays.toString(arr)); // 输出[1, 2, 3, null, null, null, null, null, null, null]包含大量null } }
数据结构（五）
一、快速排序算法核心分治思想与高效实现快速排序Quick Sort是经典的分治排序算法凭借O(n log n)的平均时间复杂度、空间效率高、原地排序等优势在工程实践中被广泛应用。它的核心是通过“基准数定位双指针交换递归分治”的逻辑将大数组拆解为小数组逐层完成排序。核心分治思想与游标移动逻辑快速排序的核心是分治策略将待排序数组拆分为“基准数左侧子数组右侧子数组”左侧子数组均小于基准数右侧均大于基准数再对左右子数组递归执行同样的操作直至子数组不可再拆分长度为1。这一过程依赖基准数定位和双指针交换机制。双指针交换是快速排序的核心操作目的是让左右指针相向移动找到“左侧大于基准数、右侧小于基准数”的元素对并交换最终将基准数归位到正确的位置完成一次分区。指针移动逻辑 I指针左指针从左向右移动寻找第一个大于基准数的元素若找到则停止若未找到I超过J直接进入最终交换。 J指针右指针从右向左移动寻找第一个小于基准数的元素若找到则停止若未找到J超过I直接进入最终交换。交换时机当I和J均找到符合条件的元素后交换二者对应的数组元素之后继续移动指针。 最终归位当I和J相遇时无论相遇位置的元素是大于还是小于基准数都将基准数与相遇位置的元素交换此时基准数就位于了分区后的正确位置。递归终止条件分区完成后数组被拆分为左侧子数组left到pivotIndex-1和右侧子数组pivotIndex1到right此时需要对这两个子数组递归执行相同的分区、交换操作直至子数组的长度为1此时数组自然有序无需排序。递归终止条件当待排序区间的左边界left大于等于右边界right时说明该区间长度小于等于1直接终止递归。 递归核心递归的本质是“分而治之”通过不断拆分大区间为小区间直到小区间无需排序最终将所有小区间有序合并得到完整有序的数组。完整快速排序代码import java.util.Arrays; public class QuickSortComplete { // 快速排序入口方法 public void quickSort(int[] array, int left, int right) { // 递归出口区间长度1直接返回 if (left right) { return; } // 1. 分区获取基准数归位后的下标 int pivotIndex partition(array, left, right); // 2. 递归排序左侧子数组 [left, pivotIndex-1] quickSort(array, left, pivotIndex - 1); // 3. 递归排序右侧子数组 [pivotIndex1, right] quickSort(array, pivotIndex 1, right); } // 分区方法同上述单次分区逻辑 private int partition(int[] array, int left, int right) { int pivot array[left]; int i left; int j right; while (i j) { while (i j array[j] pivot) { j--; } while (i j array[i] pivot) { i; } if (i j) { int temp array[i]; array[i] array[j]; array[j] temp; } } array[left] array[i]; array[i] pivot; return i; } public static void main(String[] args) { QuickSortComplete sorter new QuickSortComplete(); int[] arr {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}; System.out.println(排序前数组 Arrays.toString(arr)); sorter.quickSort(arr, 0, arr.length - 1); System.out.println(排序后数组 Arrays.toString(arr)); // 输出排序后数组按升序排列 } }内存执行流程与变量作用域快速排序的递归过程依赖JVM的栈结构理解栈帧变化和变量作用域能帮助我们更清晰地掌握算法的执行逻辑避免陷入递归的“思维迷宫”。栈帧变化模拟递归的本质是方法的嵌套调用每次递归调用都会在JVM的栈空间中创建一个新的栈帧用于存储当前方法的参数、局部变量和返回地址递归结束后栈帧出栈释放内存。以数组[3,1,4,2]为例快速排序的栈帧变化流程如下首次调用调用quickSort(array, 0, 3)创建第一个栈帧存储参数left0、right3执行分区后基准数3归位到下标2递归调用quickSort(array,0,1)和quickSort(array,3,3)。左子递归入栈调用quickSort(array,0,1)创建第二个栈帧分区后基准数1归位到下标0递归调用quickSort(array,0,-1)和quickSort(array,1,1)。左子递归的子调用入栈quickSort(array,0,-1)触发递归出口直接出栈quickSort(array,1,1)也触发出口出栈第二个栈帧执行完毕出栈。右子递归入栈回到首次调用执行quickSort(array,3,3)触发出口出栈。首次调用出栈首次调用执行完毕栈帧出栈完成整个排序过程。核心要点栈帧遵循“先进后出”的原则递归调用时栈帧入栈递归出口触发时栈帧出栈递归深度不能超过JVM栈的容量否则会抛出栈溢出异常StackOverflowError。变量作用域快速排序的方法中变量的作用域决定了变量的生命周期需要重点关注局部变量和数组引用的差异 局部变量如temp局部变量存储在当前方法的栈帧中当方法执行结束、栈帧出栈时局部变量会自动销毁内存被回收。例如分区方法中的temp仅在单次分区过程中存在分区结束后就被销毁不会影响其他方法的执行。 数组引用的共享性数组是引用类型array这个引用变量指向堆中的数组对象。在递归过程中虽然每个栈帧都有自己独立的array引用但指向同一个堆中的数组因此对数组的修改是全局生效的。例如在分区方法中修改数组元素所有递归方法中看到的数组都是修改后的状态这也是快速排序能实现原地排序的核心原因。二、ArrayList底层数据结构与扩容机制数组的核心痛点是长度固定无法动态扩容当数据量超过数组容量时需要手动创建新数组并复制数据开发效率低且易出错。ArrayList作为Java中最常用的可变数组通过封装动态扩容的数组解决了这一痛点同时提供了高效的增删改查操作是日常开发中的“高频工具类”。底层封装与扩容策略ArrayList的核心是封装一个动态扩容的数组通过合理的扩容策略平衡内存占用和性能开销其底层实现围绕初始容量、扩容触发条件和扩容规则展开。默认容量与扩容触发条件ArrayList采用“懒加载”策略初始时底层数组为空当首次添加元素时才会初始化底层数组。 默认初始容量若创建ArrayList时未指定初始容量底层数组的默认初始容量为10JDK 1.8。 扩容触发条件当ArrayList中元素的个数size属性记录有效数据的数量等于底层数组的容量时再次添加元素会触发扩容操作。例如底层数组容量为10当size为10时添加第11个元素就会触发扩容。扩容倍数规则扩容的核心是创建新数组并复制数据ArrayList的扩容规则兼顾了性能和内存利用率具体规则为 新容量约为原容量的1.5倍。 计算公式新容量 原容量 原容量右移1位等价于原容量1.5。例如原容量为10右移1位是5新容量为10515原容量为15右移1位是7新容量为15722。扩容流程计算新容量创建新数组容量为新容量将原数组的所有元素复制到新数组将ArrayList的底层数组引用指向新数组后续添加元素直接在新数组中进行。代码ArrayList扩容逻辑import java.util.Arrays; public class ArrayListSimulation { // 模拟ArrayList的核心属性底层数组、有效元素个数 private Object[] elementData; private int size; // 构造方法默认容量10 public ArrayListSimulation() { this.elementData new Object[10]; this.size 0; } // 构造方法指定初始容量 public ArrayListSimulation(int initialCapacity) { if (initialCapacity 0) { throw new IllegalArgumentException(初始容量不能为负数); } this.elementData new Object[initialCapacity]; this.size 0; } // 添加元素触发扩容的核心逻辑 public void add(Object e) { // 扩容检查如果有效元素个数等于数组容量需要扩容 if (size elementData.length) { // 计算新容量原容量 * 1.5通过位运算实现效率高 int newCapacity elementData.length (elementData.length 1); // 创建新数组 Object[] newArray new Object[newCapacity]; // 复制原数组元素到新数组 System.arraycopy(elementData, 0, newArray, 0, size); // 指向新数组 elementData newArray; System.out.println(触发扩容原容量 (newCapacity - (newCapacity - elementData.length)) , 新容量 newCapacity); } // 在size位置添加元素然后size elementData[size] e; size; } // 获取有效元素个数 public int size() { return size; } // 获取底层数组用于测试 public Object[] getElementData() { return elementData; } public static void main(String[] args) { ArrayListSimulation list new ArrayListSimulation(); // 添加11个元素观察扩容过程 for (int i 0; i 11; i) { list.add(i); } System.out.println(有效元素个数 list.size()); System.out.println(最终数组容量 list.getElementData().length); // 输出添加第11个元素时触发扩容原容量10新容量15最终数组容量15有效元素个数11 } }增删改查的底层逻辑ArrayList基于动态数组实现了高效的增删改查操作核心是通过size属性控制有效数据的范围避免操作底层数组的无效空间同时针对不同操作优化了实现逻辑。插入操作Add插入操作的核心是“先检查扩容再在指定位置插入最后更新size”分为在末尾插入和在指定位置插入两种情况其中在指定位置插入需要移动后续元素。末尾插入直接将元素放在elementData[size]位置然后size时间复杂度O(1)。指定位置插入检查插入位置的合法性位置必须在0到size之间检查是否需要扩容将插入位置及之后的元素整体向后移动一位从后往前移动避免元素覆盖在插入位置放入新元素size时间复杂度O(n)移动元素开销。代码指定位置插入逻辑public class ArrayListAddSimulation { private Object[] elementData new Object[10]; private int size 0; // 指定位置插入元素 public void add(int index, Object e) { // 1. 检查索引合法性0 index size if (index 0 || index size) { throw new IndexOutOfBoundsException(索引越界允许范围[0, size ]); } // 2. 检查扩容 if (size elementData.length) { int newCapacity elementData.length (elementData.length 1); Object[] newArray new Object[newCapacity]; System.arraycopy(elementData, 0, newArray, 0, size); elementData newArray; } // 3. 移动元素从size位置到index位置依次后移一位从后往前遍历避免覆盖 for (int i size; i index; i--) { elementData[i] elementData[i - 1]; } // 4. 插入元素 elementData[index] e; // 5. 更新size size; } // 获取元素辅助方法 public Object get(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(索引越界); } return elementData[index]; } // 转换为字符串仅打印有效元素 Override public String toString() { if (size 0) return []; StringBuilder sb new StringBuilder([); for (int i 0; i size; i) { sb.append(elementData[i]); if (i ! size - 1) sb.append(,); } sb.append(]); return sb.toString(); } public static void main(String[] args) { ArrayListAddSimulation list new ArrayListAddSimulation(); list.add(0, A); list.add(1, B); list.add(1, C); // 在索引1插入C原B后移 System.out.println(list); // 输出[A,C,B]说明插入后元素正确后移 } }删除操作Remove删除操作分为删除指定位置元素和删除指定元素核心是“移动后续元素覆盖待删除元素再更新size”同时需要注意遍历方向对删除结果的影响。删除指定位置元素检查索引合法性将待删除位置之后的所有元素整体向前移动一位从前往后移动将最后一个元素置为null帮助JVM回收避免内存泄漏size--时间复杂度O(n)移动元素开销。删除指定元素 问题若从前往后遍历删除元素后索引会发生变化可能导致漏删。例如数组[1,2,2,3]从前往后删除2第一次删除索引1的2后后续元素前移原索引2的2变为索引1下一次遍历到索引2会跳过这个2导致漏删。解决方案从后往前遍历删除元素后后续元素的位置不影响前面的遍历可避免漏删。因为从后往前删除时删除元素的位置之前的元素索引不会发生变化能保证所有符合条件的元素都被删除。代码示例public class ArrayListRemoveSimulation { private Object[] elementData new Object[10]; private int size 0; // 添加元素辅助方法 public void add(Object e) { if (size elementData.length) { int newCapacity elementData.length (elementData.length 1); elementData new Object[newCapacity]; } elementData[size] e; } // 删除所有指定元素从后往前遍历避免漏删 public void remove(Object e) { // 从后往前遍历找到等于e的元素并删除 for (int i size - 1; i 0; i--) { if (elementData[i] e || (elementData[i] ! null elementData[i].equals(e))) { // 移动元素将i之后的元素向前移动一位 for (int j i; j size - 1; j) { elementData[j] elementData[j 1]; } // 最后一个元素置null避免内存泄漏 elementData[size - 1] null; size--; } } } Override public String toString() { if (size 0) return []; StringBuilder sb new StringBuilder([); for (int i 0; i size; i) { sb.append(elementData[i]); if (i ! size - 1) sb.append(,); } sb.append(]); return sb.toString(); } public static void main(String[] args) { ArrayListRemoveSimulation list new ArrayListRemoveSimulation(); list.add(1); list.add(2); list.add(2); list.add(3); System.out.println(删除前 list); // 输出[1,2,2,3] list.remove(2); System.out.println(删除后 list); // 输出[1,3]所有2都被删除无漏删 } }打印重写ToStringArrayList重写了toString()方法核心是仅遍历0到size-1的有效元素而不是遍历整个底层数组避免打印底层数组中预留的默认值如null或0确保输出结果只包含用户添加的有效元素。原因底层数组的容量可能大于size例如扩容后容量为15但size为11剩余位置是未使用的默认值为null对象数组如果遍历整个数组会输出大量无意义的null影响可读性。实现逻辑重写toString()时通过循环遍历索引0到size-1的元素拼接字符串仅展示有效数据。示例import java.util.ArrayList; public class ArrayListToStringDemo { public static void main(String[] args) { ArrayListInteger list new ArrayList(); list.add(1); list.add(2); list.add(3); // ArrayList重写toString仅打印有效元素 System.out.println(list); // 输出[1, 2, 3] // 若直接打印底层数组假设获取到会包含null Object[] arr new Object[10]; arr[0] 1; arr[1] 2; arr[2] 3; System.out.println(Arrays.toString(arr)); // 输出[1, 2, 3, null, null, null, null, null, null, null]包含大量null } }
