ArrayList源码解析及简单自定义ArrayList

ArrayList数据结构图:

   blob.png

  ArrayList是我们使用得最多的一个集合类之一,一般用来做包装DTO到view层来显示数据.ArrayList继承了AbstractList类,实现了List,RandomAccess,Cloneable接口  

  1.    public class ArrayList<E> extends AbstractList<E>  

  2.         implements List<E>, RandomAccess, Cloneable, java.io.Serializable 

  内部结构是一个Object类型的数组

  1. private transient Object[] elementData;  

  ArrayList的大小,也就是元素个数

  1. private int size;  

 下面是几个构造函数:

 1.自定义初始化容量的构造函数:

  1. public ArrayList(int initialCapacity) {  

  2.       super();  

  3.        if (initialCapacity < 0)//初始化容量不能小于0,抛出IllegalArgumentException异常  

  4.            throw new IllegalArgumentException("Illegal Capacity: "+  

  5.                                               initialCapacity);  

  6.            this.elementData = new Object[initialCapacity];//根据参数初始化一个数组,底层是个object数组  

  7.    } 

 2.默认构造函数:  调用上面的构造函数,默认初始化内部数组大小为10

  1. public ArrayList() {  

  2.     s(10);//默认初始容量是10  

  3. }  

  3.collection转换的构造函数:

  1.   public ArrayList(Collection<? extends E> c) {  

  2.       elementData = c.toArray();//调用toArray()方法把collection转换成数组  

  3.       size = elementData.length;//把数组的长度赋值给ArrayList的size属性  

  4.       // c.toArray might (incorrectly) not return Object[] (see 6260652)  

  5.      if (elementData.getClass() != Object[].class)  

  6.         elementData = Arrays.copyOf(elementData, size, Object[].class);  

  7.      }

  8. }  

 返回ArrayList的大小:

  1. public int size() {  

  2.    return size;  

  3. }

 判断是否为空:

  1. public boolean isEmpty() {  

  2.    return size == 0;//就是看当前size是否为0  

  3. }

找出一个元素第一次出现的下标:

  1.    public int indexOf(Object o) {  

  2.     //由于数组的下标是从0开始的,所以判断是否存在只要大于0就可以了  

  3.    if (o == null) {  

  4.      for (int i = 0; i < size; i++)//注意这里是size属性而不是elementData的length  

  5.        if (elementData[i]==null)  

  6.         return i;  

  7.    } else {  

  8.     for (int i = 0; i < size; i++)  

  9.      if (o.equals(elementData[i]))//equals方法来判断  

  10.         return i;  

  11.    }  

  12.      return –1;//没有的话返回-1  

  13.    }

