likes
comments
collection
share

第一弹：集合框架（ArrayList篇）

作者站长头像
站长
· 阅读数 27

集合框架（ArrayList篇），持续更新中...

前言

Hello，大家好！我是一个技术小白Leo！

上一篇文章是关于HashMap的一些问题的总结，今天我们来聊一聊关于ArrayList的问题吧。（至于为什么先聊的是HashMap呢？这个...已经不重要啦~~~ [哭笑][哭笑][哭笑]）

本文是自己总结的一些问题，如果和各位看客老爷的想法有出入，望大家提出质疑。

好了废话不多说，咱们开始吧！！！

是时候拿出这张神图了

第一弹：集合框架（ArrayList篇）

今天我们就来聊聊列表孙子辈儿的接口 -ArrayList

ArrayList

ArrayList 是最常用的 List 实现类，实现了List接口的可扩容数组（即动态数组），内部是基于数组实现的，它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔，当数组大小不满足时需要增加存储能力，就要将已经有数组的数据复制到新的存储空间中。当从 ArrayList 的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。

public class ArrayList<E> extends AbstractList<E> implements List<E>,
RandomAccess, Cloneable, java.io.Serializable {...}
  • ArrayList 可以实现所有可选择的列表操作，允许所有的元素，包括空值。ArrayList 还提供了内部存储 list 的方法，它能够完全替代 Vector，只有一点例外，ArrayList 不是线程安全的容器。
  • ArrayList 有一个容量的概念，这个数组的容量就是 List 用来存储元素的容量。
  • ArrayList 不是线程安全的容器，如果多个线程中至少有两个线程修改了 ArrayList 的结构的话就会导致线程安全问题，作为替代条件可以使用线程安全的 List，应使用Collections.synchronizedList。
List list = Collections.synchronizedList(new ArrayList(...))
  • ArrayList 具有 fail-fast 快速失败机制，能够对 ArrayList 作出失败检测。当在选代集合的过程中该集合在结构上发生改变的时候，就有可能会发生 fail-fast，即抛出ConcurrentModificationException 异常。

ArrayList的底层工作原理

  • 在构造ArrayList时，如果没有指定客量，那么内部会构造一个空数组，如果指定了容量，那么就构造出对应容量大小的数组。

  • 在添加元素时，会先判断数组容量是否足够，如果不够则会扩容，扩容按1.5倍扩容,容量足够后，再把元素添加到数组中。

  • 在添加元素时，如果指定了下标，先检查下标是否越界，然后再确认数组客量是否足够，不够则扩容，然后再把新元案添加到指定位置，如果该位置后面有元素则后移。

  • 在获取指定下标的元素时，先检查下标是否越界，然后从数组中取出对应位置的元素

ArrayList和LinkedList有哪些区别？

1.底层数据结构

两者底层数据结构不同，ArrayList底层是基于数组实现的，LinkedList底层是基于链表实现的。

2.插入和删除受到元素位置的影响

ArrayList 采用了动态数组存储数据，所以插入或删除元素的时间复杂度受元素位置的影响的时间复杂度就是 O(1)。比如：执行 add(E e) 方法时 ArrayList 会默认将元素追加到数组的末尾。但是如果要在指定位置 i 插入或删除元素 add(int index, E element)，此时的时间复杂度就会提高到 O(n)，因为在进行上述操作时数组中的第 i 号以及之后的 (n - i) 个元素都要执行向后或向前移动一位的操作。

LinkedList 采用了双向链表存储数据，所以对于执行 add(E e) 方法进行的元素插入是不受元素位置的影响，时间复杂度近似 O(1)。但是如果要在指定位置 i 插入或删除元素 add(int index, E element)，此时的时间复杂度就近似为 O(n)，因为需要先将指针移动到指定位置后再进行元素的插入或删除操作。

3.支持快速随机访问

由于底层数据结构不同，ArrayList 支持随机访问；而 LinkedList 不支持元素的随机访问。

4.保证线程安全

ArrayList 和 LinkedList 都是不同步的，也就是无法保证线程安全。

ArrayList是如何进行扩容的？

首先ArrayList数组在不指定长度的情况下的初始长度为10，存储如果满了，arrayList会自动触发扩容机制，如下：

  1. 首先创建一个新的数组，这个新数组的长度是旧数组长度的1.5倍。
  2. 然后使用 Arrays.copyOf() 方法将旧数组的数据copy到新数组中。
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}
  1. 扩容完成之后会将新添加的元添加到新的数组里边去。

Array 和 ArrayList 有何区别？

  • Array可以存储基本类型和对象；ArrayList只能存储对象。
  • Array是固定大小，而ArrayList大小是自动扩展的。
  • ArrayList内置方法比Array多，例如：addAll、removeAll等方法只有ArrayList有。