7月22日-23日课程复习笔记数组核心操作与ArrayList原理本次课程深入探讨了数组这一基础数据结构的增删改查操作重点剖析了二分查找算法的实现细节与边界陷阱。同时课程还讲解了在有序数组中进行插入和删除的特殊逻辑并揭示了Java原生数组的局限性以及ArrayList通过动态扩容实现“可变”的底层原理。第一部分数组的增删改查核心操作1. 数组的基本特性连续存储数组在内存中占据一块连续的地址空间每个元素通过下标直接访问。随机访问由于连续存储的特性通过下标访问元素的时间复杂度为O(1)效率极高。固定长度Java中的原生数组一旦创建其长度length就不可改变。2. 插入操作 (Add)核心思路在指定位置插入新元素需要将该位置及其之后的所有元素向后移动一位腾出空间后再进行赋值。移动顺序必须从后往前依次移动元素。如果从前往后移动会导致后续元素被覆盖而丢失。时间复杂度平均需要移动一半的元素时间复杂度为O(n)。因此数组不适合频繁插入的场景。边界检查插入位置必须在有效范围内即0到size包含size表示在末尾追加。3. 删除操作 (Delete)核心思路删除指定位置的元素需要将该位置之后的所有元素向前移动一位覆盖掉目标元素。移动顺序从前往后依次覆盖即可。逻辑删除数组的删除是逻辑上的通过将后续元素前移覆盖并将有效数据长度size减1来实现。末尾被覆盖的位置成为无效数据无需特殊处理。删除所有匹配项当需要删除数组中所有值为x的元素时必须从后往前遍历。如果从前往后遍历删除一个元素后后续元素前移可能会导致连续的相同元素被跳过检查造成漏删。删除首个匹配项当只需要删除第一个匹配的元素时应从前往后遍历找到后立即删除并结束循环效率更高。4. 查找操作 (Search)线性查找适用于无序数组。通过遍历数组逐个比较时间复杂度为O(n)。二分查找仅适用于有序数组。通过不断将查找范围缩小一半来快速定位目标值时间复杂度为O(log n)。第二部分二分查找算法详解1. 核心思想分治法每次比较目标值与查找范围的中间值mid根据比较结果舍弃一半的数据将搜索范围缩小到另一半。2. 两种实现方式与边界陷阱二分查找的实现关键在于循环条件和边界更新主要有两种写法必须配套使用否则会导致死循环或漏查。写法一左闭右闭区间[left, right]循环条件while (left right)。当left等于right时区间内仍有一个元素需要检查。边界更新目标值大于mid值left mid 1。目标值小于mid值right mid - 1。关键点必须使用mid ± 1来更新边界确保搜索范围真正缩小避免left和right卡住导致死循环。写法二左闭右开区间[left, right)循环条件while (left right)。当left等于right时区间为空循环结束。初始值right应初始化为array.length因为右边界是开区间不包含该位置。边界更新目标值大于mid值left mid 1。目标值小于mid值right mid。因为right是开区间mid位置的值已经比较过且不符合新的搜索范围应排除mid。第三部分有序数组的特殊操作1. 有序数组插入核心思路在保持数组有序的前提下插入新元素。实现步骤定位遍历数组找到第一个大于目标值的位置该位置即为插入点。扩容检查检查数组是否已满size array.length如果已满则需要先扩容。移动从插入点开始将所有后续元素向后移动一位。插入将新元素放入腾出的空位并将size加1。边界情况插入最大值如果新元素比数组中所有元素都大则直接插入到数组末尾size位置。空数组如果数组为空size 0直接插入即可。2. 有序数组删除删除逻辑与普通数组相同但删除后仍需保持数组的有序性。删除操作本身不会破坏有序性。第四部分Java原生数组的局限性与ArrayList1. 原生数组的局限性长度固定创建后无法改变长度难以应对数据量不确定的场景。开小了会溢出开大了会浪费空间。2. ArrayList的实现原理封装ArrayList底层封装了一个原生数组并提供了一套动态增删改查的方法。动态扩容机制初始容量ArrayList在创建时会分配一个初始容量通常为10。容量检查每次添加元素时都会检查当前有效数据量size是否等于数组长度。创建新数组如果数组已满会创建一个新的、更大的数组。新数组的长度通常是原数组长度的1.5倍。数据复制将原数组中的所有数据逐个复制到新数组中。引用更新将ArrayList内部的数组引用指向这个新数组。原数组因没有引用指向会被垃圾回收器回收。本质所谓的“动态扩容”并非修改了原数组而是通过“创建新数组 - 复制数据 - 更新引用”的方式实现了“可变”的视觉效果。有效数据管理ArrayList使用一个size变量来记录当前存储的有效元素个数。这个size变量有两个作用记录当前元素数量。指向下一个新元素的插入位置因为数组下标从0开始。在打印或遍历时只处理0到size-1范围内的有效数据避免打印出数组中无效的默认值如0。package com.array.demo; import java.util.ArrayList; public class ChangeArray { static ArrayListString list new ArrayListString(); static ArrayListInteger list2 new ArrayListInteger(); public static void main(String[] args) { list.add(114514); list.add(1145141919810); list.add(2, element); list.remove(1); list.set(0, 1919801); // 1. 根据索引查找元素 String element list.get(0); // 获取索引0的元素 // 2. 根据元素查找索引第一次出现的位置 int index list.indexOf(1919801); // 返回该元素首次出现的索引 // 3. 根据元素查找索引最后一次出现的位置 int lastIndex list.lastIndexOf(element); // 返回该元素最后出现的索引 // 4. 判断是否包含某个元素 boolean contains list.contains(1919801); // 返回 true/false System.out.println(list); System.out.println(index); } }