真理并无尽头

常用List集合

HeJin大约 7 分钟Java集合

List集合的特点

List接口下的集合都有以下这些特点：

  • 有索引。
  • 可以存储重复元素。
  • 元素存入的顺序和实际读取顺序相同。

ArrayList

创建对象

// 构造一个空列表
public ArrayList() 

// 创建指定大小的ArrayList
public ArrayList(int initialCapacity) 

// 根据传入的Collection集合创建ArrayList
public ArrayList(Collection<? extends E> c)

常用方法

// 添加元素到集合的末尾，返回值代表太假成功
public boolean add(E e) 

// 指定索引位置添加元素
public void add(int index, E element) 

// 移除指定索引位置的元素，返回的是移除元素的值
public E remove(int index) 

// 移除指定元素
public boolean remove(Object o) 

// 修改指定索引位置的元素，返回值为修改之前的值
public E set(int index, E element) 

// 获取指定索引位置的元素
public E get(int index) 

// 获取集合大小
public int size() 

// 判断集合中是否存在元素
public boolean contains(Object o) 

// 判断集合是否为空
public boolean isEmpty()

遍历

索引遍历

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);

    for (int i = 0; i < list.size(); i++) {
        System.out.println(list.get(i));
    }
}

迭代器遍历

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);

    Iterator<Integer> iterator = list.iterator();
    while (iterator.hasNext()){
        Integer next = iterator.next();
        System.out.println(next);
    }
}

并发修改异常

迭代器遍历集合的时候修改集合，这时会出现并发修改异常。

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);

    Iterator<Integer> iterator = list.iterator();
    while (iterator.hasNext()){
        Integer next = iterator.next();
        if(next == 2){
            // 遍历集合的时候修改集合，这时会出现并发修改异常
            list.remove(next);
        }
        System.out.println(next);
    }
}
image-20221107133709157
image-20221107133709157

解决办法：（1）使用索引遍历

  • 1.索引正序遍历会出现漏掉元素的情况：
public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);

        for (int i = 0; i < list.size(); i++) {
            Integer num = list.get(i);
            if(num == 2){
                // 遍历集合的时候修改集合，这时会出现并发修改异常
                list.remove(i);
            }
            System.out.println(num);
        }
}

结果：

1
2
4

Process finished with exit code 0

这是因为ArrayList底层是数组来存储元素的，删除元素的时候，会把后面的元素移到前面。

如果一定要正序遍历，可以在删除元素后，把索引位置回退一位：

public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);

        for (int i = 0; i < list.size(); i++) {
            Integer num = list.get(i);
            if(num == 2){
                // 这时候就不会出现异常
                list.remove(i);
                // 删除元素移动了位置，回退一位
                i--;
            }
            System.out.println(num);
        }
    }
  • 2.索引倒序遍历解决问题
public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);

        for (int i = list.size() - 1; i >= 0; i--) {
            Integer num = list.get(i);
            if(num == 2){
                // 这时候就不会出现异常
                list.remove(i);
            }
            System.out.println(num);
        }
    }

4
3
2
1

Process finished with exit code 0

解决办法：（2）使用迭代器对象移除元素，而不是直接操作集合。

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);

    Iterator<Integer> iterator = list.iterator();
    while (iterator.hasNext()){
        Integer next = iterator.next();
        if(next == 2){
            // 使用迭代器移除元素
            iterator.remove();
        }
        System.out.println(next);
    }

}

并发修改异常原理

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);

    Iterator<Integer> iterator = list.iterator();
    while (iterator.hasNext()){
        Integer next = iterator.next();
        if(next == 2){
            // 直接操作集合，出现并发修改异常
            list.remove(next);
        }
        System.out.println(next);
    }

}

确定异常位置

image-20221107140856226
image-20221107140856226
image-20221107141011796
image-20221107141011796
image-20221107141101188
image-20221107141101188

查看源码

image-20221107141606864
image-20221107141606864
image-20221107141918883
image-20221107141918883

checkForComodification方法：

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

其中modCount是ArrayList的父类AbstractList的成员变量：

image-20221107142320220
image-20221107142320220

expectedModCount是ArrayList的成员内部类Itr的成员变量：

image-20221107142536787
image-20221107142536787

调用ArrayList的迭代器Itr的next方法会首先判断modCount 和 expectedModCount是否相等：

