ArrayList原理

视频地址

在本套课程中，我们将全面深度剖析ArrayList原理，包含底层数据结构、扩容机制、性能分析、底层源码解析、以及各种和ArrayList相关的面试题等。让我们不仅是学习ArrayList基本应用，而且通过底层原理分析让大家更深层次的理解ArrayList，甚至在某些性能方面会颠覆我们对于它的认知,同时在面试方面会给我们带来更大优势。

学习目标

ArrayList集合底层数据结构介绍
ArrayList继承关系
ArrayList源码分析
面试题讲解
自定义ArrayList

ArrayList集合底层数据结构介绍

ArrayList是由动态再分配的Object[]数组作为底层结构，可设置null值，是非线程安全的。

ArrayList集合介绍

List 接口的可调整大小的数组实现。

数组:一旦初始化长度就不可以发生改变。

数组结构介绍

增删慢：每次删除元素，都需要更改数组长度、拷贝以及移动元素位置。
查询快：由于数组在内存中是一块连续空间，因此可以根据地址+索引的方式快速获取对应位置上的元素。

ArrayList 继承关系

Serializable 标记接口

略。

Cloneable 标记接口

浅拷贝

基本数据类型可以完全复制，引用数据类型则不可以。

to add code

深拷贝

to add code

RandomAccess 标记接口

随机访问和顺序访问

顺序访问（通过迭代器）：链表在内存中不是按顺序存放的，而是通过指针连在一起，为了访问某一元素，必须从链头开始顺着指针才能找到某一个元素。

随机访问（通过索引）：数组在内存中是按顺序存放的，可以通过下标直接定位到某一个元素存放的位置。

鼓励通用列表算法在使用时，检查给定列表是否为 instanceof RandomList，若是，则使用如下方式遍历：

    for (int i = 0, n = list.size(); i < n; i++) {
        list.get(i);
    }

否则，使用迭代器方式遍历：

    for (Iterator i = list.iterator(); i.hasNext();) {
        i.next();
    }

AbstractList 抽象类

ArrayList源码分析

构造方法

ArrayList() 构造一个初始容量为十的空列表。
ArrayList(int initialCapacity) 构造具有指定初始容量的空列表。
ArrayList(Collection<? extends E> c) 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。

注意点：

通过ArrayList()构造方法创建集合对象并未构造一个初始容量为十的空列表，仅仅将DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的地址赋值给elementData。
根据ArrayList(int initialCapacity)构造方法创建一个长度为initialCapacity的数组。
根据ArrayList(Collection<? extends E> c)构造方法创建指一个长度为c.size()的数组。

添加方法

public boolean add(E e) 将指定的元素追加到此列表的末尾。
public void add(int index, E element) 在此列表中的指定位置插入指定的元素。
public boolean addAll(Collection<? extends E> c) 按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾。
public boolean addAll(int index, Collection<? extends E> c) 将指定集合中的所有元素插入到此列表中，从指定的位置开始。

注意点：

添加方法（可能）会导致ArrayList底层数组扩容，扩容规律为从0到10、再每次变成1.5倍。
add(int index, E element)和addAll(int index, Collection<? extends E> c)会导致数组元素移动，移动的元素是从index开始到size-1，每个元素都往后移动1或c.size()个元素。

删除方法

public E remove(int index) 根据索引删除元素
public boolean remove(Object o) 根据元素删除元素

注意点：

remove(int index)会导致数组元素移动，移动的元素是从index+1开始到size-1，每个元素都往前移动1个元素。
删除方法不会导致ArrayList底层数组扩容。

修改方法

public E set(int index, E element) 根据索引修改集合元素

注意点：

set(int index, E element)会不导致数组元素移动。
修改方法不会导致ArrayList底层数组扩容。

获取方法

public E get(int index) 根据索引获取元素

注意点：

get(int index)会不导致数组元素移动。
get(int index)查询速度很快，因为可以直接定位元素。
修改方法不会导致ArrayList底层数组扩容。

toString()方法

toString()方法中使用了迭代器方法iterator()。

迭代器方法

public Iterator<E> iterator() 普通迭代器

问题：已知集合List list = new ArrayList<>()里面有三个元素：”hello”、”world”、”java”，使用迭代器遍历集合看有没有”PHP”这个元素，如果有，就使用集合对象删除该元素。

错误代码如下：

    @Test
    public void testRemove() {
        List<String> list = new ArrayList<>();
        list.add("hello");
        list.add("world");
        list.add("java");

        Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            String s = it.next();
            if(s.equals("java")) {
                // 注意此行，若"java"不是倒数第二个元素，则会抛出ConcurrentModificationException
                list.remove("java");
            }
        }
        System.out.println(list);
    }

