戏说list中的ArrayList和LinkedList，在for循环中删除，如同一把利刃，耍不好，还自费武功！
ClEyes-KeThink
787
发布于 未知归属地
Java学习分享

ArrayList

ArrayList没有被任何多线程关键字修饰，但底层对象数组elementData被关键字transient修饰：

transient关键字修饰字段表示该属性不会被序列化，但ArrayList实现Serializable接口？

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

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

ArrayList的数组是动态扩增的，并不是所有被分配的内存空间都存储数据
如果采用外部序列化法实现数组的序列化，会序列化整个数组，导致没有存储数据的内存空间被序列化；
所以需要transient修饰数组，防止数组被其他外部方法序列化！

ArrayList内部提供两个私有方法writeObject()和readObject()来自我完成序列化与反序列化，从而在序列化与反序列化数组时节省了空间和时间！

  private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

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

    /**
     * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
     * deserialize it).
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in capacity
        s.readInt(); // ignored

        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            int capacity = calculateCapacity(elementData, size);
            SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

ArrayList在大量新增元素的场景下效率一定会变慢？

当ArrayList新增元素时，会先确认容量大小，如果容量够大，就不用进行扩容；
如果容量不够大，就会按照原来数组的1.5倍进行动态扩容，将整个数组复制到新分配的内存地址。
在初始化ArrayList时，容量默认为10，也可以通过构造函数合理指定数组初始大小，有助于减少数组扩容次数，提高系统性能。
因此，在ArrayList初始化时根据存储数据的规模指定数组容量大小，并且在添加元素时只在数组末尾添加元素，那么ArrayList在大量新增元素的场景下性能并不会变差，反而比其他List集合的性能要好

LinkedList

LinkedList基于双向链表实现，有三个transient成员变量：first、last、size（头结点、尾结点、容量）

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

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

被transient修饰的原因：在序列化时不会只对头尾进行序列化，所以LinkedList也是自行实现readObject()和writeObject()进行序列化与反序列化!

  private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out any hidden serialization magic
        s.defaultWriteObject();

        // Write out size
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (Node<E> x = first; x != null; x = x.next)
            s.writeObject(x.item);
    }

    /**
     * Reconstitutes this {@code LinkedList} instance from a stream
     * (that is, deserializes it).
     */
    @SuppressWarnings("unchecked")
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden serialization magic
        s.defaultReadObject();

        // Read in size
        int size = s.readInt();

        // Read in all elements in the proper order.
        for (int i = 0; i < size; i++)
            linkLast((E)s.readObject());
    }

ArrayList和LinkedList新增、删除

ArrayList和LinkedList新增、删除元素花费时间：

从集合头部位置新增、删除元素：ArrayList > LinkedList
从集合中间位置新增、删除元素：ArrayList < LinkedList
从集合尾部位置新增、删除元素：ArrayList < LinkedList

解释：

ArrayList添加元素到头部，需要对头部以后的数据进行复制重排，效率很低；
LinkedList添加元素到头部，在添加元素之前的循环查找操作较少，效率较高。

ArrayList添加元素到中间，同样有部分数据需要复制重排，效率较低；
LinkedList添加元素到中间，在添加之前先循环查找接近size/2次，效率很低。

ArrayList添加元素到尾部，不需要复制重排数据，效率非常高；
LinkedList添加元素到尾部，不需要循环查找元素，但LinkedList多了new Node对象，以及变换指针指向对象的过程，所以效率要低于ArrayList

ArrayList若有动态扩容的情况，效率也会降低
ArrayList和LinkedList删除元素操作和添加元素操作很接近，是一样的原理

ArrayList和LinkedList遍历元素花费时间：

for(;;)循环：ArrayList < LinkedList
迭代器迭代循环、foreach语法糖：ArrayList≈LinkedList

解释：

从for(;;)循环索引查找的角度，LinkedList查询效率低，ArrayList查询效率高；
切忌使用for(;;)循环遍历LinkedList，性能最差。

从iterator迭代器迭代循环遍历的角度，两者查询效率都很高，性能差不多相当；
推荐使用iterator迭代器循环遍历LinkedList

ArrayList基于数组实现，实现RandomAccess接口标志，可以实现快速随机访问，通过索引一次性O(1)定位元素，所以for(;;)循环性能是最好的！

LinkedList基于双向链表实现，通过size/2分为前后两个半段，来循环查找到对应元素；
在for(;;)循环遍历时，平均每次循环都会遍历1/4个List，严重影响效率！

ArrayList使用循环遍历做删除操作应该注意的问题：

// 写法1：正确
public static void remove(ArrayList<String> list)  {
        Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            String str = it.next();
            if (str.equals("b")) {
                it.remove();
            }
        }
    }
// 写法2：造成modCound != exceptedModeCount，进而抛出异常
public static void remove(ArrayList<String> list) {
        for (String s : list) {
            if (s.equals("b")) {
                list.remove(s);
            }
        }
    }

第一个写法是正确的;
第二个虽然用的是foreach语法糖，遍历的时候用的底层也是迭代器遍历，但是在remove操作时使用的是原始数组list的remove()方法，而不是迭代器的remove()方法；这样就会造成modCound != exceptedModeCount，进而抛出异常;

阿里Java规约提过：在集合中进行remove操作时，不要在 foreach循环里进行元素的remove/add操作。
remove元素请使用Iterator方式，如果并发操作，需要对Iterator对象加锁。

评论 (2)