全文目录开篇语一、ArrayList一间会自动扩建的“顺序仓库”1.1 底层结构1.2 扩容机制grow 策略1.3 时间复杂度分析ArrayList二、LinkedList一条会插队的“双向人链”2.1 底层结构双向链表2.2 时间复杂度分析LinkedList2.3 ArrayList vs LinkedList 场景对比三、CopyOnWriteArrayList读的时候“看旧版”写的时候“印新版”3.1 写时复制机制3.2 迭代器的“快照语义”3.3 时间复杂度与代价3.4 适用场景四、三者总结到底什么时候选谁文末开篇语哈喽各位小伙伴们你们好呀我是喵手。运营社区C站/掘金/腾讯云/阿里云/华为云/51CTO欢迎大家常来逛逛今天我要给大家分享一些自己日常学习到的一些知识点并以文字的形式跟大家一起交流互相学习一个人虽可以走的更快但一群人可以走的更远。我是一名后端开发爱好者工作日常接触到最多的就是Java语言啦所以我都尽量抽业余时间把自己所学到所会的通过文章的形式进行输出希望以这种方式帮助到更多的初学者或者想入门的小伙伴们同时也能对自己的技术进行沉淀加以复盘查缺补漏。小伙伴们在批阅的过程中如果觉得文章不错欢迎点赞、收藏、关注哦。三连即是对作者我写作道路上最好的鼓励与支持一、ArrayList一间会自动扩建的“顺序仓库”1.1 底层结构底层是动态数组Object[] elementData元素在内存中是连续存储的支持随机下标访问因此get(index)和set(index)是 O(1)ListStringlistnewArrayList();list.add(A);list.add(B);list.add(C);System.out.println(list.get(1));// B典型 O(1) 访问1.2 扩容机制grow 策略看下核心思想就行不用死记源码细节。当你add一个元素而内部数组已经满了就会触发扩容操作大致伪代码基于 JDK 8 思路简化privatevoidgrow(intminCapacity){intoldCapacityelementData.length;// 1.5 倍扩容newCapacity old old/2intnewCapacityoldCapacity(oldCapacity1);if(newCapacityminCapacity){newCapacityminCapacity;}// 复制到新数组elementDataArrays.copyOf(elementData,newCapacity);}关键点总结扩容比例约 1.5 倍数组拷贝成本O(n)每次扩容都要把旧数组的元素复制到新数组里均摊复杂度amortized虽然扩容是 O(n)但不是每次add都扩容所以末尾追加 add 操作平均是 O(1)1.3 时间复杂度分析ArrayList操作复杂度说明get(index)O(1)直接按下标访问数组set(index, element)O(1)直接覆盖数组元素add(element)尾部均摊 O(1)偶尔会 O(n) 扩容add(index, element)O(n)需要挪动 index 之后的所有元素remove(index)O(n)需要把后面的元素往前搬contains(element)O(n)线性遍历一句话ArrayList读快随机访问牛中间插删慢。适合“读多写少且多是尾部追加”的场景。二、LinkedList一条会插队的“双向人链”2.1 底层结构双向链表LinkedList底层是双向链表每个节点长这样privatestaticclassNodeE{Eitem;NodeEnext;NodeEprev;}特点每个节点知道自己的prev和next内存不连续通过引用把节点串起来头尾插入删除很快中间插入/删除只要找到节点改指针即可简单示例LinkedListStringlistnewLinkedList();list.add(A);// 尾部插入list.addFirst(0);// 头部插入 O(1)list.addLast(B);// 尾部插入 O(1)list.removeFirst();// 头删 O(1)list.removeLast();// 尾删 O(1)2.2 时间复杂度分析LinkedList重点来了随机访问其实不行。操作复杂度说明get(index)O(n)需要从头/尾走到 indexaddFirst(element)/addLastO(1)只改头尾指针removeFirst()/removeLast()O(1)同上在“已知节点处”插入/删除内部方法O(1)修改前后指针即可add(index, element)O(n)先 O(n) 找到节点再 O(1) 插入remove(index)O(n)同理contains(element)O(n)线性遍历也就是说你不知道节点位置只给 index它很慢O(n)你只在头尾操作它很快2.3 ArrayList vs LinkedList 场景对比我们来搞个“擂台表”维度ArrayListLinkedList底层结构动态数组双向链表随机访问get(index)O(1)✅ 很快O(n)❌ 需要遍历尾部追加add(element)均摊O(1)O(1)尾插中间插入/删除O(n)搬运数组元素O(n)找到节点接着 O(1) 插入头部插入/删除O(n)O(1)非常适合内存局部性好数组连续差节点分散典型使用场景查询多、按索引访问多频繁头尾操作、频繁插入删除换句话说如果你的逻辑经常get(i)、set(i)、for 循环按下标遍历 —— 优先 ArrayList如果你是队列双端队列频繁在头尾插入删除 —— 可以考虑 LinkedList或 ArrayDeque三、CopyOnWriteArrayList读的时候“看旧版”写的时候“印新版”现在上场的是偏“并发场景”的大哥CopyOnWriteArrayList。名字很直白“写时复制”。3.1 写时复制机制核心思想一句话读时不加锁写时复制一个新数组把修改后的新数组替换旧数组。简化版伪代码非真实源码只讲原理publicbooleanadd(Ee){finalReentrantLocklockthis.lock;lock.lock();try{Object[]oldArrayarray;intlenoldArray.length;// 1. 新建一个数组比原来多 1 个Object[]newArrayArrays.copyOf(oldArray,len1);// 2. 把新元素放在最后newArray[len]e;// 3. 用新数组替换旧的arraynewArray;returntrue;}finally{lock.unlock();}}读取操作publicEget(intindex){return(E)array[index];// 直接读不加锁}所以特性是读无锁非常适合高并发读写每次都复制整个数组代价昂贵O(n) 且创建新数组3.2 迭代器的“快照语义”CopyOnWriteArrayList的另一个特点是它的迭代器遍历的是创建迭代器那一刻的快照数组。即遍历过程中即使别的线程修改了列表你也不会ConcurrentModificationException你看到的就是某个时间点的“历史版本”示例代码CopyOnWriteArrayListStringlistnewCopyOnWriteArrayList();list.add(A);list.add(B);for(Strings:list){System.out.println(s);list.add(C);// 不会抛 ConcurrentModificationException}System.out.println(Size: list.size());// 3 or more看你加了几次对比ArrayListListStringlistnewArrayList();list.add(A);list.add(B);for(Strings:list){System.out.println(s);list.add(C);// 这里会抛 ConcurrentModificationException}3.3 时间复杂度与代价操作复杂度说明读get(index)O(1)无锁从当前数组快照读遍历O(n)无锁基于快照数组add/remove/setO(n) 分配数组复制旧数组并修改并发读写是否安全是读无锁写有锁优点读操作极其简单、安全不会ConcurrentModificationException遍历无锁适合读多写少场景缺点写操作非常重复制整个数组 GC 压力不适合写多、列表很大的场景3.4 适用场景一句非常实在的话CopyOnWriteArrayList “读特别多写很少”的并发场景神器。常见使用场景监听器列表、订阅者列表偶尔注册/取消频繁通知系统配置列表启动时初始化运行中偶尔变更读取很多白名单/黑名单缓存偶尔更新、频繁检查示例classEventBus{privatefinalCopyOnWriteArrayListListenerlistenersnewCopyOnWriteArrayList();publicvoidregister(Listenerl){listeners.add(l);// 写少}publicvoidpublish(Evente){for(Listenerl:listeners){// 读多l.onEvent(e);}}}四、三者总结到底什么时候选谁如果把三者当成“角色卡”能大概这么选ArrayList主打随机访问快遍历快内存局部性好场景大部分是读和尾部追加比如分页数据、列表展示、缓存数组等并发非线程安全多线程要自己加锁或用Collections.synchronizedListLinkedList主打头尾插删快场景作为队列/双端队列Deque如频繁addFirst/removeFirst但在现代 Java 里很多情况下用ArrayDeque会更合适CopyOnWriteArrayList主打并发读多写少读无锁遍历安全场景监听器列表、配置列表、几乎只读的共享集合不适合写操作频繁、集合超大… …文末好啦以上就是我这期的全部内容如果有任何疑问欢迎下方留言哦咱们下期见。… …学习不分先后知识不分多少事无巨细当以虚心求教三人行必有我师焉wished for you successed ⭐️若喜欢我就请关注我叭。⭐️若对您有用就请点赞叭。⭐️若有疑问就请评论留言告诉我叭。版权声明本文由作者原创转载请注明出处谢谢支持