17-手写ArrayList：从0实现动态数组

手写ArrayList从0实现动态数组彻底搞懂自动扩容开篇你真的理解ArrayList吗日常开发中ArrayList是最常用的集合。但面试官追问ArrayList底层是怎么扩容的为什么默认容量是10删元素时为什么要System.arraycopy很多人就答不上来。最好的学习方式就是手写一遍。本文从0实现一个简易ArrayList把扩容、增删改查、迭代器原理全部讲透。一、ArrayList的本质ArrayList底层就是一个Object数组加上一个size计数器记录有效元素个数。Object[] elementData int size数组一旦创建长度就固定ArrayList的动态只是个假象容量不够时新建更大数组把旧数据拷贝过去。二、手写ArrayList骨架2.1 基本结构publicclassMyArrayListE{privateObject[]elementData;// 存元素的数组privateintsize;// 有效元素个数publicMyArrayList(){this(10);// 默认容量10}publicMyArrayList(intinitialCapacity){elementDatanewObject[initialCapacity];}publicintsize(){returnsize;}}【面试高频】JDK1.7中ArrayList初始化时就创建长度10的数组JDK1.8优化为延迟初始化首次add时才创建。三、add方法与扩容原理3.1 add实现publicbooleanadd(Ee){// 1. 检查是否需要扩容ensureCapacity(size1);// 2. 存入元素size1elementData[size]e;returntrue;}privatevoidensureCapacity(intminCapacity){if(minCapacityelementData.length){grow(minCapacity);}}3.2 扩容核心逻辑privatevoidgrow(intminCapacity){intoldCapacityelementData.length;// 新容量 旧容量 * 1.5intnewCapacityoldCapacity(oldCapacity1);// 处理新容量不够的边界情况if(newCapacityminCapacity){newCapacityminCapacity;}// 创建新数组拷贝旧数据elementDataArrays.copyOf(elementData,newCapacity);}【面试高频】ArrayList扩容是1.5倍计算方式是oldCapacity (oldCapacity 1)。用位运算比除法更高效。3.3 为什么是1.5倍太小如1.2倍频繁扩容频繁创建数组性能差太大如2倍浪费内存空间1.5倍是空间和时间的折中选择【面试陷阱】Vector扩容是2倍因为Vector是线程安全的扩容开销相对锁来说占比小。四、get与set方法4.1 get实现publicEget(intindex){rangeCheck(index);// 越界检查return(E)elementData[index];}privatevoidrangeCheck(intindex){if(indexsize||index0){thrownewIndexOutOfBoundsException(Index: index, Size: size);}}4.2 set实现publicEset(intindex,Eelement){rangeCheck(index);EoldValue(E)elementData[index];elementData[index]element;returnoldValue;}set返回旧值这是个容易忽略的细节。五、remove方法与数组拷贝5.1 按索引删除publicEremove(intindex){rangeCheck(index);EoldValue(E)elementData[index];// 计算需要移动的元素个数intnumMovedsize-index-1;if(numMoved0){System.arraycopy(elementData,index1,elementData,index,numMoved);}// 最后一位置null帮助GCelementData[--size]null;returnoldValue;}5.2 为什么要System.arraycopy删除中间元素后后面所有元素要整体前移一位。手动写循环效率低System.arraycopy是native方法直接操作内存性能最高。删除索引2的元素 [A, B, C, D, E, null] size5 ↓ [A, B, D, E, null, null] size4【面试高频】ArrayList的删除是O(n)操作因为要移动元素。这也是LinkedList存在的价值。5.3 按元素删除publicbooleanremove(Objecto){if(onull){for(inti0;isize;i){if(elementData[i]null){fastRemove(i);returntrue;}}}else{for(inti0;isize;i){if(o.equals(elementData[i])){fastRemove(i);returntrue;}}}returnfalse;}【面试陷阱】按元素删除用equals比较不是。所以自定义类必须重写equals。六、迭代器原理6.1 为什么不用for循环遍历删除for(inti0;ilist.size();i){if(list.get(i).equals(a)){list.remove(i);// 会导致索引错乱}}删除后size变化后面元素前移导致跳过下一个元素。6.2 手写迭代器publicclassMyIteratorE{privateObject[]elementData;privateintsize;privateintcursor;// 下一个要返回的索引publicMyIterator(Object[]elementData,intsize){this.elementDataelementData;this.sizesize;}publicbooleanhasNext(){returncursorsize;}SuppressWarnings(unchecked)publicEnext(){return(E)elementData[cursor];}}6.3 fail-fast机制JDK的ArrayList迭代器有modCount检查遍历过程中如果用list.remove修改结构会抛ConcurrentModificationException。正确做法是用迭代器的remove方法它会同步更新modCount。七、完整测试publicclassTest{publicstaticvoidmain(String[]args){MyArrayListStringlistnewMyArrayList();// 测试add和扩容for(inti0;i15;i){list.add(元素i);}System.out.println(size: list.size());// 15// 测试getSystem.out.println(list.get(0));// 元素0System.out.println(list.get(14));// 元素14// 测试setlist.set(0,新元素);System.out.println(list.get(0));// 新元素// 测试removelist.remove(0);System.out.println(list.get(0));// 元素1System.out.println(size: list.size());// 14}}八、与JDK源码的对比维度我的实现JDK实现默认容量1010延迟初始化扩容倍数1.51.5删除方式arraycopyarraycopy序列化无重写writeObject/readObjectfail-fast无modCount机制并发修改无保护抛CME异常【面试高频】ArrayList用transient修饰elementData自定义序列化只写有效元素节省空间。九、性能对比操作ArrayListLinkedList随机访问O(1)O(n)头部插入O(n)O(1)尾部插入平均O(1)O(1)中间插入O(n)O(n)删除O(n)O(n)内存占用紧凑每个节点额外存前后指针【面试陷阱】不要以为LinkedList插入删除一定比ArrayList快。中间位置插入LinkedList也要先遍历到位置时间复杂度也是O(n)。十、开发踩坑实录坑 1边遍历边删除for(Strings:list){if(s.equals(a)){list.remove(s);// ConcurrentModificationException}}正确做法用迭代器remove或Java 8的removeIf。坑 2subList修改影响原ListListIntegersublist.subList(1,3);sub.set(0,100);// 原list也被修改原因subList返回的是视图不是副本。坑 3Arrays.asList不能addListIntegerlistArrays.asList(1,2,3);list.add(4);// UnsupportedOperationException原因返回的是Arrays内部类不是真正的ArrayList。十一、面试速记卡11.1 核心知识点知识点答案底层结构Object数组默认容量10JDK8延迟初始化扩容倍数1.5倍扩容方式Arrays.copyOf删除元素System.arraycopy前移是否线程安全否随机访问O(1)序列化transient修饰数组自定义序列化11.2 高频面试题ArrayList底层是什么默认容量是多少ArrayList扩容机制是怎样的为什么是1.5倍ArrayList和Vector有什么区别ArrayList和LinkedList有什么区别ArrayList的remove是怎么实现的为什么遍历时删除会抛ConcurrentModificationExceptionArrayList用transient修饰数组的原因ArrayList在多线程下会有什么问题11.3 口诀底层Object数组默认容量是10 扩容一点五倍Arrays.copyOf来拷贝 删除arraycopy前移最后一位置null 随机访问O一插入删除O n transient修饰数组自定义序列化省空间十二、小结手写一遍ArrayList你对扩容、删除、迭代器原理都会有深刻理解。面试时被问到ArrayList能从源码角度回答比背八股强一百倍。记住ArrayList的核心数组1.5倍扩容System.arraycopy。这三个点搞懂ArrayList的面试题基本都能应对。