java集合数据比较 java集合-数组ArrayList

1、简介ArrayList是java集合框架常用的集合类之一，底层是基于数组来实现容量大小动态变化的。
2、类图（JDK 1.8）下图是ArrayList实现的接口和继承的类关系图：

文章插图
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable1、实现了四个接口
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+1elementData[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 =https://tazarkount.com/read/= 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_SIZEelementData = Arrays.copyOf(elementData, newCapacity);//复制当前数组到一个新数组（长度为newCapacity），并返回}//判断 最小容量大于MAX_ARRAY_SIZE返回Integer.MAX_VALUE 否则返回 MAX_ARRAY_SIZEprivate static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow 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++;//数组修改+1E oldValue = https://tazarkount.com/read/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 workreturn 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倍的容量去扩容【java集合数据比较 java集合-数组ArrayList】2.1、非线程安全。解释一下什么是线程安全：
2.2、当多个线程访问某个类,不管运行时环境采用何种调度方式或者这些线程如何交替执行,并且在主调代码中不需要任何额外的同步或协同,这个类都能表现出正确的行为,那么就称这个类为线程安全的。
----《并发编程实战》
多线程并发访问时，得不到正确的结果。
3、适用于查询多的场景，对元素进行频繁的移动或删除场景比较适用LinkedList这种数据结构人生很多烦恼，是因为想得太多，做得太少