正文 

当前位置： 首页 > 程序 > java教程

java集合学习笔记：arraylist(代码片段)

笑虾 笑虾     2022-10-24     560

关键词：

Java 集合学习笔记：ArrayList

简介

ArrayList 是 List 接口的大小可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。（此类大致上等同于 Vector 类，除了此类是非线程安全的。）

List 的 数组实现。

  1. 因为底层数据解构是数组，所以特点是连续内存空间，根据索引操作。
  2. 优势在读，频繁写操作相对吃亏。有两个性能消耗点：
    2.1. 插入/删除时，当前元素之后的所有元素需要整体平移。
    2.2. 空间不足时的反复自动扩容。

UML


从类图可见ArrayList 并不是直接实现 List 。
ArrayList 是继承 AbstractList 再进行扩展的。
至于实现List接口的行为，听说是失误，反正删不删也不影响，所以就一直没动。

常用方法

增

方法说明
boolean add(E e)在列表末尾添加新元素。
void add(int index, E element)在指定位置添加元素，原 index 到末尾的所有元素，整体后移一位。
boolean addAll(Collection<? extends E> c)将指定集合添加到当前列表的末尾。
boolean addAll(int index, Collection<? extends E> c)将指定集合插入当前列表的指定位置。

删

方法说明
void clear()清空列表。
E remove(int index)移除指定索引上的元素。右侧所有元素整体向左平移一位。
boolean remove(Object o)移除指定元素。如果有多个，每次只会移除第一个。
boolean removeAll(Collection<?> c)删除指定集合中包含的元素。
boolean removeIf(Predicate<? super E> filter)删除所有复合条件的元素。（filter 是一个返回布尔型的 Lambda）
boolean retainAll(Collection<?> c)保留当前列表与目标集合中都存在的元素。也就是，从当前列表中删除指定集合中不存在的所有元素。

改

方法说明
E set(int index, E element)替换指定位置的元素
void replaceAll(UnaryOperator operator)遍历列表执行特定的操作，实现替换。list.replaceAll(x -> x * 2);
void sort(Comparator<? super E> c)传入一个比较器。list.sort((a,b) -> b-a);

查

方法说明
size()获取列表大小。
boolean isEmpty()判断列表是否为空。
E get(int index) 按索引获取元素。
boolean contains(Object o)判断列表是否包含指定元素。
int indexOf(Object o)返回指定元素在列表中的索引位置 。
int lastIndexOf(Object o)返回指定元素最后一次出现的位置。

迭代

方法说明
void forEach(Consumer<? super E> action)遍历列表执行消费者。
Iterator iterator()返回迭代器
Spliterator spliterator()返回可拆分迭代器。
ListIterator listIterator()返回双向迭代器。
ListIterator listIterator(int index)从指定的位置开始，返回双向迭代器。
List subList(int fromIndex, int toIndex)返回指定范围的subList
Object[] toArray()返回 Object 数组
<T> T[] toArray(T[] a)返回指定类型数组。 list.toArray(new Integer[0]);

内部类

类说明
class Itr implements Iterator实现了 Iterator 接口，iterator() 返回的就是它。
class ListItr extends Itr implements ListIterator双向迭代器。listIterator() 返回的就是它。
private class SubList extends AbstractList implements RandomAccess私有内部类。subList() 返回的就是它。

静态内部类

类说明
static final class ArrayListSpliterator<E> implements Spliterator<E>实现了可拆分迭代器接口。

自动扩容逻辑

Java7

–说明
Object[] elementData;被封装的数组对象：ArrayList内部真正储存数据的容器。
自动扩容其实就是在折腾elementData。
int size;元素个数： ArrayList中实际存储元素的个数。
DEFAULT_CAPACITY = 10;默认初始容量
Object[] EMPTY_ELEMENTDATA = ;初始化容器 ：所有ArrayList都用它初始化，避免创建无数个空数组浪费。
默认扩容因子oldCapacity + (oldCapacity >> 1)： 原容量 x 1.5
扩容方式1. 调用 ensureCapacity(int minCapacity) 手动扩容。
2. add 时自动检测并按需扩容。
3. addAll 时自动检测并按需扩容。
4. readObject(ObjectInputStream s) 时自动检测并按需扩容。

