首页 > 代码库 > java ArrayList 实现
java ArrayList 实现
关于ArrayList的实现和原理,原文出处:http://www.cnblogs.com/ITtangtang/p/3948555.html
我觉得他写的非常好,真的很好.
做一个记录和总结吧
public class arraylist<E> { /** * 存放集合的元素 * */ private transient Object[] elementData; /** 元素的大小 */ private int size;
定义了一个泛型类,一个object的数组和一个私有变量来记录该集合的元素数量,原文多了一个私有变量,我也不知道干嘛用的,作者也没解释也没提及到,我没使用也没事
1 /** 2 * 根据指定大小初始化 3 * @param initialCapacity 4 */ 5 public arraylist(int initialCapacity){ 6 super(); 7 if(initialCapacity<=0){ 8 //抛异常 9 throw new IllegalArgumentException("初始化参数不能小于0"); 10 }else{ 11 //初始化数组 12 this.elementData=http://www.mamicode.com/new Object[initialCapacity]; 13 } 14 } 15 /** 16 * 默认初始化 17 */ 18 public arraylist(){ 19 this(10); 20 } 21 /** 22 * 根据一个集合类初始化 23 * @param c 一个必须继承了Collection接口的类 24 */ 25 public arraylist(Collection<? extends E> c){ 26 //初始化 27 elementData=http://www.mamicode.com/c.toArray(); 28 size=elementData.length; 29 //如果不是任意类型的数组就转换Objec类型 30 if (elementData.getClass() != Object[].class){ 31 elementData=http://www.mamicode.com/Arrays.copyOf(elementData,size, Object[].class); 32 } 33 } 34
3个初始化方法,根据默认大小进行数组的初始化,给定大小初始化和传递一个继承了Collection集合接口的类进行转换赋值初始化
1 /** 2 * 扩容集合 3 * @param minCapacity 4 */ 5 public void ensureCapacity(int minCapacity){ 6 /** 当前数组的大小 */ 7 int oldCapacity = elementData.length; 8 if (minCapacity > oldCapacity) { 9 /** 10 * oldData 虽然没有被使用,但是这是关于内存管理的原因和Arrays.copyOf()方法不是线程安全 11 * oldData在if的生命周期内引用elementData这个变量,所以不会被GC回收掉 12 * 当Arrays.copyOf()方法在把elementData复制到newCapacity时,就可以防止新的内存或是其他线程分配内存是elementData内存被侵占修改 13 * 当结束是离开if,oldData周期就结束被回收 14 */ 15 Object oldData[] = elementData; 16 int newCapacity = (oldCapacity * 3)/2 + 1; //增加50%+1 17 if (newCapacity < minCapacity) 18 newCapacity = minCapacity; 19 //使用Arrays.copyOf把集合的元素复制并生成一个新的数组 20 elementData =http://www.mamicode.com/ Arrays.copyOf(elementData, newCapacity); 21 } 22 }
这是一个核心的方法,集合的扩容,其实是对数组的扩容,minCapacity集合的大小,进行对比判断是否应该进行扩容,使用了Arrays.copyOf()方法进行扩容,
原文有进行详细的解释,这个方法把第一个参数的内容复制到一个新的数组中,数组的大小是第二个参数,并返回一个新的数组,关于oldData的变量上文有详细的注释
1 /** 2 * 检查索引是否出界 3 * @param index 4 */ 5 private void RangeCheck(int index){ 6 if(index > size || index < 0){ 7 throw new IndexOutOfBoundsException("下标超出,Index: " + index + ", Size: " +size); 8 } 9 }
一个下标的检索是否出 1 /**
2 * 添加元素 3 * 将指定的元素添加到集合的末尾 4 * @param e 添加的元素 5 * @return 6 */ 7 public boolean add(E e){ 8 ensureCapacity(size+1); 9 elementData[size]=e; 10 size++; 11 return true;
12 }
添加元素,先进行扩容,在赋值,然后元素加一,注意 size+1 字段size并没有加一,这里进行的是算术的运算,所以在后面才需要进行自增
1 /** 2 * 添加元素 3 * 将元素添加到指定的位置 4 * @param index 指定的索引下标 5 * @param element 元素 6 * @return 7 */ 8 public boolean add(int index, E element){ 9 RangeCheck(index); 10 ensureCapacity(size+1); 11 // 将 elementData中从Index位置开始、长度为size-index的元素, 12 // 拷贝到从下标为index+1位置开始的新的elementData数组中。 13 // 即将当前位于该位置的元素以及所有后续元素右移一个位置。 14 System.arraycopy(elementData, index, elementData, index+1, size-index); 15 elementData[index]=element; 16 size++;//元素加一 17 return true; 18 }
这里不同的是 System.arraycopy(elementData, index, elementData, index+1, size-index);
这是一个c的内部方法,详细的原文有解释,这里就不说了,这个也是整个ArrayList的核心所在,也Arrays.copyOf()的内部实现原理
1 /** 2 * 添加全部元素 3 * 按照指定collection的迭代器所返回的元素顺序,将该collection中的所有元素添加到此列表的尾部。 4 * @param c 5 * @return 6 */ 7 public boolean addAll(Collection < ? extends E>c){ 8 Object[] newElement=c.toArray(); 9 int elementLength=newElement.length; 10 ensureCapacity(size+elementLength); 11 //从newElement 0的下标开始,elementLength个元素,elementData size的下标 12 System.arraycopy(newElement, 0, elementData, size, elementLength); 13 size+=elementLength; 14 return elementLength!=0; 15 }
基本上其他方法都只是根据不同的情况进行不同的处理,比如通过接口把数据对象传递进来然后获取长度进行扩容,在把数据使用System,arraycopy复制到新的数组中
1 /** 2 * 指定位置,添加全部元素 3 * @param index 插入位置的下标 4 * @param c 插入的元素集合 5 * @return 6 */ 7 public boolean addAll(int index, Collection<? extends E> c){ 8 if(index > size || index < 0){ 9 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " +size); 10 } 11 Object[] newElement=c.toArray(); 12 int elementLength=newElement.length; 13 ensureCapacity(size+elementLength); 14 int numMoved=size-index; 15 //判断插入的位置是否在数组中间 16 if(numMoved>0){ 17 //把index插入位置的后面的所有元素往后移 18 //elementData index下标开始的numMoved个元素插入到elementData 的index+elementLength位置 19 System.arraycopy(elementData, index, elementData, index+elementLength, numMoved); 20 } 21 //把newElement里从0开始的elementLength个元素添加到elementData index开始的位置 22 System.arraycopy(newElement, 0, elementData, index, elementLength); 23 size += elementLength; 24 return elementLength != 0; 25 } 26 27 /** 28 * 指定下标赋值 29 * @param index 30 * @param element 31 * @return 32 */ 33 public E set(int index,E element){ 34 RangeCheck(index); 35 E oldElement=(E)elementData[index]; 36 elementData[index]=element; 37 return oldElement; 38 } 39 40 /** 41 * 根据下标取值 42 * @param index 43 * @return 44 */ 45 public E get(int index){ 46 RangeCheck(index); 47 return (E)elementData[index]; 48 } 49 50 /** 51 * 根据下标移除元素 52 * @param index 53 */ 54 public E remove(int index){ 55 RangeCheck(index); 56 E oldElement=(E)elementData[index]; 57 /** 移除的下标后面的元素数量 */ 58 int numMoved=size-index-1; 59 //如果在数组范围内就进行移动 60 if(numMoved>0) 61 System.arraycopy(elementData, index+1, elementData, index, numMoved); 62 //移除 63 elementData[--size]=null; 64 return oldElement; 65 } 66 67 /** 68 * 根据元素移除 69 * @param obj 70 * @return 71 */ 72 public boolean remove(Object obj){ 73 //Arraylist允许存放null,所以也要进行判断处理 74 if(obj==null){ 75 for(int index=0;index<size;index++){ 76 if(elementData[index]==null){ 77 remove(index); 78 return true; 79 } 80 } 81 }else{ 82 for(int index=0;index<size;index++){ 83 if(obj.equals(elementData[index])){ 84 remove(index); 85 return true; 86 } 87 } 88 } 89 return false; 90 } 91 92 /** 93 * 根据下标移除指定范围内的元素 94 * @param fromIndex 开始 95 * @param toIndex 结束 96 */ 97 protected void removeRange(int fromIndex, int toIndex){ 98 RangeCheck(fromIndex); 99 RangeCheck(toIndex); 100 //要移动的元素数 101 int numMoved = size - toIndex; 102 //把toIndex后面的元素移动到fromIndex 103 System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); 104 //要移除的元素数量 105 int newSize=size-(toIndex-fromIndex); 106 while(size!=newSize){ 107 elementData[--size]=null; 108 } 109 } 110 111 /** 112 * 把数组容量调整到实际的容量 113 */ 114 public void trimToSize(){ 115 int leng=elementData.length; 116 if(size<leng){ 117 Object[] old=elementData; 118 elementData=http://www.mamicode.com/Arrays.copyOf(elementData, size); 119 } 120 } 121 /** 122 * 把集合元素转换成数组 123 * @return 124 */ 125 public Object[] toArray(){ 126 return Arrays.copyOf(elementData, size); 127 } 128 129 public <T>T[] toArray(T[] a){ 130 if(a.length<size){ 131 return (T[]) Arrays.copyOf(elementData,size, a.getClass()); 132 } 133 //把集合元素复制到a数组中 134 System.arraycopy(elementData, 0, a, 0, size); 135 if (a.length > size){ 136 for(int index=size;index<a.length;index++){ 137 a[index] = null; 138 } 139 } 140 return a; 141 }
基本上都是对数组进行操作和使用c的方法进行赋值移动等,详细的可以查看原文,原文中除了那个私有变量外也没多少问题,代码可以完美运行,这李要注意的和难点就会是System,arraycopy和Arrayist.copy()这2个方法
和在扩容方法里oldData这个变量的使用,这个变量真的很好,一开始我也不知道为什么要这么使用,在原文的末尾会进行解释。
java ArrayList 实现