[数据结构与算法]ArrayList使用remove()移除元素失败

有关ArrayList的源码解析以及HashMap、Set等相关内容在原来的文章中已经介绍过了，这里就不再赘述。今天这篇文章单刀直入将今天在工作中遇到的一个问题，ArrayList调用remove移除元素失败？

从源码角度来ArrayList的扩容机制与LinkedList链表的维护与查找_任天柳-CSDN博客](https://blog.csdn.net/lmlzww/article/details/117635696?spm=1001.2014.3001.5501)

Java集合——HashMap源码_任天柳-CSDN博客](https://blog.csdn.net/lmlzww/article/details/122029568?spm=1001.2014.3001.5501)

抽离业务之后的代码

public static void main(String[] args) {
    ArrayList<Integer> targetIndex = new ArrayList<>();
    targetIndex.add(0);
    LinkedList<String> dataSource = new LinkedList<>();
    dataSource.add("one");
    dataSource.add("tow");
    dataSource.add("three");
    //移除失败[one, tow, three]
    targetIndex.forEach(item->{
        dataSource.remove(item);
    });
    System.out.println(dataSource.toString());
    //移除成功[tow, three]
    targetIndex.forEach(item->{
        dataSource.remove(item.intValue());
    });
    System.out.println(dataSource.toString());
}

原理概述

简单的来说之所以第一遍遍历的时候没有遍历成功，这是由于多态机制的存在，在list中remove的实现有两个方法一个是根据索引进行移除的一个是根据对象进行移除。在第一个循环中我们传递进去的参数是Interge形式的，在调用的时候他会调用：

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

我们可以看出他是将入参当做list中的一个值，而非是一个索引，通o.equals(x.item)来决定是要对那个元素进行移除，而我们传递进去的索引，所以在这个场景中他就没有找到要移除的元素。这里可以想到如果dataSource的类型也是Integer,那用第一种方法进行移除就更有意思了，因为他有可能是碰巧对应上的。这时候数据就会发生混乱。

而第二中的遍历方式中我们采用了intValue()，这个方法的返回值是一个int，所以remove方法就调用了：

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

这两个方法的不同点在于第一种是通过比对集合内的值来寻找要移除的元素，而第二中则是通过索引直接找到要移除的元素。这里重点点一下第二种方法如何确定要移除的元素。我们常见的List有两种一个是底层实现为数组的ArrayList、一种为底层实现为链表的LinkList。

ArrayList移除元素的操作是通过index直接确定下标元素的位置，之后通过数组拷贝来实现数组的一个整体前移。LinkList是链表，他的index实际上是一个虚拟的，他是通过index确定要遍历多少个链表元素，来确定要移除的目标元素。但是写JDK的大佬们很机智，他们并没有直接简单的从头或是从尾遍历，而是采用一个类似于二分的机制根据index来决定这个元素从头遍历还是从尾遍历。这一点感觉是LinkList的精髓所在：

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}