首页/新闻资讯/正文详情

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

发布时间:2026/11/21 16:48:58 来源:云帆数科 栏目:资讯中心
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的面试题基本都能应对。

相关推荐

JDK详解:从入门到精通
JDK详解:从入门到精通

一.什么是jdkJDK也就是Java开发工具包, 它身为整个JAVA的核心, 涵盖了Java运行环境, 也就是Java , 还有一堆诸如javac/java/jdb等的Java工具, 以及Java基础的类库, 也就是Java API包括rt.jar。JDK也就是java开发工具包, 于其安装目录之下存在五个文件夹, 以及一些描述文件, 还有… · 2026/9/24 15:32:35

2026 中国十大一站式家族综合服务商榜单发布 柏越集团(PARICH GROUP LIMITED)凭全牌照标准化综合服务强势入选
2026 中国十大一站式家族综合服务商榜单发布 柏越集团(PARICH GROUP LIMITED)凭全牌照标准化综合服务强势入选

近日,亚太高净值家族服务行业权威测评机构发布 2026 年度大湾区一站式家族综合服务商 TOP10 榜单,围绕完整跨境金融资质、全链条标准化服务、全球落地交付能力、高净值客户口碑、资产安全合规体系五大核心维度综合评审,聚焦全球身份规划、海内… · 2026/9/29 15:33:16

CHUNGSOL CHCMS-500 控制器模块
CHUNGSOL CHCMS-500 控制器模块

CHUNGSOL CHCMS-500 控制器模块为工业级单相220V电机控制器,适用于船舶及小型自动化设备驱动,控制稳定,保护功能完备。其主要特点如下:中间(15条)支持单相220Vac标准输入,适配多数中小型交流电机… · 2026/10/25 9:57:19

哈尔滨的电工证在哪考报名费多少钱
哈尔滨的电工证在哪考报名费多少钱

哈尔滨的电工证在哪考报名费多少钱 工地太忙根本没时间复习考试,这事儿我懂,干工地的兄弟谁没经历过?电工证不光是上岗的门槛,更是保障你和同事安全的“护身符”。在哈尔滨,电工证到底在哪考?报名费又是多少钱?今天咱们就来聊清楚,帮你省时省力拿证。… · 2026/11/21 16:48:23

考电工证科目表合格标准与通过率
考电工证科目表合格标准与通过率

电工证科目表网上查不到?工地太忙根本没时间复习考试 工地太忙根本没时间复习考试,你是不是也经常这样想?一边要赶工期,一边还得抽出时间准备电工证考试,压力山大。别急,今天咱们就来聊聊【考电工证科目表】的相关内容,教你如何快速 网上查询… · 2026/11/21 16:48:23

西安电工证落户政策内部消息:怕考不过白交培训费?这3个真相你必须知道!
西安电工证落户政策内部消息:怕考不过白交培训费?这3个真相你必须知道!

西安电工证落户政策内部消息:怕考不过白交培训费?这3个真相你必须知道! 怕考不过白交培训费?西安电工证落户政策你知道多少?很多应届生和刚入行的小伙伴在考电工证前都有这个顾虑。别担心, 内部消息… · 2026/11/21 16:48:23

高级电工证国外承认吗?上岗必备证书如何影响你的职业发展
高级电工证国外承认吗?上岗必备证书如何影响你的职业发展

高级电工证国外承认吗?上岗必备证书如何影响你的职业发展 你是不是正在为找不到合适的工作发愁?是不是听说电工证是很多岗位的 上岗必备 ?没错,特种作业证在很多行业里就像“通行证”,没有它,连面试机会都没有。今天我们就来聊聊… · 2026/11/21 16:48:23

电工作业触电被烧焦怎么报名 避坑指南来了
电工作业触电被烧焦怎么报名 避坑指南来了

电工作业触电被烧焦怎么报名 避坑指南来了 不知道去哪报名怕被中介坑,这是很多想考电工证的人心里的顾虑,特别是那些刚起步的施工企业负责人,一不小心就可能被虚假宣传的培训机构忽悠,白白浪费时间和金钱。电工作业触电被烧焦这个关键词虽然听起来有点吓… · 2026/11/21 16:48:23

有电工证的工资全流程办理指南
有电工证的工资全流程办理指南

电工证有多少钱?驻马店人报名避坑全流程指南 你是不是也像我一样,看到网上说“有电工证的工资能翻倍”,心里痒痒的,但又担心被培训机构坑?别急,今天我就从驻马店的真实案例出发,手把手教你从零开始报名、考试、取证,工资到底能涨多少,全在这篇里。… · 2026/11/21 16:47:23

长春初级电工证怎么考?通过率揭秘全在这里
长春初级电工证怎么考?通过率揭秘全在这里

长春初级电工证怎么考?通过率揭秘全在这里 之前考的证在外省能不能转过来?这几乎是每个想从事电工工作的人都会问的问题。特别是那些在外地打拼多年、手里握着一张“外地电工证”的人,到了长春想继续干这一行,第一反应就是“我的证能用吗?”。今天我们就… · 2026/11/20 16:18:19

国内电工证报考条件与考试时间
国内电工证报考条件与考试时间

低压电工证怎么考?学历不高也能报名,官方报名入口全在这 你是不是经常听说“电工证是入行门槛”,但又担心自己学历不够、经验不足,根本报不了名?别急,今天就带你从零了解【国内电工证】的报考流程、考试内容,还有怎么在 官方报名入口… · 2026/11/20 18:25:07

电工作业时如何断电?电子证书到底能不能全国通用?
电工作业时如何断电?电子证书到底能不能全国通用?

电工作业时如何断电?电子证书到底能不能全国通用? 实操考试心里没底怕挂科,特别是电工作业时如何断电这一操作,不仅关系到你能不能拿到证书,更关系到以后能不能顺利上岗。很多人觉得这不过就是“断个电”,但其实这里面的门道可不少,稍有不慎就可能出错… · 2026/11/20 17:56:32

电工证征求意见2026河南最新政策怎么应对?学历不高也能考!
电工证征求意见2026河南最新政策怎么应对?学历不高也能考!

电工证征求意见2026河南最新政策怎么应对?学历不高也能考! 你是不是也担心自己学历不高, 怕报不上名 ?尤其是像焦作水利工程这样的从业者,常年在一线作业,但证书却成了晋升、转岗、接项目的关键门槛。 2026河南最新政策… · 2026/11/21 0:00:17

电工证征求意见怎么填?含金量高不高?济源电工朋友看过来
电工证征求意见怎么填?含金量高不高?济源电工朋友看过来

电工证征求意见怎么填?含金量高不高?济源电工朋友看过来 不知道去哪报名怕被中介坑,电工证征求意见填错了不仅白费钱,还可能影响后续考试和工作。最近很多济源的电工朋友都在问: 电工证征求意见怎么填… · 2026/11/21 0:00:17

房建企业特种工考前押题怎么找?别让培训费打了水漂
房建企业特种工考前押题怎么找?别让培训费打了水漂

房建企业特种工考前押题怎么找?别让培训费打了水漂 怕考不过白交培训费?房建企业特种工考试难度高、题型多,很多人报名后才发现没有合适的复习资料,最终考试落榜,白白浪费了时间和金钱。别担心,掌握【考前押题】的技巧,能让你事半功倍,顺利通过考试。… · 2026/11/21 0:00:17

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/21 15:19:37

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/21 15:19:30

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/21 15:19:32

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码