Java collection ArrayList sample code analysis

ArrayList Introduction: ArrayList is an array queue, which is equivalent to a dynamic array, and the capacity can grow dynamically; it inherits AbstractList and implements List, RandomAccess , Cloneable, Serializable interfaces.

Features:

(1) ArrayList inherits AbstractList and implements List. It is an array queue and provides related functions such as adding, deleting, modifying, and traversing.

(2) ArrayList implements the RandomAccess interface and provides a random access function. RandomAccess is implemented by List in Java and provides a fast access function for the List; fast random access can also be performed through element subscripts.

(3) ArrayList implements the Cloneable interface, covers the function clone(), and can be cloned.

(4) ArrayList implements the Serializable interface and can be serialized and transmitted through the network.

(5) ArrayList is not thread-safe and is recommended to be used in a single thread.

(6) ArrayList uses elementData an Object[] array to dynamically store data.

(7) The initial size of the object array is 10, and the array size adjustment method is newCapacity = oldCapacity + (oldCapacity >> 1);

ArrayList supports three traversal methods:

(1) Traverse through iterator, that is, traverse through Itreator

Integer value=Iterator iter=list.iterator()(iter.hasNext())
{
    value=(Interger)iter.next()}

(2) Random access mode, traverse all elements through index values ​​

Interger value=size=list.size()fo(i=i
 (3) for loop traversal  
Integer value=(Integer inte : list)
{
    value=inte}
 Among the three traversal methods, traversing through index is the fastest, and traversing through iterator is the slowest. 
Sample program: 
public class Hello {

    public static void main(String[] args) {

        ArrayList list = new ArrayList();
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        list.add(0, "5");
        System.out.println("the first element is: "+ list.get(0));
        list.remove("3");
        System.out.println("Arraylist size=: "+ list.size());
        System.out.println("ArrayList contains 3 is: "+ list.contains(3));
        list.set(1, "10");
        for(Iterator iter = list.iterator(); iter.hasNext(); )
        {
            System.out.println("next is: "+ iter.next());
        }
        String[] arr = (String[])list.toArray(new String[0]);
        for (String str:arr)
            System.out.println("str: "+ str);
        list.clear();
        System.out.println("ArrayList is empty: "+ list.isEmpty());
    }
}
 Running results: 
the first element is: 5
Arraylist size=: 4
ArrayList contains 3 is: false
next is: 5
next is: 10
next is: 2
next is: 4
str: 5
str: 10
str: 2
str: 4
ArrayList is empty: true
ArrayList source code analysis: 
// Arraylist inherits AbstractList and implements List, RandomAccess, and Cloneable , Serializable interface 
public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;  //序列化ID
    private static final int DEFAULT_CAPACITY = 10; //初始大小为10，会动态增加
    private static final Object[] EMPTY_ELEMENTDATA = {};//空的数组实例
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    transient Object[] elementData; // ArrayList用来存储对象的数组
    private int size;//数组中包含对象的个数
    //ArrayList构造函数，构造初始大小的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);
        }
    }
    //构造函数，初始化大小为10的数组
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    //带有Collection的构造函数
    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;
        }
    }
    //当前容量值设置为实际个数
    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
                    ? EMPTY_ELEMENTDATA
                    : Arrays.copyOf(elementData, size);
        }
    }
    //判断容量，容量不够增加
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                // any size if not default element table
                ? 0
                // larger than default for default empty table. It's already
                // supposed to be at default size.
                : 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 static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    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 int size() {
        return size;
    }
    //判断ArrayList是否为空
    public boolean isEmpty() {
        return size == 0;
    }
    //判断是否含有某个对象
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }
    //查找对象，返回坐标
    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
    //返回对象相同的最后一个坐标
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
    //返回一个影子对象克隆
    public Object clone() {
        try {
            ArrayList v = (ArrayList) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }
    //返回一个包含所有ArrayList元素的数组
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
    //返回泛型对象数组，一般使用这个不是上边那个
    @SuppressWarnings("unchecked")
    public  T[] toArray(T[] a) {
        if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }
    //得到指定下标的对象
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }
    //得到指定下标的对象，并对下标进行判断
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }
    //替换指定下标的对象，会检查下标并返回
    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
    //追加对象
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    //在指定的下标后增加对象
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                size - index);
        elementData[index] = element;
        size++;
    }
    //删除指定坐标的对象
    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;
    }
    // 删除ArrayList第一次出现的对象o
    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
    }
    //清空ArrayList
    public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }
    //将集合C追加到ArrayList中
    public boolean addAll(Collection c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
    //在ArrayList中的某个坐标后追加集合c
    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;
    }
    //删除范围中的对象
    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                numMoved);

        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }
    //范围检查
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    //在添加或者添加所有的时候范围检查
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }
    public boolean removeAll(Collection c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }
    public boolean retainAll(Collection c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }
    //删除c中的在ArrayList中存在或者不存在的
    private boolean batchRemove(Collection c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                        elementData, w,
                        size - r);
                w += size - r;
            }
            if (w != size) {
            // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }
    //序列化
    private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (int i=0; i
 Related articles: 

 Detailed introduction to using C# to describe data structure 3: ArrayList graphic code
js implements ArrayList function with example code
PHP method to implement C# copycat ArrayList
The above is the detailed content of Java collection ArrayList sample code analysis. For more information, please follow other related articles on the PHP Chinese website!