Java容器ArrayList知识点总结

ArrayList

底层实现是数组，访问元素效率高 (查询快，插入、修改、删除元素慢)

与LinkedList相比，它效率高，但线程不安全。

ArrayList数组是一个可变数组，可以存取包括null在内的所有元素

• 每个ArrayList实例都有一个容量，该容量是指用来存储列表元素的数组的大小
• 随着向ArrayList中不断增加元素，其容量自动增长
• 在添加大量元素前，应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量，这样可以减少递增式再分配的数量。
• 所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多进行扩容操作而浪费时间、效率
• 源码分析
  

底层使用数组实现

transient Object[] elementData;

构造方法

private static final int DEFAULT_CAPACITY = 10;private static final Object[] EMPTY_ELEMENTDATA = {};private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};transient Object[] elementData;private int size; // 构造一个空列表public ArrayList() {    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA ;  } // 构造一个指定初始容量的空列表public ArrayList(int initialCapacity) {    if (initialCapacity > 0) {      this.elementData = new Object[initialCapacity];    } else if (initialCapacity == 0) {      this.elementData = EMPTY_ELEMENTDATA;    } else {      throw new IllegalArgumentException("Illegal Capacity: "+                        initialCapacity);    }  }  // 构造一个指定Collection元素的列表，这些元素按照Connection元素的迭代返回顺序进行排列public ArrayList(Collection<? extends E> c) {    elementData = c.toArray();    if ((size = elementData.length) != 0) {      // c.toArray might (incorrectly) not return Object[] (see 6260652)      if (elementData.getClass() != Object[].class)        elementData = Arrays.copyOf(elementData, size, Object[].class);    } else {      // replace with empty array.      this.elementData = EMPTY_ELEMENTDATA;    }  } 

存储

// 在列表的指定位置的元素用element替代，并且返回该位置原来的元素public E set(int index, E element) {    rangeCheck(index); // 检查数组容量，抛出：IndexOutOfBoundsException     E oldValue = elementData(index);    elementData[index] = element;    return oldValue;  } // 在列表的尾部添加指定元素public boolean add(E e) {    ensureCapacityInternal(size + 1); // 数组扩容    elementData[size++] = e;    return true;  } // 在列表的指定位置添加元素public void add(int index, E element) {    rangeCheckForAdd(index);     ensureCapacityInternal(size + 1); // Increments modCount!!     // src:源数组,srcPro:源数组中的起始位置    // dest:目标数组，destPost:目标数组的起始位置，length:要复制的数组元素数量       // 将当前位于该位置的元素以及所有后续元素后移一个位置    System.arraycopy(elementData, index, elementData, index + 1,             size - index);    // 用element替换index位置的元素    elementData[index] = element;    size++;  } // 在列表的尾部添加Connection中的元素，元素顺序按照Connection迭代器返回的顺序public boolean addAll(Collection<? extends E> c) {    Object[] a = c.toArray(); // 转化为一个数组     int numNew = a.length;    ensureCapacityInternal(size + numNew); // Increments modCount     // Increments modCount!!    System.arraycopy(a, 0, elementData, size, numNew);    size += numNew;    return numNew != 0;  } // 在列表的指定位置添加Connection中的元素，元素顺序按照Connection迭代器返回的顺序public boolean addAll(int index, Collection<? extends E> c) {    rangeCheckForAdd(index);     Object[] a = c.toArray();    int numNew = a.length;    ensureCapacityInternal(size + numNew); // Increments modCount     int numMoved = size - index;    if (numMoved > 0)      System.arraycopy(elementData, index, elementData, index + numNew,               numMoved);     System.arraycopy(a, 0, elementData, index, numNew);    size += numNew;    return numNew != 0;  } 

读取

// 移除此列表指定位置上的元素public E remove(int index) {    rangeCheck(index);     modCount++;    E oldValue = elementData(index);     int numMoved = size - index - 1;    if (numMoved > 0)      System.arraycopy(elementData, index+1, elementData, index,               numMoved);    elementData[--size] = null; // clear to let GC do its work     return oldValue;  } // 移除此列表中的某个元素public boolean remove(Object o) {    if (o == null) {      for (int index = 0; index < size; index++)        if (elementData[index] == null) {          fastRemove(index);          return true;        }    } else {      for (int index = 0; index < size; index++)        if (o.equals(elementData[index])) {          fastRemove(index);          return true;        }    }    return false;  } private void fastRemove(int index) {    modCount++;    int numMoved = size - index - 1;    if (numMoved > 0)      System.arraycopy(elementData, index+1, elementData, index,               numMoved);    elementData[--size] = null; // clear to let GC do its work  } 

