ArrayList 与顺序表复习笔记1. 学习目标掌握线性表、顺序表、ArrayList 的基本概念、常见操作、遍历方式、扩容机制以及 ArrayList 在实际案例中的使用。2. 线性表2.1 概念线性表是由n个具有相同特性的数据元素组成的有限序列。常见线性表包括顺序表链表栈队列2.2 逻辑结构与物理结构线性表在逻辑上是线性结构即元素之间呈现一条连续的线性关系。但线性表在物理存储上不一定连续常见的物理存储方式有两种数组存储物理地址连续。链式存储物理地址不一定连续通过引用或指针连接元素。3. 顺序表3.1 概念顺序表是使用一段物理地址连续的存储单元依次存储数据元素的线性结构。一般情况下顺序表底层使用数组实现并在数组上完成增、删、查、改等操作。3.2 顺序表的核心特点底层空间连续。支持通过下标随机访问。插入和删除可能需要搬移元素。容量不够时需要扩容。3.3 顺序表基本结构publicclassSeqList{privateint[]array;privateintsize;// 默认构造方法SeqList(){}// 将顺序表的底层容量设置为 initcapacitySeqList(intinitcapacity){}}其中array底层数组用于存储元素。size当前顺序表中的有效元素个数。3.4 顺序表常见接口// 新增元素默认在数组最后新增publicvoidadd(intdata){}// 在 pos 位置新增元素publicvoidadd(intpos,intdata){}// 判断是否包含某个元素publicbooleancontains(inttoFind){returntrue;}// 查找某个元素对应的位置publicintindexOf(inttoFind){return-1;}// 获取 pos 位置的元素publicintget(intpos){return-1;}// 将 pos 位置的元素设置为 valuepublicvoidset(intpos,intvalue){}// 删除第一次出现的关键字 keypublicvoidremove(inttoRemove){}// 获取顺序表长度publicintsize(){return0;}// 清空顺序表publicvoidclear(){}// 打印顺序表通常用于测试publicvoiddisplay(){}3.5 顺序表插入与删除的代价插入元素在指定位置插入元素时需要将该位置及其后面的元素整体向后移动一位。时间复杂度O(N)删除元素删除指定位置元素时需要将该位置后面的元素整体向前移动一位。时间复杂度O(N)4. ArrayList 简介4.1 ArrayList 的本质ArrayList是 Java 集合框架中的一个普通类实现了List接口。它的底层是一段连续空间支持动态扩容本质上是一个动态类型的顺序表。4.2 ArrayList 的主要特点使用泛型实现使用前通常需要实例化并指定元素类型。实现了RandomAccess接口支持随机访问。实现了Cloneable接口支持克隆。实现了Serializable接口支持序列化。底层使用数组存储元素。支持自动扩容。不是线程安全的。4.3 线程安全问题ArrayList适合在单线程环境中使用。多线程环境中可以考虑VectorCopyOnWriteArrayList5. ArrayList 的构造方法构造方法说明ArrayList()无参构造创建空列表ArrayList(int initialCapacity)指定初始容量ArrayList(Collection? extends E c)使用其他集合构造 ArrayList5.1 推荐写法ListIntegerlist1newArrayList();推荐使用接口接收实现类对象便于后续替换实现。5.2 指定初始容量ListIntegerlist2newArrayList(10);当可以预估元素数量时可以指定初始容量减少扩容次数。5.3 使用已有集合构造ArrayListIntegerlist3newArrayList(list2);构造完成后list3中的元素与list2中的元素一致。5.4 避免使用原生类型不推荐这样写Listlist4newArrayList();list4.add(111);list4.add(100);原因省略泛型后集合中可以存放任意类型元素后续使用时容易出现类型转换问题。推荐这样写ListIntegerlistnewArrayList();6. ArrayList 常见操作方法说明boolean add(E e)尾插元素evoid add(int index, E element)将元素插入到index位置boolean addAll(Collection? extends E c)尾插集合c中的所有元素E remove(int index)删除index位置的元素boolean remove(Object o)删除第一次出现的元素oE get(int index)获取index位置的元素E set(int index, E element)将index位置元素修改为elementvoid clear()清空集合boolean contains(Object o)判断元素是否存在int indexOf(Object o)返回元素第一次出现的下标int lastIndexOf(Object o)返回元素最后一次出现的下标ListE subList(int fromIndex, int toIndex)截取[fromIndex, toIndex)范围内的元素6.1 添加元素ListStringlistnewArrayList();list.add(JavaSE);list.add(JavaWeb);list.add(JavaEE);add(E e)默认将元素添加到末尾。6.2 获取元素个数System.out.println(list.size());size()返回集合中有效元素个数。6.3 获取指定位置元素System.out.println(list.get(1));注意下标范围必须是[0, size)否则会抛出下标越界异常。6.4 修改指定位置元素list.set(1,JavaWEB);set会覆盖指定下标位置上的原元素。6.5 指定位置插入元素list.add(1,Java数据结构);插入后原来index位置及其后面的元素会统一向后移动。6.6 删除指定元素list.remove(JVM);删除第一次出现的指定元素删除成功后其后面的元素会统一向前移动。6.7 删除指定下标元素list.remove(list.size()-1);注意下标不能超过有效元素范围否则会抛出下标越界异常。6.8 判断元素是否存在if(list.contains(测试课程)){list.add(测试课程);}contains返回true表示集合中存在指定元素否则返回false。6.9 查找元素位置list.add(JavaSE);System.out.println(list.indexOf(JavaSE));System.out.println(list.lastIndexOf(JavaSE));indexOf从前往后查找返回第一次出现的位置。lastIndexOf从后往前查找返回最后一次出现的位置。6.10 截取子列表ListStringretlist.subList(0,4);subList(0, 4)表示截取[0, 4)范围内的元素。注意subList返回的子列表与原列表存在关联修改时要特别小心。6.11 清空集合list.clear();System.out.println(list.size());clear()会清空所有有效元素。7. ArrayList 的遍历方式ArrayList常见遍历方式有三种for循环 下标foreach迭代器7.1 for 循环 下标for(inti0;ilist.size();i){System.out.print(list.get(i) );}特点适合需要使用下标的场景。ArrayList支持随机访问因此这种方式很常用。7.2 foreach 遍历for(Integerinteger:list){System.out.print(integer );}特点写法简洁。适合只读取元素、不关心下标的场景。7.3 迭代器遍历IteratorIntegeritlist.listIterator();while(it.hasNext()){System.out.print(it.next() );}迭代器是一种设计模式在 Java 集合框架中被广泛使用。8. ArrayList 扩容机制8.1 为什么需要扩容ArrayList底层使用数组存储元素数组长度固定。当元素数量超过当前数组容量时需要申请更大的新数组并将旧数组中的元素复制过去。8.2 默认容量当使用无参构造创建ArrayList时底层最初是一个空数组。第一次添加元素时默认容量会扩展为10。privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA{};privatestaticfinalintDEFAULT_CAPACITY10;8.3 添加元素时的扩容流程publicbooleanadd(Ee){ensureCapacityInternal(size1);elementData[size]e;returntrue;}添加元素时核心流程如下判断当前容量是否足够。如果容量足够直接插入元素。如果容量不够调用扩容逻辑。扩容完成后将元素放入数组末尾。size加一。8.4 计算容量privatestaticintcalculateCapacity(Object[]elementData,intminCapacity){if(elementDataDEFAULTCAPACITY_EMPTY_ELEMENTDATA){returnMath.max(DEFAULT_CAPACITY,minCapacity);}returnminCapacity;}如果底层数组还是默认空数组第一次扩容时容量取DEFAULT_CAPACITY和minCapacity中较大的值。8.5 触发扩容privatevoidensureExplicitCapacity(intminCapacity){modCount;if(minCapacity-elementData.length0){grow(minCapacity);}}当minCapacity大于当前数组长度时调用grow进行扩容。8.6 扩容大小intoldCapacityelementData.length;intnewCapacityoldCapacity(oldCapacity1);扩容时新容量通常是旧容量的1.5倍。其中oldCapacity1表示旧容量除以2。所以newCapacityoldCapacityoldCapacity/2;8.7 特殊情况如果用户实际需要的容量超过预估的1.5倍容量则按照实际需要的容量扩容。if(newCapacity-minCapacity0){newCapacityminCapacity;}如果需要扩容的大小超过最大数组限制则重新计算容量。privatestaticfinalintMAX_ARRAY_SIZEInteger.MAX_VALUE-8;8.8 真正扩容elementDataArrays.copyOf(elementData,newCapacity);Arrays.copyOf会申请新空间并将旧数组中的元素复制到新数组中。8.9 扩容流程总结插入元素前检查容量是否足够。容量不够时进入扩容流程。默认按照旧容量的1.5倍扩容。如果1.5倍仍然不够则按实际需求容量扩容。扩容前检查是否超过最大数组限制。使用Arrays.copyOf完成新数组申请和数据复制。9. ArrayList 的问题与思考9.1 任意位置插入、删除效率低ArrayList底层使用连续空间。在任意位置插入或删除元素时需要整体搬移后续元素。时间复杂度O(N)9.2 扩容有额外开销扩容过程需要申请新空间。拷贝旧数据。释放旧空间。因此频繁扩容会带来时间和空间上的额外消耗。9.3 可能造成空间浪费扩容通常会申请比当前实际需求更大的空间。例如容量扩到较大后如果后续只插入少量数据剩余空间就会被浪费。9.4 改进方向针对这些问题可以考虑使用其他数据结构链表适合频繁插入、删除的场景。LinkedListJava 集合框架中的链式线性表实现。合理设置初始容量减少扩容次数。根据业务选择数据结构频繁随机访问优先考虑ArrayList频繁插入删除可以考虑链表。10. 重点速记线性表是具有相同特性的数据元素组成的有限序列。顺序表底层使用连续空间一般用数组实现。ArrayList本质是动态顺序表。ArrayList支持随机访问查询指定下标元素效率高。ArrayList任意位置插入、删除效率较低时间复杂度为O(N)。ArrayList无参构造时第一次添加元素会扩容到默认容量10。ArrayList扩容通常按1.5倍增长。ArrayList不是线程安全的。使用泛型可以限制集合中存储的元素类型避免类型混乱。subList(fromIndex, toIndex)截取范围是左闭右开区间[fromIndex, toIndex)。11. 易错点整理11.1 下标越界get、set、remove(index)都要求下标合法。合法范围通常是0 index size插入时add(index, element)的合法范围通常是0 index size11.2 remove 的重载问题ArrayList中remove有两个常见重载remove(intindex)remove(Objecto)对于ListInteger删除整数元素时容易混淆ListIntegerlistnewArrayList();list.add(1);list.add(2);list.add(3);list.remove(1);// 删除下标为 1 的元素list.remove(Integer.valueOf(1));// 删除元素 111.3 subList 不是完全独立的新 ArrayListsubList返回的是原列表的一部分视图与原列表有关联。修改原列表或子列表时要注意可能互相影响。11.4 泛型不能省略不推荐使用ListlistnewArrayList();推荐使用ListStringlistnewArrayList();12. 面试与考试常问问题12.1 ArrayList 底层是什么底层是数组。12.2 ArrayList 为什么支持随机访问因为底层数组空间连续可以通过下标直接计算元素位置。12.3 ArrayList 插入和删除为什么慢因为在中间位置插入或删除元素时需要搬移后续元素。12.4 ArrayList 默认容量是多少第一次添加元素时默认容量为10。12.5 ArrayList 如何扩容容量不足时通常扩容为旧容量的1.5倍并通过Arrays.copyOf拷贝数据。12.6 ArrayList 是否线程安全不是线程安全的。多线程场景可以考虑Vector或CopyOnWriteArrayList。12.7 ArrayList 和顺序表有什么关系ArrayList可以看作 Java 中动态顺序表的一种实现。