public E next() {
    checkForComodification();
    int i = cursor;
    if (i >= size)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

如果modCount != expectedModCount，就抛出并发修改异常。

经过debug，我们发现，只要不涉及删除元素，modCount = expectedModCount。

image-20221107145550306
image-20221107145550306

当删除元素之后，list.modCount就会发生变化。

image-20221107145801914
image-20221107145801914

此时再次调用迭代器的next()方法，就会抛出异常：

image-20221107145915022
image-20221107145915022

结论：ArrayList的迭代器对象的next()方法，会进行modCount（ArrayList的成员变量）和expectedModCount（迭代器的成员变量，初始值=modCount）的比较。而在对集合进行结构修改（增加、删除元素等），modCount会发生改变。此时迭代器的next()调用时就会抛出并发修改异常。

查看ArrayList的remove方法，发现的确修改了modCount：

public boolean remove(Object o) {
    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;
            }
    }
    return false;
}

private void fastRemove(int index) {
    modCount++;		// 这里修改了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
}

查看ArrayList的其他方法，发现有的也修改了modCount：

image-20221107150551639
image-20221107150551639
image-20221107150631463
image-20221107150631463
image-20221107150708289
image-20221107150708289

所以，在对ArrayList进行迭代器遍历时，如果直接修改ArrayList集合结构（删除、增加、排序等），会抛出并发修改异常。

使用迭代器的remove方法为什么可以遍历的时候删除集合中的元素，不抛出异常

image-20221107151928451
image-20221107151928451

思考：迭代器的iterator.next()方法为什么需要并发修改异常？

保证数据安全。多线程情况下，线程A需要调用迭代器的next()方法获取元素，但是在此之前线程B修改或者删除了元素。如果不进行安全判断，线程A就无法获取到原来的数据。

foreach遍历

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);

    for (Integer a : list) {
        System.out.println(a);
    }
}

底层还是使用迭代器实现的。所以，如果直接修改集合，还是会出现并发修改异常。

转换为数组遍历

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(5);
    list.add(4);

    Integer[] ints = list.toArray(new Integer[0]);
    for (Integer i : ints) {
        System.out.println(i);
    }

}

LinkedList

创建对象

// 创建一个空集合
public LinkedList() 

// 根据传入的Collection集合创建LinkedList 
public LinkedList(Collection<? extends E> c)

常用方法

LinkedList是List接口的链表实现，使用的是双向链表，并且维护了指向链表的头节点指针和尾节点指针。

同时LinkedList实现了Deque接口，是一个双端队列。支持在两端插入和删除元素的线性集合。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;
    
    transient Node<E> first;

    transient Node<E> last;
    
    ......
        
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }    
}

链表特性

// 添加元素到集合尾部
public boolean add(E e)

// 将指定元素插入到集合中的指定位置。
// 将当前位于该位置的元素(如果有的话)和所有后续元素向右移动(向它们的索引添加1)    
public void add(int index, E element)
    
// 在集合头部插入元素   
public void addFirst(E e)

// 在集合尾部插入元素    
public void addLast(E e)

// 移除指定元素    
public boolean remove(Object o)

// 移除指定位置的元素    
public E remove(int index)

// 移除集合头部元素    
public E removeFirst()

// 移除集合尾部元素     
public E removeLast()    
    
// 获取指定集合位置的元素    
public E get(int index)
    
// 设置指定位置的元素值  
public E set(int index, E element)
    
// 返回集合元素个数
public int size()
    
// 判断集合中是否存在元素    
public boolean contains(Object o)

队列特性

// 入队：添加指定元素作为列表的尾部(最后一个元素)。
public boolean offer(E e)

// 入队：插入元素到列表的头部（第一个元素）    
public boolean offerFirst(E e)

// 入队：插入元素到列表的尾部（最后一个元素）      
public boolean offerLast(E e)    

// 返回该列表的第一个元素，但不删除    
public E peek()    
    
// 出队：删除并返回该列表的第一个元素    
public E pop()    
    
// 返回此列表中的第一个元素    
public E getFirst()
    
// 返回此列表中的最后一个元素    
public E getLast()

遍历

同ArrayList。

  • 索引遍历
  • 迭代器遍历
  • foreach（增强for循环）遍历
  • 转化为数组遍历

ArrayList和LinkedList的区别

都是实现了List接口，不同点是底层存储数据的数据结构不同。ArrayList底层使用数组来存储，而LinkedList是双向链表。而且LinkedList还实现了双端队列，可以实现队列的操作。

  • ArrayList：查找快，增删慢。
  • LinkedList：增删快，查找慢。
Copyright © 2023 HeJin