java集合-数组ArrayList

1、简介

ArrayList是java集合框架常用的集合类之一，底层是基于数组来实现容量大小动态变化的。

2、类图（JDK 1.8）

下图是ArrayList实现的接口和继承的类关系图：

public class ArrayList<E> extends AbstractList<E>

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

1、实现了四个接口

1.1. java.util.List 接口，提供数组的添加、删除、修改、迭代遍历等操作。

1.2. java.util.RandomAccess 接口，表示 ArrayList 支持快速的随机访问。（RandomAccess 是 List 实现所使用的标记接口，用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。）

1.3. java.io.Serializable 接口，表示 ArrayList 支持序列化的功能。

1.4. java.lang.Cloneable 接口，表示 ArrayList 支持克隆。

2、继承了AbstractList抽象类

2.1AbstractList抽象类就是List分支的顶层超类。此类提供了List接口的骨干实现，以最大限度地减少实现由“随机访问”数据存储（例如数组、链表）支持的此接口所需的工作量

三、常用方法

添加元素 add()

    /**

     * Appends the specified element to the end of this list.

     * 添加单个元素方法

     * @param e element to be appended to this list

     * @return <tt>true</tt> (as specified by {@link Collection#add})

     */

    public boolean add(E e) {

        //判断如果容量不够，进行扩容

        ensureCapacityInternal(size + 1);  // Increments modCount!!

        //设置到数组末尾，然后在size+1

        elementData[size++] = e;

        return true;

    }

	//保证数组大小是否足够，不足则1.5倍扩容

    private void ensureCapacityInternal(int minCapacity) {

        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

    }

	//计算数组，最小需要的长度

    private static int calculateCapacity(Object[] elementData, int minCapacity) {

        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

            //new ArrayList()初始化的时候 elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA

            //在添加的时候在初始化长度为10的数组

            return Math.max(DEFAULT_CAPACITY, minCapacity);

        }

        return minCapacity;

    }

	private void ensureExplicitCapacity(int minCapacity) {

        modCount++;

        // overflow-conscious code

        //判断数组容量是否足够，不足进行扩容

        if (minCapacity - elementData.length > 0)

            grow(minCapacity);//数组扩容

    }

	    /**

     * Increases the capacity to ensure that it can hold at least the

     * number of elements specified by the minimum capacity argument.

     * 数组扩容，增加容量以确保它至少可以容纳最小容量参数指定的元素数

     * @param minCapacity the desired minimum capacity

     */

    private void grow(int minCapacity) {

        int oldCapacity = elementData.length;

        int newCapacity = oldCapacity + (oldCapacity >> 1);//新数组长度是旧数组的1.5倍

        if (newCapacity - minCapacity < 0)//判断新数组需要的长度，是否比需要数组需要的最小容量小

            newCapacity = minCapacity;

        if (newCapacity - MAX_ARRAY_SIZE > 0)//判断新数组长度是否大于MAX_ARRAY_SIZE【2147483647-8】

            newCapacity = hugeCapacity(minCapacity);//判断 最小容量大于MAX_ARRAY_SIZE返回Integer.MAX_VALUE 否则返回 MAX_ARRAY_SIZE

        elementData = Arrays.copyOf(elementData, newCapacity);//复制当前数组到一个新数组（长度为newCapacity），并返回

    }

    //判断 最小容量大于MAX_ARRAY_SIZE返回Integer.MAX_VALUE 否则返回 MAX_ARRAY_SIZE

    private static int hugeCapacity(int minCapacity) {

        if (minCapacity < 0) // overflow

            throw new OutOfMemoryError();

        return (minCapacity > MAX_ARRAY_SIZE) ?

            Integer.MAX_VALUE :

            MAX_ARRAY_SIZE;

    }

流程图：

get方法 get()

根据下标获取元素

    public E get(int index) {

        rangeCheck(index);//判断当前下标是否数组越界，越界抛出IndexOutOfBoundsException异常

        //根据数组下标获取元素

        return elementData(index);

    }

    //判断当前下标是否数组越界，越界抛出IndexOutOfBoundsException异常

    private void rangeCheck(int index) {

        if (index >= size)

            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    }

    //根据数组下标获取元素

    @SuppressWarnings("unchecked")

    E elementData(int index) {

        return (E) elementData[index];

    }

删除元素 remove()

1、public E remove(int index)

