ArrayList移除元素
首先在主函数中调用ArrayList的有参构造方法生成一个List实例list，并且发现共有四种移除元素的方法：
List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C", "D", "E", "F", "G", "H", "I", "J")); list.remove(3); list.remove("H"); list.removeAll(Arrays.asList("F", "G")); list.clear();
remove(int index)
点进去第一个remove方法：
/** * Removes the element at the specified position in this list. * Shifts any subsequent elements to the left (subtracts one from their * indices). * * @param index the index of the element to be removed * @return the element that was removed from the list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); 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 return oldValue; }
首先检验index是否合法，然后将index对应元素赋值给oldValue，需要移动的元素为index之后的所有元素，总数为size-index-1，使用System.arraycopy来将index之后的所有元素向前移动一位；该方法时间复杂度较高；
remove(Object o)
点进去第二个remove方法：
/** * Removes the first occurrence of the specified element from this list, * if it is present. If the list does not contain the element, it is * unchanged. More formally, removes the element with the lowest index * <tt>i</tt> such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> * (if such an element exists). Returns <tt>true</tt> if this list * contained the specified element (or equivalently, if this list * changed as a result of the call). * * @param o element to be removed from this list, if present * @return <tt>true</tt> if this list contained the specified element */ 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; }
使用遍历的方式去寻找该对象，发现第一个与该对象相等的元素，使用fastRemove方法进行移除，并返回true，因此该方法只能移除第一个与该对象相等的元素。点进去fastRemove方法：
/* * Private remove method that skips bounds checking and does not * return the value removed. */ 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 }
发现该方法也是通过System.arraycopy将index之后的所有元素向前移动一位；该方法时间复杂度较高；
removeAll(Collection<?> c)
点进去removeAll方法
/** * Removes from this list all of its elements that are contained in the * specified collection. * * @param c collection containing elements to be removed from this list * @return {@code true} if this list changed as a result of the call * @throws ClassCastException if the class of an element of this list * is incompatible with the specified collection * (<a href="Collection.html#optional-restrictions">optional</a>) * @throws NullPointerException if this list contains a null element and the * specified collection does not permit null elements * (<a href="Collection.html#optional-restrictions">optional</a>), * or if the specified collection is null * @see Collection#contains(Object) */ public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, false); }
首先对集合c转进行NonNull校验，然后使用batchRemove方法进行移除；点进去batchRemove：
private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } 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; }
本质上是将elementData进行一次遍历，将集合c中不包含的元素依次重新放入elementData即可，然后将最后数量为c的size的元素置为null；也涉及到元素的移动，不过只需一次遍历即可；
clear()
点进去clear方法
/** * Removes all of the elements from this list. The list will * be empty after this call returns. */ public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }
将所有元素置为null即可；
LinkedList移除元素
首先在主函数中调用LinkedList的有参构造方法生成一个List实例list（若生成LinkedList实例，则有更多关于队列操作的方法，但在这里我们只对比LinkedList与ArrayList在List上的区别），并且发现共有四种移除元素的方法：
List<String> list = new LinkedList<>(Arrays.asList("A", "B", "C", "D", "E", "F", "G", "H", "I", "J")); list.remove(3); list.remove("H"); list.removeAll(Arrays.asList("F", "G")); list.clear();
remove(int index)
点进去第一个remove方法：
/** * Removes the element at the specified position in this list. Shifts any * subsequent elements to the left (subtracts one from their indices). * Returns the element that was removed from the list. * * @param index the index of the element to be removed * @return the element previously at the specified position * @throws IndexOutOfBoundsException {@inheritDoc} */ public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }
首先检验index是否合法，然后使用unlink方法来移除元素。点进去unlink：
/** * Unlinks non-null node x. */ E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }
仅需使要被移除元素的prev.next直接指向被移除元素的next，使要被移除元素的next.prev直接指向被移除元素的prev即可，无需移动元素；
remove(Object o)
点进去第二个remove方法：
/** * Removes the first occurrence of the specified element from this list, * if it is present. If this list does not contain the element, it is * unchanged. More formally, removes the element with the lowest index * {@code i} such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> * (if such an element exists). Returns {@code true} if this list * contained the specified element (or equivalently, if this list * changed as a result of the call). * * @param o element to be removed from this list, if present * @return {@code true} if this list contained the specified element */ 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; }
使用遍历的方式去寻找该对象，发现第一个与该对象相等的元素，使用unlink方法进行移除，并返回true，因此该方法只能移除第一个与该对象相等的元素。无需移动任何元素；
removeAll(Collection<?> c)
点进去removeAll方法
/** * {@inheritDoc} * * <p>This implementation iterates over this collection, checking each * element returned by the iterator in turn to see if it's contained * in the specified collection. If it's so contained, it's removed from * this collection with the iterator's <tt>remove</tt> method. * * <p>Note that this implementation will throw an * <tt>UnsupportedOperationException</tt> if the iterator returned by the * <tt>iterator</tt> method does not implement the <tt>remove</tt> method * and this collection contains one or more elements in common with the * specified collection. * * @throws UnsupportedOperationException {@inheritDoc} * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} * * @see #remove(Object) * @see #contains(Object) */ public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); boolean modified = false; Iterator<?> it = iterator(); while (it.hasNext()) { if (c.contains(it.next())) { it.remove(); modified = true; } } return modified; }
首先对集合c转进行NonNull校验，然后使用Iterator进行遍历，移除所有集合c包含的元素；无需对元素进行移动；
clear()
点进去clear方法
/** * Removes all of the elements from this list. * The list will be empty after this call returns. */ public void clear() { // Clearing all of the links between nodes is "unnecessary", but: // - helps a generational GC if the discarded nodes inhabit // more than one generation // - is sure to free memory even if there is a reachable Iterator for (Node<E> x = first; x != null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; }
遍历将所有元素以及元素的prev和next置为null即可；
结论
1.ArrayList应尽量避免移除元素操作，因为移除元素需要复制移动一次被移除元素之后的数据，所需时间较长；
2.如ArrayList无法避免移除元素操作，应尽量将多个要移除的元素形成一个集合，使用removeAll(Collection<?> c)方法进行移除，因为只会移动一次数据，可以少花费时间；
3.对于需要经常移除元素的场景，应尽量使用LinkedList来实现，所需时间复杂度较低；