minCapacity：最小所需容积
newCapacity：新容积

  1. 计算新容积newCapacity：
    1.1. 默认扩容1.5倍。
    1.2. 如果1.5不够，则扩容到所需大小minCapacity。
    1.3. 如果新容积newCapacity > MAX_ARRAY_SIZE则进一步判断：(minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
  2. 底层调用Arrays.copyOf(elementData, newCapacity)创建新数组，再将结果赋给原容器elementData。
    2.1. Arrays.copyOf的底层是native原生方法System.arraycopy

Java8

-说明
int DEFAULT_CAPACITY = 10;默认初始容量。（容量：指底层数组实际大小）
Object[] EMPTY_ELEMENTDATA = ;列表大小为 0 时共享此空数组。避免每个空列表都创建一个空数组，浪费。
Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = ;1. 初始列表时，没给默认大小，用此空数组。
2. 扩容时用于作为判断条件之一。
Object[] elementData;内部容器，底层实际用于保存数据的数组。
size列表长度。（容器当前存了几个元素）。
默认扩容因子新容量 = 旧容量 + (旧容量 >> 1) = 原容量 x 1.5

具体的直接看源码吧。。。

扩容 - 核心代码

/**
 * 在此列表中的指定位置插入指定元素。
 * 将当前位于该位置的元素（如果有）和任何后续元素向右移动（将其索引加一）。
 */
public void add(int index, E element) 
	// 检查 index 如果越界就抛异常。
	rangeCheckForAdd(index);
	// 判断内部数组 elementData 大小，如果有需要就扩容。同时列表修改次数 modCount++
	ensureCapacityInternal(size + 1);
	// 将目标索引后面的所有元素整体向后移一位。用的原生方法 System.arraycopy
	System.arraycopy(elementData, index, elementData, index + 1, size - index);
	// 当前索引位置赋值
	elementData[index] = element;
	// 列表大小+1
	size++;

/**
 * 计算内部数组 elementData 最小所需容量
 */
private void ensureCapacityInternal(int minCapacity) 
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) 
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    
	// 判断内部数组 elementData 大小，如果有需要就扩容。
    ensureExplicitCapacity(minCapacity);

/**
 * 判断内部数组 elementData 大小，如果有需要就扩容。
 */
private void ensureExplicitCapacity(int minCapacity) 
	// 列表修改次数 modCount++
	modCount++;

    // 最小所需容量 > 数组原长度则扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);

/**
 * 扩容，以确保至少要能下 minCapacity 个元素。
 */
private void grow(int minCapacity) 
    // 原容量
    int oldCapacity = elementData.length;
    // 新容量 = 原容量 + (原容量 / 2)
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 新容量够用就用新容量，不够就按 minCapacity 来。
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 新容量大于最大限制，就使用最大限制。
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 原数组 = 复制原数组中的数据，并按 newCapacity 创建的新数组。
    elementData = Arrays.copyOf(elementData, newCapacity);

移除 - 核心代码

  • E remove(int index)
public E remove(int index) 
    rangeCheck(index); // 检查索引，越界就抛异常

    modCount++; // 列表修改次数 +1
    E oldValue = elementData(index); // 缓存当前索引值，删除完成后 return 出去
	// 利用 arraycopy 将索引后的全部元素整体前移一位，覆盖当前索引值，达到删除目的。
    int numMoved = size - index - 1; // 计算需要整体向左移动的元素个数
    // 如果有，就复制（以复制实现移动效果）
    // 将数组 elementData 中 index+1 位置开始的元素，复制到 index 处。（也就是向前移一位）
    // 需要复制的元素个数就是 numMoved （也就是被删除的元素右侧的所有元素）
    if (numMoved > 0) 
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    // 所有数据复制后向左移一位粘贴，最右侧一格现在就需要销毁了。
    elementData[--size] = null; // --size 实现长度减1。同时也将最后一个元素=null 以便垃圾回收。
	// 返回被删除的值
    return oldValue;
  • boolean remove(Object o)
// 遍历数组逐个比对，找到第一个复合的元素就移除。
// 唯一区别就在于 null 和普通对象做了区别处理
public boolean remove(Object o) 
    if (o == null) 
        for (int index = 0; index < size; index++)
        	// null 直接使用 == 对比
            if (elementData[index] == null) 
                fastRemove(index);
                return true;
            
     else 
        for (int index = 0; index < size; index++)
        	// 其他对象使用 equals 对比
            if (o.equals(elementData[index])) 
                fastRemove(index);
                return true;
            
    
    return false;

// 在 remove(int index) 基础上做了简化，省去了对【索引的校验】和【删除值的返回】。
// 因为这里是通过对比对象得出的 index 绝对是存在的。
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

根据 remove 我们可以看到，每次执行只会移除第一个匹配到的元素。

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, null, 3, 4, 5, null));
list.remove(null);
System.out.println(list);
// [1, 2, 3, 4, 5, null]
  • boolean removeAll(Collection<?> c) 