删除列表中指定位置的元素。将任何后续元素向左移动

    //根据下标删除数组元素，下标右边元素向左移

    public E remove(int index) {

        rangeCheck(index);//判断当前下标是否数组越界，越界抛出IndexOutOfBoundsException异常

        modCount++;//数组修改+1

        E oldValue = elementData(index);//根据下标获取数组元素

        int numMoved = size - index - 1;//元素向左移动的长度

        if (numMoved > 0)

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

                             numMoved);//当前下标-后续元素向左移动

        //先size-1设置null删除元素，方便gc回收

        elementData[--size] = null; // clear to let GC do its work

        return oldValue;//返回旧的值

    }

2、public boolean remove(Object o)

删除数组的第一个匹配元素，

    //删除数组的第一个匹配的元素

    public boolean remove(Object o) {

        if (o == null) {

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

                if (elementData[index] == null) {

                    fastRemove(index);//根据下标删除元素，逻辑同remove(int index)方法

                    return true;

                }

        } else {

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

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

                    fastRemove(index);//根据下标删除元素，逻辑同remove(int index)方法

                    return true;

                }

        }

        return false;

    }

获取元素下标 indexOf()

    //取得当前元素下标，查找不到返回-1  代码逻辑跟 remove(Object o) 类似

    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;

    }

时间复杂度

add(E e)方法添加元素到末尾

时间复杂度为O(1)。

add(int index, E element)方法添加元素到指定位置

时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。

最好时间复杂度是 O(1) ，最坏时间复杂度是 O(n) ，平均时间复杂度是 O(n) 。

最好时间复杂度发生在末尾添加的情况。

get(int index)方法获取指定索引位置的元素

数组在内存中是连续的地址空间，可以直接通过下标去数组查找元素，时间复杂度为O(1)。

remove(int index)方法删除指定索引位置的元素

最好时间复杂度是 O(1) ，最坏时间复杂度是 O(n) ，平均时间复杂度是 O(n) 。

remove(Object o)方法删除指定元素值的元素

由于要先找到元素 O(n)，然后在通过下标删除元素 O(n)，时间复杂度为O(n)。

小结

1、存储一组不唯一（可以有多个元素引用相同的对象），有序的对象，按照插入顺序的保证有序，元素可以重复，支持null元素

2、按照1.5倍的容量去扩容

2.1、非线程安全。解释一下什么是线程安全：

2.2、当多个线程访问某个类,不管运行时环境采用何种调度方式或者这些线程如何交替执行,并且在主调代码中不需要任何额外的同步或协同,这个类都能表现出正确的行为,那么就称这个类为线程安全的。

----《并发编程实战》

多线程并发访问时，得不到正确的结果。

巴特西

java集合-数组ArrayList

1、简介

2、类图（JDK 1.8）

三、常用方法

添加元素 add()

get方法 get()

删除元素 remove()

获取元素下标 indexOf()

时间复杂度

add(E e)方法添加元素到末尾

add(int index, E element)方法添加元素到指定位置

get(int index)方法获取指定索引位置的元素

remove(int index)方法删除指定索引位置的元素

remove(Object o)方法删除指定元素值的元素

小结

1、存储一组不唯一（可以有多个元素引用相同的对象），有序的对象，按照插入顺序的保证有序，元素可以重复，支持null元素

2、按照1.5倍的容量去扩容

3、适用于查询多的场景，对元素进行频繁的移动或删除场景比较适用LinkedList这种数据结构

最新文章

热门文章

巴特西

java集合-数组ArrayList

1、简介

2、类图（JDK 1.8）

三、常用方法

添加元素 add()

get方法 get()

删除元素 remove()

获取元素下标 indexOf()

时间复杂度

add(E e)方法 添加元素到末尾

add(int index, E element)方法 添加元素到指定位置

get(int index)方法 获取指定索引位置的元素

remove(int index)方法 删除指定索引位置的元素

remove(Object o)方法 删除指定元素值的元素

小结

1、存储一组不唯一（可以有多个元素引用相同的对象），有序的对象，按照插入顺序的保证有序，元素可以重复，支持null元素

2、按照1.5倍的容量去扩容

3、适用于查询多的场景，对元素进行频繁的移动或删除场景比较适用LinkedList这种数据结构

最新文章

热门文章

add(E e)方法添加元素到末尾

add(int index, E element)方法添加元素到指定位置

get(int index)方法获取指定索引位置的元素

remove(int index)方法删除指定索引位置的元素

remove(Object o)方法删除指定元素值的元素