Java知识点总结（Java容器-ArrayList）-白红宇

Java知识点总结（Java容器-ArrayList）

阅读量：7209 次

发布时间：2019-06-29

本文共 9049 字，大约阅读时间需要 30 分钟。

Java知识点总结（Java容器-ArrayList）

@(Java知识点总结)[Java, Java容器, JavaCollection, JavaList]

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
     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
     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
     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
    
     */{  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();      }    }  }}

转载地址：http://vygum.baihongyu.com/

你可能感兴趣的文章