public boolean removeAll(Collection<?> c) 
    Objects.requireNonNull(c); // 如果 c 为 null 抛异常
    return batchRemove(c, false); //  

/**
 * 批量移除
 * @param c collection 从当前列表中的元素，如果 c 也有，那么根据 complement 决定去留。
 * @param complement 判断对 c 中包含的元素 true=保留，false=移除
 */
private boolean batchRemove(Collection<?> c, boolean complement) 
    final Object[] elementData = this.elementData;
    // r 表示被检测的索引。用于遍历原数组，从 0 一直加到 size-1，逐个检测元素。
    // w 表示用于保存的位置。配合 r 每判定保留（移动的元素就是要保留下来的）一个元素 +1。最终 w 也就是最后一个留存元素的索引。
    int r = 0, w = 0;
    boolean modified = false;
    try 
    	// 本质上是两层循环：第一层 for 遍历 elementData
    	// 第二层用 c.contains 进行了简化。判断 c 中是否包含 elementData的当前元素。
    	// 如果不包含，就是要保留的元素。将元素从 r 移动到 w。然后 w 向后移一位。 
    	// 否则遇到需要移除的元素时，只需要跳过移动操作。r++ 但 w 没动，下个元素移过就实现了。
    	// 假设第一个元素就是要移除的，那么移动就是：1到0, 2到1，3到2，以此类推，从第二个元素开始整体向前平移一位。
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
            	// 将要保留的元素从 r 移到 w
                elementData[w++] = elementData[r];
     finally 
        // r 没走到 size 只有一种可能就是异常了。(暂时还没想到什么情况能触发异常)
        // 后面的不处理的，没移动的都一把移过来。
        // 最后更新 w  = w + 刚才这波移动的个数
        if (r != size) 
            System.arraycopy(elementData, r, elementData, w, size - r);
            w += size - r;
        
        // w 之后都是要移除的，全部置空，等GC回收
        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;

使用建议

  1. 插入：如果插入多个连续的元素，可以使用addAll优化 。只需要整体平移一次。
  2. 扩容：如果能提前确定所需容积，可以手动指定大小来实现优化。省掉多次扩容浪费时间。
  3. 删除：如是删除连续的几个元素可以使用removeRange(int fromIndex, int toIndex) ，底层只需要 arraycopy 整体平移一次。
    3.1. 当然这个方法没有直接开放给用户使用。可以list.subList(3, 5).clear();间接调它。
    3.2. subList.clear() > List.clear() > AbstractList.clear() >> AbstractList.removeRange() >ArrayList.removeRange() 大概就是这么兜了一圈，实现的。
  4. 遍历删除：遍历中要删除元素的场景，请用迭代器或Java8的 removeIf。详情见：笑虾：forEach 遍历中 remove 的BUG，及 Java8 的新推荐。
  5. 效率：底层的数据结构为数组，基于索引操作。相对来说：查询效率高，增删效率低。

参考资料

ArrayList

笑虾：Java 集合学习笔记：Iterator
笑虾：Java 集合学习笔记：Collection

java集合学习笔记：arraylist(代码片段)

Java集合学习笔记：ArrayListUML简介阅读源码增删改查手动扩容/缩容迭代内部类ItrListItr静态内部类自动扩容逻辑Java7Java8扩容-核心代码移除-核心代码学习总结参考资料UML从类图可见ArrayList并不是直接实现List。ArrayList是继承Abstra... 查看详情

java集合类（java.util）源码阅读笔记------arraylist(代码片段)

一、继承关系publicclassArrayList<E>extendsAbstractList<E>implementsList<E>,RandomAccess,Cloneable,java.io.Serializable继承自AbstractList抽象类，实现List接口，RandomAccess接口，Clonea 查看详情

java集合学习笔记(代码片段)

Java集合学习笔记前言开始学习Java的集合，简要的记录一下学习到的东西，仅供自己查阅和复习方便。学习自廖雪峰的Java教程。集合简介Java标准库自带的java.util包提供了集合类：Collection，它是除Map外所有其他集... 查看详情

java集合学习笔记(代码片段)

Java集合学习笔记前言开始学习Java的集合，简要的记录一下学习到的东西，仅供自己查阅和复习方便。学习自廖雪峰的Java教程。集合简介Java标准库自带的java.util包提供了集合类：Collection，它是除Map外所有其他集... 查看详情

java集合学习笔记：hashmap(代码片段)