判断是否包含一个元素:

  1. public boolean contains(Object o) {  

  2.    return indexOf(o) >= 0;//不存在是-1  

元素最后一次出现的下标:

  1.  public int lastIndexOf(Object o) {  

  2.  if (o == null) {  

  3.     for (int i = size-1; i >= 0; i–)//注意这里的i是等于数组长度减1,从数组的最后一位开始  

  4.     if (elementData[i]==null)  

  5.         return i;  

  6.  } else {  

  7.     for (int i = size-1; i >= 0; i–)  

  8.     if (o.equals(elementData[i]))  

  9.         return i;  

  10.  }  

  11.    return –1;  

  12.    } 

  重新分配ArrayList空间为元素多少的真实大小:

  注意size一般和内部结构的数组长度是不一样的,通过上面的构造函数我们知道内部数组初始化容量是10,

  而size是在add()方法后才加一,这个方法是保证列表的大小和内部数组的大小一致

  1.  public void trimToSize() {  

  2.      modCount++;  

  3.     int oldCapacity = elementData.length;  

  4.    if (size < oldCapacity) {  

  5.            elementData = Arrays.copyOf(elementData, size);  

  6.     }  

  7.  }  

如有必要,增加此ArrayList实例的容量,以确保它至少能够容纳最小容量参数所指定的元素数,因为每次重新分配空间都是比较消耗时间的,所以如果能预计list可能的大小的话可以通过自己的控制ArrayList

的大小来提高效率.

  1.  public void ensureCapacity(int minCapacity) {//注意是public类型,也就是说可以我门自己来重新分配空间  

  2.        modCount++;   

  3.       int oldCapacity = elementData.length;//老的容量   

  4.       if (minCapacity > oldCapacity) {   

  5.         Object oldData[] = elementData;//把当前数组临时保存起来   

  6.         int newCapacity = (oldCapacity * 3)/2 + 1;//加1是为了保证oldCapacity为1或者0的情况下   

  7.         if (newCapacity < minCapacity)//是按1.5被来增加容量的   

  8.          newCapacity = minCapacity;   

  9.            // minCapacity is usually close to size, so this is a win:   

  10.            elementData = Arrays.copyOf(elementData, newCapacity);   

  11.       }   

  12.  }  

clone一个副本:

  1. public Object clone() {  

  2.    try {  

  3.        ArrayList<E> v = (ArrayList<E>) super.clone();  

  4.        v.elementData = Arrays.copyOf(elementData, size);  

  5.        v.modCount = 0;  

  6.        return v;  

  7.    } catch (CloneNotSupportedException e) {  

  8.        // this shouldn't happen, since we are Cloneable  

  9.        throw new InternalError();  

  10.     }  

  11.   }  

 转换为数组:

  1. public Object[] toArray() {  

  2.     return Arrays.copyOf(elementData, size);//调用Arrays.copyOf()方法  

  3. }  

下面是转换为泛型数组:

  1. public <T> T[] toArray(T[] a) {  

  2.        if (a.length < size)  

  3.            // Make a new array of a's runtime type, but my contents:  

  4.            return (T[]) Arrays.copyOf(elementData, size, a.getClass());  

  5.            System.arraycopy(elementData, 0, a, 0, size);  

  6.        if (a.length > size)  

  7.            a[size] = null;  

  8.        return a;  

  9.    }  

范围检查:臭名昭著的 IndexOutOfBoundsException异常

  1. private void RangeCheck(int index) {  

  2.    (index >= size)//数组越界,这里没有判断小于0的情况  

  3.   throw new IndexOutOfBoundsException(index: "+index+", Size: "+size);  

通过下标得到一个元素:

  1. public E get(int index) {  

  2.    RangeCheck(index);//先检查是否越界

  3.    return (E) elementData[index];//返回的是数组中的下标    

  4. }  

 通过下标和一个元素赋值,返回的是原先的值:

  1.  public E set(int index, E element) {  

  2.     RangeCheck(index);//先检查是否越界

  3.     E oldValue = (E) elementData[index];//通过临时变量把当前下标的值保存  

  4.     elementData[index] = element;//赋值  

  5.     return oldValue;//注意返回的是当前下标的原先值  

  6.  }  

添加一个新的元素到末尾,前面说道新增方法都要先调用ensureCapacity方法:

  1.  public boolean add(E e) {  

  2.      ensureCapacity(size + 1); //大小加一 // Increments modCount!!  

  3.      elementData[size++] = e;//size默认是0所以是从0开始赋值  

  4.     return true;  

  5.  }  

 API文档中的说明是:将指定的元素插入此列表中的指定位置。向右移动当前位于该位置的元素(如果有)以及所有后续元素(将其索引加 1)。通俗的说法是在指定位置插入元素,指定元素和后面的元素后移

 这个方法和set(int index, E element) 不一样,set只是把元素赋值给指定的下标同时返回下标的原先值.

 add(int index, E element)的判断越界是通过元素的大小来判断的

所以如果

 

  1. ArrayList list=new ArrayList();  

  2. list.add(18);  

  3. //报错,因为size元素大小还是0  

  4. //如果l  

  5. list.add(0,"")//就可以  

   如果一致add同一下标所有后续元素索引加1

   如下: 

  1. ArrayList list=new ArrayList();  

  2. list.add(08);  

  3. list.add(08);  

  4. list.add(08);  

  5. System.out.println(list);  

  6. //结果为[8, 8, 8]  

  1. public void add(int index, E element) {  

  2. if (index > size || index < 0)//判断是否越界,注意这里是以元素的个数来判断的  

  3.     throw new IndexOutOfBoundsException(  

  4.     "Index: "+index+", Size: "+size);  

  5.   

  6.     ensureCapacity(size+1);  // Increments modCount!!  

  7.     System.arraycopy(elementData, index, elementData, index + 1,  

  8.          size – index);  

  9.    //源数组中位置在 srcPos 到 srcPos+length-1 之间的组件被分别复制到  

  10.    //目标数组中的 destPos 到 destPos+length-1 位置  

  11.    elementData[index] = element;  

  12.     size++;//元素加一  

  13.  }  

删除指定位置的元素,返回被删除的元素,由于ArrayList采用一个对象数组存储元素,所以在删除一个元素时需要把后面的元素前移。删除一个元素时只是把该元素在elementData数组中的引用置为null,具体的对象的销毁由垃圾收集器负责:

  1.  public E remove(int index) {  

  2.     RangeCheck(index);//判断是否越界  

  3.     modCount++;  

  4.     E oldValue = (E) elementData[index];  

  5.   

  6.     int numMoved = size – index – 1;//新的数组长度  

  7.     if (numMoved > 0)  

  8.        System.arraycopy(elementData, index+1, elementData, index, numMoved);  

  9.       elementData[–size] = null// Let gc do its work  

  10.     return oldValue;//返回删除前的数据  

  11.  }  

 内部删除方法,跳过越界检查,不返回删除元素的值:ArrayList内部调用的删除方法

  1. /* 

  2.   * Private remove method that skips bounds checking and does not 

  3.   * return the value removed. 

  4.   */  

  5.  private void fastRemove(int index) {  

  6.      modCount++;  

  7.      int numMoved = size – index – 1;  

  8.      if (numMoved > 0)  

  9.          System.arraycopy(elementData, index+1, elementData, index, numMoved);  

  10.         elementData[–size] = null// Let gc do its work  

  11.  }  

 删除指定元素:

  1.  public boolean remove(Object o) {  

  2. if (o == null) {  

  3.            for (int index = 0; index < size; index++)  

  4.     if (elementData[index] == null) {  

  5.         fastRemove(index);  

  6.         return true;  

  7.     }  

  8. else {  

  9.     for (int index = 0; index < size; index++)  

  10.     if (o.equals(elementData[index])) {  

  11.         fastRemove(index);  

  12.         return true;  

  13.     }  

  14.        }  

  15. return false;  

  16.    }  

 清空列表:

  1.  public void clear() {  

  2. modCount++;  

  3.   

  4. // Let gc do its work  

  5. for (int i = 0; i < size; i++)  

  6.     elementData[i] = null;  

  7.   

  8. size = 0;//设定元素大小为0  

  9.    }  

添加集合c中的元素到ArrayList的末尾,添加成功返回true,如果集合c为空,返回false。

  1.   public boolean addAll(Collection<? extends E> c) {  

  2.         Object[] a = c.toArray();  

  3.        int numNew = a.length;  

  4.        ensureCapacity(size + numNew);  // Increments modCount  

  5.        System.arraycopy(a, 0, elementData, size, numNew);//添加到列表的末尾  

  6.        size += numNew;  

  7.       return numNew != 0;  

  8.  }

在指定位置插入集合中的所有元素,和上面一个方法基本差不多,指定位置元素和以后的都要后移:

  1.  public boolean addAll(int index, Collection<? extends E> c) {  

  2.   if (index > size || index < 0)//判断越界   

  3.     throw new IndexOutOfBoundsException(  

  4.     "Index: " + index + ", Size: " + size);  

  5.   

  6.    Object[] a = c.toArray();  

  7.    int numNew = a.length;  

  8.    ensureCapacity(size + numNew);  // Increments modCount  

  9.    int numMoved = size – index;  

  10.   if (numMoved > 0)//两种情况  

  11.        System.arraycopy(elementData, index, elementData, index + numNew,  

  12.              numMoved);  

  13.   

  14.        System.arraycopy(a, 0, elementData, index, numNew);//这里是等于0的情况也就是说直接在数组后面加  

  15.       size += numNew;  

  16.       return numNew != 0;  

  17.  }  

删除指定范围的元素

  1. protected void removeRange(int fromIndex, int toIndex) {   

  2.        modCount++;   

  3.        int numMoved = size – toIndex;   

  4.        System.arraycopy(elementData, toIndex, elementData, fromIndex,   

  5.                         numMoved);   

  6.   

  7. // Let gc do its work   

  8.    int newSize = size – (toIndex-fromIndex);   

  9.    while (size != newSize)   

  10.        elementData[–size] = null;   

  11.    }  

 结合API文档和网上搜索来的ArrayList的特效来总结下:

 API文档是如此介绍ArrayList的:

    接口的大小可变数组的实现。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List 接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。(此类大致上等同于 Vector 类,除了此类是不同步的。)

 Vector由于使用了synchronized方法(线程安全)所以性能上比ArrayList要差。

 

List允许有相同的元素

  ArrayList的方法都没有同步,所以在多线程中是不安全的,必须自己同步

  toArray()方法返回的是和原列表相同的对象,也就是说:
  arrayList.toArray()[0]==arrayList.get(0)返回的是true(假定arrayList不空)。

  clone()方法是一个浅拷贝。

API文档:

  在添加大量元素前,应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量
  可以通过自己调用ensureCapacity()提高效率

  创建同步线程的ArrayList

  List list = Collections.synchronizedList(new ArrayList(…));

  ArrayList提供了4种添加方法:list.add(e);  

  1. list.add(index, element);  

  2. list.addAll(c);  

  3. list.addAll(index, c);  

每次添加都调用ensureCapacity()方法,扩大容量是每次是1.5倍:

  1. list.set(index, element);  

  2. list.add(index, element);  

 set是用指定的元素替代此列表中指定位置上的元素

 add是将指定的元素插入此列表中的指定位置。向右移动当前位于该位置的元素

 对于新增和删除操作add和remove,ArrayList要移动数据。所以性能不是很好

 而访问数据是直接根据数组下标来获得数据的,所以速度很快

移除ArrayList内重复数据:

  1. public static void removeDuplicate(List arlList) {  

  2.     HashSet h = new HashSet(arlList);  

  3.     arlList.clear();  

  4.     arlList.addAll(h);  

  5. }  

  1. 除了具有Collection接口必备的iterator()方法外,List还提供一个listIterator()方法,返回一个 ListIterator接口,和标准的Iterator接口相比,ListIterator多了一些add()之类的方法,允许添加,删除,设定元素,还能向前或向后遍历。  

     

  2.  简单的自定义ArrayList,用于理解ArrayList内部构造原理:

  3. /** 
     * 自定义ArrayList 
     * @author as-us 
     * 
     */  
    public class CustomArrayList {  
          
        private Object[] elementData;  
          
        private int size;  
      
        public CustomArrayList(int initialCapacity) {  
            if(initialCapacity<0){  
                try {  
                    throw new Exception();  
                } catch (Exception e) {  
                    e.printStackTrace();  
                }  
            }  
            elementData=new Object[initialCapacity];  
        }  
      
        public CustomArrayList() {  
            this(10);  
        }  
          
        /** 
         * 添加元素 
         * @param obj 
         */  
        public void add(Object obj){  
            /* 
             * 首先判断是否需要扩容 
             */  
            ensureCapacity();  
              
            elementData[size++]=obj;  
        }  
          
          
        /** 
         * 添加元素 
         * @param obj 
         */  
        public void add(int index,Object obj){  
            checkRange(index);//检查是否越界  
            /* 
             * 首先判断是否需要扩容 
             */  
            ensureCapacity();  
            //add 3-6  [1, 2, 3, 4, 5] ---> [1, 2, 3,6, 4, 5]   
            //System.arraycopy(elementData, index, elementData, index+1, size-index);  
            System.arraycopy(elementData, index, elementData, index + 1, size - index);  
            elementData[index] = obj;  
            size++;  
        }  
          
          
          
        /** 
         * 根据索引位置移除对象 
         * @param index 
         */  
        public void remove(int index){  
              
            //移除  [1, 2, 3, 4, 5] remove--> 3  
            int numMoved=size-index-1;  
            if(numMoved>0){  
                System.arraycopy(elementData, index+1, elementData, index, numMoved);  
            }  
            elementData[size--]=null;  
        }  
          
        public void remove(Object object){  
            if(object==null){  
                for (int i = 0; i < elementData.length; i++) {  
                    if(get(i)==null){  
                        remove(i);  
                    }  
                }  
            }else{  
                for (int i = 0; i < size; i++) {  
                    if(get(i).equals(object)){  
                        remove(i);  
                    }  
                }  
            }  
        }  
          
        public Object get(int index){  
            checkRange(index);  
            return elementData[index];  
        }  
          
        public Object set(int index,Object object){  
            checkRange(index);  
            Object oldValue =  elementData[index];  
            oldValue=object;  
            elementData[index]=object;  
            return oldValue;  
        }  
          
        public int size(){  
            return size;  
        }  
          
        private void checkRange(int index){  
            if(index>=size || index<0){  
                try {  
                    throw new Exception("数组越界");  
                } catch (Exception e) {  
                    e.printStackTrace();  
                }  
            }  
        }  
          
        private void ensureCapacity(){  
            //数据扩容;  
            if(elementData.length==size){  
                Object [] newArray=new Object[size*2+1]; //原来的2倍  
                /** 
                 * src:源数据;srcPos:源数组要复制的起始位置;dest:目的数组;destPos:目的数组放置的起始位置;length:复制的长度 
                 */  
                //System.arraycopy(src, srcPos, dest, destPos, length);  
                System.arraycopy(elementData, 0, newArray, 0, elementData.length);  
                elementData = newArray;  
            }  
        }  
          
          
          
        public static void main(String[] args) {  
            // 初始化    
            int[] ids = { 1, 2, 3, 4, 5 };    
            System.out.println(Arrays.toString(ids)); // [1, 2, 3, 4, 5]    
            // 将数据的索引1开始的3个数据复制到目标的索引为0的位置上    
            int[] ids2 = new int[6];    
            System.arraycopy(ids, 1, ids2, 0, 3);    
            System.out.println(Arrays.toString(ids2)); // [2, 3, 4, 0, 0, 0]  
              
              
            CustomArrayList list=new CustomArrayList();  
              
            list.add("333");  
            list.add("444");  
            list.add("5");  
            list.add("344433");  
            list.add("333w");  
            list.add("333wertrwe");  
            System.out.println(list.get(5));  
            list.remove("444");  
            System.out.println(list.size());  
            list.add("dededddddddddd");  
            System.out.println(list.size());  
        }  
          
      
    }

 个人CSDN-ArrayList原理分析

发表评论