数组扩容

每当向数组中添加元素时，都需要去检查添加元素后元素的个数是否超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。

public void ensureCapacity(int minCapacity) {    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA )         ? 0 : DEFAULT_CAPACITY;     if (minCapacity > minExpand) {      ensureExplicitCapacity(minCapacity);    }  } private void ensureCapacityInternal(int minCapacity) {    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA ) {      minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);    }     ensureExplicitCapacity(minCapacity);  } private void ensureExplicitCapacity(int minCapacity) {    modCount++;     // overflow-conscious code    if (minCapacity - elementData.length > 0)      grow(minCapacity);  } private void grow(int minCapacity) {    // overflow-conscious code    int oldCapacity = elementData.length;    int newCapacity = oldCapacity + (oldCapacity >> 1);    if (newCapacity - minCapacity < 0)      newCapacity = minCapacity;    if (newCapacity - MAX_ARRAY_SIZE > 0)      newCapacity = hugeCapacity(minCapacity);    // minCapacity is usually close to size, so this is a win:    elementData = Arrays.copyOf(elementData, newCapacity);  } private static int hugeCapacity(int minCapacity) {    if (minCapacity < 0) // overflow      throw new OutOfMemoryError();    return (minCapacity > MAX_ARRAY_SIZE) ?      Integer.MAX_VALUE :      MAX_ARRAY_SIZE;  } 

手写ArrayList

public class MyArrayList /*implements List<E>*/{ private transient Object[] elementData; private int size; //元素个数  public MyArrayList(){  this(10); }  public MyArrayList(int initialCapacity) {  if (initialCapacity<0) {   try {    throw new Exception();   } catch (Exception e) {    e.printStackTrace();   }  }  elementData = new Object[initialCapacity]; }  public int size() {  return size; }  public boolean isEmpty(){  return size == 0; } //根据index删掉对象 public void remove(int index) throws Exception {  rangeCheck(index);  int numMoved = size-index-1;  if (numMoved > 0) {   System.arraycopy(elementData, index+1, elementData, index, numMoved);  }  elementData[--size] = null; } //删掉对象 public boolean remove(Object obj) throws Exception {  for (int i = 0; i < size; i++) {   if (get(i).equals(obj)) {    remove(i);   }   return true;  }  return true; } //修改元素 public Object set(int index , Object obj ) throws Exception{  rangeCheck(index);  Object oldValue = elementData[index];  elementData[index] = obj;  return oldValue; } //在指定位置插入元素 public void add(int index,Object obj) throws Exception {  rangeCheck(index);  ensureCapacity();  System.arraycopy(elementData, index, elementData, index+1, size-index);  elementData[index] = obj;  size ++; } public void add(Object object) {  ensureCapacity();  /*elementData[size] = object;  size ++;*/  elementData[size++] = object; //先赋值，后自增 }  public Object get(int index) throws Exception {  rangeCheck(index);  return elementData[index]; } public void rangeCheck(int index) throws Exception {  if (index<0 || index >=size) {   throw new Exception();  } } //扩容 public void ensureCapacity() {  //数组扩容和内容拷贝  if (size==elementData.length) {   //elementData = new Object[size*2+1]; 这么写原来数组里的内容丢失   Object[] newArray = new Object[size*2+1];   //拷贝数组里的内容   /*for (int i = 0; i < newArray.length; i++) {    newArray[i] = elementData[i];   }*/   System.arraycopy(elementData, 0, newArray, 0, elementData.length);   elementData = newArray;  } } // 测试 public static void main(String[] args) {  MyArrayList myArrayList = new MyArrayList(3);  myArrayList.add("111");  myArrayList.add("222");  myArrayList.add("333");  myArrayList.add("444");  myArrayList.add("555");    try {   myArrayList.remove(2);   myArrayList.add(3, "新值");   myArrayList.set(1, "修改");  } catch (Exception e1) {   // TODO Auto-generated catch block   e1.printStackTrace();  }  System.out.println(myArrayList.size());  for (int i = 0; i < myArrayList.size(); i++) {   try {    System.out.println(myArrayList.get(i));   } catch (Exception e) {    e.printStackTrace();   }  } }}