Java集合学习笔记：HashMapUML简介阅读源码属性字段1.静态属性2.成员属性HashMap结构静态工具方法hash【算法学习】^加>>>减少碰撞comparableClassFor(Objectx)compareComparables(Class<?>kc,Objectk,Objectx)tableSizeFor(intcap)【算法学习】32 查看详情

java集合学习笔记：abstractlist(代码片段)

Java集合学习笔记：AbstractListequals(Objecto)hashCode()indexOf(Objecto)lastIndexOf(Objecto)clear()addAll(intindex,Collection<?extendsE>c)equals(Objecto)ItrListItrSubList参考资料equals(Objecto)实现equa 查看详情

java集合学习笔记：map(代码片段)

Java集合学习笔记：MapUML简介源码阅读嵌套类interfaceEntry<K,V>静态方法comparingByKey()comparingByKey(Comparator<?superK>cmp)comparingByValue()comparingByValue(Comparator<?superV>cmp)比较器InterfaceCo 查看详情

java集合学习笔记：hashmap(代码片段)

Java集合学习笔记：HashMapUML简介阅读源码属性字段1.静态属性2.成员属性静态内部类classNode<K,V>静态工具方法hash(Objectkey)comparableClassFor(Objectx)compareComparables(Class<?>kc,Objectk,Objectx)tableSizeFor(intcap)构造方法H 查看详情

java集合学习笔记：比较器comparablecomparator(代码片段)

Java集合学习笔记：比较器Comparable、ComparatorComparable隐式比较升序（默认）Comparator显示比较Lambda降序Comparator.reverseOrder降序参考资料Comparable隐式比较packagecom.jerry;importlombok.Data;@DatapublicclassHero 查看详情

java集合学习笔记：比较器comparablecomparator(代码片段)

Java集合学习笔记：比较器Comparable、ComparatorComparable隐式比较升序（默认）Comparator显示比较Lambda降序Comparator.reverseOrder降序参考资料Comparable隐式比较packagecom.jerry;importlombok.Data;@DatapublicclassHero 查看详情

java集合学习笔记：list(代码片段)

Java集合学习笔记：ListUMLListUML除了过气的Vector直接实现List接口，其他实现都是通过继承AbstractList实现的。List可以看出List在Collection基础增加的一批方法，都是针对索引用的。限定符和类型方法和说明voidadd(intindex,Eeleme... 查看详情

java集合学习笔记：list(代码片段)

Java集合学习笔记：ListUMLListUML除了过气的Vector直接实现List接口，其他实现都是通过继承AbstractList实现的。List可以看出List在Collection基础增加的一批方法，都是针对索引用的。限定符和类型方法和说明voidadd(intindex,Eeleme... 查看详情

java集合学习笔记：iterableiterator(代码片段)

Java集合学习笔记：Iterable、IteratorUMLIterable_可迭代JDK8之前JDK8新增default方法Iterator_迭代器JDK8之前JDK8新增default方法参考资料UML此图内含Collection.uml可在Idea中打开在学习设计模式的时候就有一个"迭代器模式"，JDK中提... 查看详情

java集合学习笔记：collection(代码片段)

Java集合学习笔记：CollectionUML简介方法和说明JDK8新增`default`方法参考资料UML简介Collection表示包含了一组元素的对象，它定义了一系列用来折腾这些元素的方法。给徒子徒孙们立好了规矩。通常不直接实现这个接口&#... 查看详情

java学习笔记：list，set，map(代码片段)

...0c;还有很多没加上去。。。未完待续。。。容器也叫集合ArrayList：用数组组成的线性结构LinkedList：用链表组成的线性结构…所有的容器装的是对象，但是容器会把传进去的孤立的值自动装箱成对象，功能强大。有... 查看详情

arraylist学习笔记(代码片段)

ArrayList的数据结构比较简单，但是其中也包含了一些好的设计思想。ArrayList是用数组实现的，因为可以自动扩容（增加50%），所以ArrayList也可以理解为动态数组。1.初始化ArrayList的实现也是在不断改进的。在JDK... 查看详情

go语言学习笔记十三：map集合(代码片段)

Go语言学习笔记十三：Map集合Map在每种语言中基本都有，Java中是属于集合类Map，其包括HashMap,TreeMap等。而Python语言直接就属于一种类型，写法上比Java还简单。Go语言中Map的写法比Java简单些，比Python繁琐。定义Mapvarxmap[string]stringx:... 查看详情

集合(java)(代码片段)

...学习Java知识了。在之前我们一起了解过了集合中的一种ArrayList,没有看过的观众老爷请点击链接先了解一下浅谈集合之ArrayList_Michelhjx的博客-CSDN博客        现在我们稍微回顾一下集合类的特点 :                提供... 查看详情