List集合底层分析

List集合子类ArrayList、Vector、LinkedList底层及扩展机制分析ArrayList特点高效的数组查询和修改，快速的不安全和有序的扩展机制1.初始化时使用无参构造函数，将创建一个elementData没有初始容量的空数组。/***DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空数组*privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};*构造一个初始容量为10的空列表。*/publicArrayList(){这个。elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}2。第一次add操作调用set时，会判断当前数组elementData是否为空。如果为空，则形成最小要求容量为10的最小长度，然后扩容。如果根据所需容量计算出的结果小于0，则进行新容量的未赋值操作，然后调用Arrays.copyOf方法对数组进行赋值，赋值完成。3.当需求容量大于10时，将容量扩充为现有容量的1.5倍，完成分配。4.使用参数化结构时，使用参数化结构初始化elementData数组。当容量不够时，同上3.privatevoidgrow(intminCapacity){//溢出意识代码//当前数组的长度intoldCapacity=elementData.length;//计算扩容intnewCapacity=oldCapacity+(oldCapacity>>1);//当需求容量大于新容量时，使用需求容量进行扩容if(newCapacity-minCapacity<0)newCapacity=minCapacity;如果(newCapacity-MAX_ARRAY_SIZE>0)newCapacity=hugeCapacity(minCapacity);//minCapacity通常接近大小，所以这是一个胜利：elementData=Arrays.copyOf(elementData,newCapacity);}vectorcollection低效数组安全性（同步悲观锁）顺序扩容机制1.无参构造初始化时，默认容量为10./***构造一个空vector，使其内部数据数组*大小为{@code10}并且它的标准容量增量是*零。*/publicVector(){这(10);}2.当需求容量小于现有容量时，容量将扩大现有容量的两倍privatevoidgrow(intminCapacity){//溢出意识代码intoldCapacity=elementData.le恩;//因为capacityIncrement默认为0，扩容相当于：现有容量+现有容量（2倍）intnewCapacity=oldCapacity+((capacityIncrement>0)?capacityIncrement:oldCapacity);如果(newCapacity-minCapacity<0)newCapacity=minCapacity;如果(newCapacity-MAX_ARRAY_SIZE>0)newCapacity=hugeCapacity(minCapacity);elementData=Arrays.copyOf(elementData,newCapacity);}3。调用Arrays.copyOf方法复制数组并完成赋值LinkedList特性增加和删除底层非数组，而是一个Node对象[prev(上一个元素)，item(存储)，next(下一个元素))]双重不安全链表分析1、首先要知道linkedList的一个内部类Node对象，这个对象有三个属性，分别是item：要存储的值，next：下一个元素，prev：上一个元素。私有静态类Node{E项；下一个节点；节点上一个；Node(Nodeprev,Eelement,Nodenext){this.item=element;这个.下一个=下一个；this.prev=prev;}}1.1可以自己创建一个Node节点对象，玩玩node节点的连接方式。节点类{公共T对象；下一个公共节点；公共节点前；公共节点（Tobj）{this.obj=obj;}@OverridepublicStringtoString(){return"Node{"+"obj="+obj+'}';}}1.2测试代码，创建三个node节点，将每个节点连接起来，形成链式结构。NodeXM=newNode<>("小明");NodeZS=newNode<>("张三");NodeLS=newNode<>("李四");//让每个节点的下一个节点指向下一个对象XM.next=ZS;ZS.next=LS;//每个节点的前一点LS.pre=ZS;ZS.pre=XM;Nodefirst=newNode<>("First");节点最后=新节点<>("最后");首先=XM；//根据第一个元素遍历while(true){if(first==null){break;}System.out.println(first);第一个=第一个.下一个；}System.out.println("===================pre=================");最后=LS;while(true){if(last==null){中断；}System.out.println(last);最后=最后.pre;}//在张三和李四之间插入小红/***1.将张三的下一个元素指向李四*2.将小红的下一个元素指向李四*3.将小红的最后一个元素指向张三*4.将李四的最后一个元素指向小红*/点头eXH=newNode<>("小红");ZS.next=XH;XH.next=LS;XH.pre=ZS;LS.pre=XH;System.out.println("==========插入小红后=============");首先=XM；//根据第一个元素遍历while(true){if(first==null){break;}System.out.println(first);第一个=第一个.下一个；}System.out.println("====================前=================");最后=LS;while(true){if(last==null){中断；}System.out.println(last);last=last.pre;}2。初始化linkedList集合后，将创建一个空集合。此时内部的三个属性，大小为0，第一个和最后一个属性为null/***构造一个空列表。*/publicLinkedList(){}3.当集合执行第一次添加操作时，真正完成的是将最后一个元素与新添加的元素连接起来。此时集合的last属性为null，元素e既是第一个又是最后一个元素。/***链接e作为最后一个元素。*/voidlinkLast(Ee){finalNodel=last;finalNodenewNode=newNode<>(l,e,null);最后一个=新节点；如果（l==null）首先=newNode；elsel.next=newNode;尺码++；模数++；}4.第二次添加集合时，会直接将最后一个属性作为新元素的前一个元素。当新元素是集合的最后一个元素，且此时l不为空时，将l的下一个元素指向新元素。