Hefery 的个人网站

Hefery's Personal Website

Contact：hefery@126.com
  menu
73 文章
0 浏览
1 当前访客
ღゝ◡╹)ノ❤️
/  

Java基础—ArrayList

ArrayList

ArrayList：动态修改的数组

ArrayList特点

  • 底层基于数组实现，ArrayList集合长度可动态变化。允许 null 的存在
  • JDK1.7开始，右侧尖括号可不写内容，但<>本身还要写ArrayList<String> list = new ArrayList<>();
  • 对于ArrayList集合来说，直接打印得到的不是地址值，而是内容。如果内容是空，得到的是空的中括号：[]
  • 插入的元素是有序的，可以重复

构造方法

方法说明
ArrayList()构造一个初始容量为 10 的空列表
ArrayList(int initialCapacity)构造一个具有指定初始容量的空列表
ArrayList(Collection<? extends E> c)构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的

常用方法

类型方法说明
booleanadd(E e)将指定的元素添加到此列表的尾部
voidadd(int index, E element)将指定的元素插入此列表中的指定位置
voidclear()移除此列表中的所有元素
Eget(int index)返回此列表中指定位置上的元素
booleanisEmpty()如果此列表中没有元素，则返回 true
Eremove(int index)移除此列表中指定位置上的元素
Eset(int index, E element)用指定的元素替代此列表中指定位置上的元素
intsize()返回此列表中的元素数
booleancontains(Object o)如果此列表中包含指定的元素，则返回 true
intindexOf(Object o)返回列表中首次出现的指定元素的索引，如果没有，则返回 -1

ArrayList源码

ArrayList 是 Java 集合框架中比较常用的数据结构，继承 AbstractList，实现 List 接口
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable，还实现了 RandomAccess、Cloneable、Serializable 接口，ArrayList 支持快速访问、复制、序列化

成员变量

主要是：Object[] elementData和int size，而DEFAULT_CAPACITY、EMPTY_ELEMENTDATA、DEFAULTCAPACITY_EMPTY_ELEMENTDATA则用于构造方法

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * 默认初识容量为 10，空参构造器创建使用
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 空的 elementData
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 第一次添加元素时知道 elementData 该从空的构造函数还是有参构造函数被初始化的，以便确认如何扩容
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存储 ArrayList 元素的数组缓冲区
     * ArrayList 的容量就是这个数组缓冲区的长度：elementData.length 为ArrayList容量，表示最多可以容纳多少个元素
     * 当添加第一个元素时，带有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 将扩展为 DEFAULT_CAPACITY
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     * ArrayList实际元素个数（elementData包含的元素数量） 
     */
    private int size;

}

构造函数

使用无参构造函数时，把 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 赋值给 elementData

使用有参构造函数时，initialCapacity 为零则是把 EMPTY_ELEMENTDATA 赋值给 elementData

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
  
    /**
     * 构造一个指定初始容量 DEFAULT_CAPACITY 为 initialCapacity 且 elementData 没有元素的 ArrayList
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            // 非法参数异常
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }
    }

    /**
     * 空参构造：默认初始容量 DEFAULT_CAPACITY 为 10
     */
    public ArrayList() {
        // 构造函数只是给 elementData 赋值了一个空的数组，其实是在第一次添加元素时初始容量扩大至 10
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 构造一个包含传入了数组元素的 ArrayList
     */
    public ArrayList(Collection<? extends E> c) {
        // 将传进来的数组参数赋给 elementData
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // 传进来的数组参数，如果发送错误返回的不是数组，就使用 Arrays 工具类转成数组并赋给 elementData
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 替换成空数组 EMPTY_ELEMENTDATA
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }


}

成员方法

添加add
  • public boolean add(E e)：尾插，直接在 ArrayList 尾部插入数据
  • public void add(int index, E element)：指定 index 插入元素

指定 index 插入元素的 add() 方法：先检查 index 合理性rangeCheckForAdd(index)