如上错误代码中，使用Iterator遍历数据时，却使用list来删除数据，会抛出ConcurrentModificationException，如下为正确代码：

    @Test
    public void testRemoveViaIterator() {
        List<String> list = new ArrayList<>();
        list.add("hello");
        list.add("world");
        list.add("java");

        Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            String s = it.next();
            if(s.equals("java")) {
                // 注意此行
                it.remove();
            }
        }
        System.out.println(list);
    }

结论:

迭代器remove()方法底层调用的还是集合自身的remove方法删除元素。
之所以不会产生并发修改异常，是因为在迭代器的remove()方法中会再次将集合时机修改次数赋值给预期修改次数。
当删除ArrayList中倒数第二个元素时，不会出现ConcurrentModificationException。

清空方法

public void clear() 清空集合所有数据

注意点：

将elementData中每个元素都赋值为null，等待垃圾回收将这个给回收掉。
clear()方法不会导致ArrayList底层数组扩容。

包含方法

public boolean contains(Object o) 判断集合是否包含指定元素

注意点：

contains(Object o)方法会调用indexOf(Object o)。

判断集合是否为空

public boolean isEmpty()

常见面试题

ArrayList是如何扩容的？

第一次扩容10，以后每次都是原容量的1.5倍。

ArrayList频繁扩容导致添加性能急剧下降，如何处理？

在特定场景中，如果可以明确知道会有多少个元素，可以使用ArrayList(int initialCapacity)构造方法来直接指定元素个数，避免扩容。

ArrayList添加或删除元素一定比LinkedList慢么？

ArrayList 添加元素时（可能）会导致扩容和数据复制，删除元素时会导致据复制，但是在ArrayList底层不是每次删除元素都需要扩容，因此在这个方面相对于链表来说数组的性能更好。

LinkedList 添加和删除元素之所以效率并不高，其原理在于底层先需要对整个集合进行折半的动作，然后又需要对集合进行遍历一次，这些操作导致效率变低。

ArrayList是线程安全的吗？

ArrayList不是线程安全的。

示例程序（可以创建一个Thread子类，将ArrayList作为构造方法传进来，在run()中对ArrayList进行添加数据。再创建测试方法，创建50个线程，看最终ArrayList中是否有50个元素。）

需要线程安全怎么办?

方式一: 使用Collections.synchronizedList(list)
方式二：使用synchronized加锁锁住对list的操作

如何复制某个ArrayList到另一个ArrayList中？

使用clone()方法
使用ArrayList构造方法
使用addAll方法

ArrayList 和 LinkList区别？

ArrayList

基于动态数组的数据结构
对于随机访问的get和set，ArrayList要优于LinkedList
对于随机操作的add和remove ，ArrayList不一定比LinkedList慢(ArrayList底层由于是动态数组，因此并不是每次add和remove的时候都需要创建新数组)

LinkedList

基于链表的数据结构
对于顺序操作，LinkedList不一定比ArrayList慢
对于随机操作，LinkedList效率明显较低

ArrayList使用在查询比较多，但是插入和删除比较少的情况，而LinkedList用在查询比较少而插入删除比较多的情况

ArrayList类中会抛出如下异常：

IndexOutOfBoundsException
NullPointerException
CloneNotSupportedException
IllegalArgumentException
ConcurrentModificationException

CopyOnWriteArrayList

用于读多写少的场景。

在add()/remove()/set()/clear()/sort()/subList()时会加锁。

自定义ArrayList

详见代码。

作者：张三创建时间：2024-10-13 23:01
最后编辑：张三更新时间：2024-10-25 08:35

java高级-ArrayList

ArrayList原理

学习目标

ArrayList集合底层数据结构介绍

ArrayList集合介绍

数组结构介绍

ArrayList 继承关系

Serializable 标记接口

Cloneable 标记接口

浅拷贝

深拷贝

RandomAccess 标记接口

AbstractList 抽象类

ArrayList源码分析

构造方法

添加方法

删除方法

修改方法

获取方法

toString()方法

迭代器方法

清空方法

包含方法

判断集合是否为空

常见面试题

ArrayList是如何扩容的？

ArrayList频繁扩容导致添加性能急剧下降，如何处理？

ArrayList添加或删除元素一定比LinkedList慢么？

ArrayList是线程安全的吗？

如何复制某个ArrayList到另一个ArrayList中？

ArrayList 和 LinkList区别？

ArrayList

LinkedList

ArrayList类中会抛出如下异常：

CopyOnWriteArrayList

自定义ArrayList