即if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
  
    /**
     * 尾插法：将指定元素附加到此列表的末尾，返回是否插入成功的 boolean 类型返回值
     */
    public boolean add(E e) {
        // 确保容量足够
        ensureCapacityInternal(size + 1);  
        // 尾插元素
        elementData[size++] = e;
        // 返回结果
        return true;
    }

    /**
     * 指定位置插入指定元素，将位于当前位置的元素和任何后续元素向右移动（index+1）
     */
    public void add(int index, E element) {
        // 检查插入索引 index 的范围
        rangeCheckForAdd(index);
        // 确保容量足够
        ensureCapacityInternal(size + 1);
        // System.arraycopy 是 native 方法
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        // 指定 index，插入元素
        elementData[index] = element;
        // elementData包含的元素数量++
        size++;
    }

}

无论是哪种 add() 方法，都要先确定容量是否满足：ensureCapacityInternal(size + 1);

先计算明确的容量calculateCapacity(Object[] elementData, int minCapacity)

如果这个计算出来的容量不够就调用 grow(int minCapacity) 扩容ensureExplicitCapacity(int minCapacity)

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    /**
     * 计算最小容量
     * 如果 elementData 是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，就返回 DEFAULT_CAPACITY=10 和 传入参数 minCapacity 最大的那个
     * 如果 elementData 非 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，就返回 传入参数 minCapacity
     */
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    /**
     * 确保显示容量
     */
    private void ensureExplicitCapacity(int minCapacity) {
        // 记录操作次数
        modCount++; 
        // 溢出就扩容 grow()
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
  
}

扩容原理：grow(int minCapacity)

  • 默认将扩容至原来容量的 1.5 倍
  • 扩容一次还是小(newCapacity - minCapacity < 0)，将所需容量大小赋给 newCapacity
  • 扩容一次太多了(newCapacity - MAX_ARRAY_SIZE > 0)，调用hugeCapacity(int minCapacity)方法找到一个适合的容量
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

    /**
     * 扩容：增加容量以确保它至少可以容纳最小容量参数指定的元素数量
     */
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        // 默认将扩容至原来容量的 1.5 倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 扩容一次还是小，将所需容量大小赋给 newCapacity
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 扩容一次太多了，
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 将原数组中的数据复制到大小为 newCapacity 的新数组中，并将新数组赋值给 elementData
        // minCapacity 通常接近 size
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    /**
     * grow扩容一次，容量多了，(newCapacity - MAX_ARRAY_SIZE > 0)
     */
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }

}
移除remove
  • remove(int index)：根据下标 index 移除元素：要判断要删除的元素是否位于数组的最后一个位置
  • remove(Object o)：传入元素值移除元素：判断查找传入参数是否为 null
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

    /**
     * 根据下标 index 移除元素，将后续元素向左移动，从索引中减去 1
     */
    public E remove(int index) {
        // 检查 index 是否合法
        rangeCheck(index);
        // 记录操作数
        modCount++;
        // 记录被移除的元素
        E oldValue = elementData(index);
        // 要删除的元素是否位于数组的最后一个位置
        int numMoved = size - index - 1;
        if (numMoved > 0)
            // 将后续元素向左移动，从索引中减去 1
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        elementData[--size] = null;
        // 返回被移除的元素
        return oldValue;
    }

    /**
     * 从此列表中删除指定元素的第一个匹配项
     */
    public boolean remove(Object o) {
        // 查找传入参数是否为 null
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        // 传入参数没移除，返回 false
        return false;
    }

    /*
     * 跳过边界检查且不返回已删除值
     */
    private void fastRemove(int index) {
        // 记录操作数
        modCount++;
        // 要删除的元素是否位于数组的最后一个位置
        int numMoved = size - index - 1;
        if (numMoved > 0)
            // 将后续元素向左移动，从索引中减去 1
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        // 移除元素
        elementData[--size] = null;
    }

}
获取get

get(int index)：根据下标 index 返回元素值 elementData(index)

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

    /**
     * 返回 ArrayList 指定位置的元素
     */
    public E get(int index) {
        // 检查 index 是否合法
        rangeCheck(index);
        return elementData(index);
    }

}
替换set

set(int index, E element)：在下标 index 处替换元素值为 element

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

    /**
     * 将 ArrayList 指定位置 index 的元素替换为指定元素 element
     */
    public E set(int index, E element) {
        // 检查 index 是否合法
        rangeCheck(index);
        // 记录替换前的元素值
        E oldValue = elementData(index);
        // 将新的元素值在指定位置 index 处替换
        elementData[index] = element;
        // 返回替换前的值
        return oldValue;
    }

}
清除clear

void clear()：遍历 ArrayList 将所有元素值设置为 null，再把 ArrayList 实际元素个数 size 设置为 0

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

    /**
     * 清除 ArrayList 中所有元素
     */
    public void clear() {
        // 记录操作数
        modCount++;
        // 遍历，所有元素值设置为 null
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        // ArrayList实际元素个数设置为 0
        size = 0;
    }

}

ArrayList留坑

先看演示代码：ArrayList 存储了 [0, 1, 2, 3, 3, 4]，遍历删除值为 3 的元素，却没删干净

public class ListDemo {

    public static void main(String[] args) {
        List<Integer> list=new ArrayList<Integer>();
        list.add(0);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(3);
        list.add(4);
        System.out.println(list);  // [0, 1, 2, 3, 3， 4]

        // 普通for循环遍历
        for(int i=0;i<list.size();i++){
            if(list.get(i)==3) list.remove(i);
        }
        System.out.println(list);  // [0, 1, 2, 3, 4]

        // foreach遍历
        for(Integer i:list){
            if(i==3) list.remove(i);
        }
        System.out.println(list);  // [0, 1, 2, 3, 4]

        // 迭代遍历,用list.remove(i)方法删除元素
        Iterator<Integer> it = list.iterator();
        while (it.hasNext()) {
            Integer value = it.next();
            if(value==3) {
                list.remove(value);
            }
        }
        System.out.println(list);  // [0, 1, 2, 3, 4]
    }

}

原因：List调用remove(index)方法后，会移除 index 位置上的元素，index 之后的元素就全部依次左移，即索引依次 -1 要保证能操作所有的数据。只要 List 中有相邻 2 个相同的元素，就过滤不完

解决：需要把 index-1，否则原来索引为index+1的元素就无法遍历到(因为原来索引为 index+1 的数据，在执行移除操作后，索引变成 index，如果没有 index-1 的操作，就不会遍历到该元素，而是遍历该元素的下一个元素)

public class ListDemo {

    public static void main(String[] args) {
        List<Integer> list=new ArrayList<Integer>();
        list.add(0);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(3);
        list.add(4);
        System.out.println(list);  // [0, 1, 2, 3, 3， 4]

        // 索引同步
        for (int i=list.size()-1; i >= 0; i--) {
            if (list.get(i) == 3) {
                list.remove(i);
            }
        }
        System.out.println(list);  // [0, 1, 2, 4]

        // 倒叙遍历
        for(int i=0;i<list.size();i++){
            if(list.get(i)==3) {
                list.remove(i--);
            }
        }
        System.out.println(list);  // [0, 1, 2, 4]

        // 迭代器
        Iterator<Integer> it = list.iterator();
        while (it.hasNext()) {
            if(it.next() == 3) {
                it.remove();
            }
        }
        System.out.println(list);  // [0, 1, 2, 4]
    }

}

ArrayList去重

  • Stream 流的 distinct
  • LinkedHashSet
public class ArrayListDemo {

    public static void main(String[] args) {
        ArrayList<Integer> numbersList = new ArrayList<>(Arrays.asList(1, 1, 2, 3, 3, 3, 4, 5, 6, 6, 6, 7, 8));
        // LinkedHashSet
        LinkedHashSet<Integer> hashSet = new LinkedHashSet<>(numbersList);
        ArrayList<Integer> listWithoutDuplicates1 = new ArrayList<>(hashSet);
        System.out.println(listWithoutDuplicates1);
        // Stream
        List<Integer> listWithoutDuplicates2 = numbersList.stream().distinct().collect(Collectors.toList());
        System.out.println(listWithoutDuplicates2);
    }

}

Arrays工具类

数组工具类，都是定义了静态方法

数据类型方法说明
static StringtoString(数组)返回指定数组内容的字符串表示形式
static voidsort(数组)数字升序、字符按值
static <T> T[]copyOf(T[] original, int newLength)复制指定的数组，截取或用 null 填充（如有必要），以使副本具有指定的长度
static <T> List<T>asList(T... a)返回一个受指定数组支持的固定大小的列表
static intbinarySearch(Object[] a, T key)使用二分搜索法来搜索指定数组，以获得指定对象
标题：Java基础—ArrayList
作者：Hefery
地址：http://hefery.icu/articles/2022/03/16/1647433266664.html