Java中常见数据结构List之ArrayList

这里主要包含ArrayList和LinkedList.

关于Java中的集合内容，感觉都已经被写烂了，我这里主要是做个复习，再从扒下源代码，尽量用最直白的语言把里面的核心内容记录下来。仅此而已。

首先放一个Collection下的UML图：(此图是idea通过diagram功能生成的，基于JDK7)

Java中常见数据结构List之ArrayList

一、ArrayList

1， for-each原理：

0、在编译的时候编译器会自动将对for这个关键字的使用转化为对目标的迭代器的使用，这就是foreach循环的原理

1、ArrayList之所以能使用foreach循环遍历，是因为ArrayList所有的List都是Collection的子接口，而Collection是Iterable的子接口，ArrayList的父类AbstractList正确地实现了Iterable接口的iterator方法。之前我自己写的ArrayList用foreach循环直接报空指针异常是因为我自己写的ArrayList并没有实现Iterable接口

2、任何一个集合，无论是JDK提供的还是自己写的，只要想使用foreach循环遍历，就必须正确地实现Iterable接口。

2，集合中的 fail-fast iterator：

Iterator 是工作在一个独立的线程中，并且拥有一个 mutex 锁。 Iterator 被创建之后会建立一个指向原来对象的单链索引表，当原来的对象数量发生变化时，这个索引表的内容不会同步改变，所以当索引指针往后移动的时候就找不到要迭代的对象，所以按照 fail-fast 原则 Iterator 会马上抛出 java.util.ConcurrentModificationException 异常。

当使用foreach遍历一个list元素时，因为foreach底层实现是使用iteator中的hasNext, next等，源码中next执行时会checkForComdification：

Java中常见数据结构List之ArrayList

3， ArrayList初始值大小是10，每次扩容是增加2倍。优缺点是：

//默认的构造函数， 当然还有构造函数是可以指定大小的

public ArrayList() {

    this(10);

}

//jdk7中的扩容代码， 我看了jdk6中是扩容1.5倍的， 这里有点差别

private void grow(int minCapacity) {

    // overflow-conscious code

    int oldCapacity = elementData.length;

    int newCapacity = oldCapacity + (oldCapacity >> 1);

    if (newCapacity - minCapacity < 0)

        newCapacity = minCapacity;

    if (newCapacity - MAX_ARRAY_SIZE > 0)

        newCapacity = hugeCapacity(minCapacity);

    // minCapacity is usually close to size, so this is a win:

    elementData = Arrays.copyOf(elementData, newCapacity);

}

ArrayList的优点：

1、ArrayList底层以数组实现，是一种随机访问模式，再加上它实现了RandomAccess接口，因此查找也就是get的时候非常快

2、ArrayList在顺序添加一个元素的时候非常方便，只是往数组里面添加了一个元素而已

ArrayList的缺点：

1、删除元素的时候，涉及到一次元素复制，如果要复制的元素很多，那么就会比较耗费性能

2、插入元素的时候，涉及到一次元素复制，如果要复制的元素很多，那么就会比较耗费性能

因此，ArrayList比较适合顺序添加、随机访问的场景。

4，细节：为什么ArrayList的elementData是用transient修饰的？

ArrayList实现了Serializable接口，这意味着ArrayList是可以被序列化的，用transient修饰elementData意味着我不希望elementData数组被序列化。这是为什么？因为序列化ArrayList的时候，ArrayList里面的elementData未必是满的，比方说elementData有10的大小，但是我只用了其中的3个，那么是否有必要序列化整个elementData呢？显然没有这个必要，因此ArrayList中重写了writeObject方法：

private transient Object[] elementData;

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 array length

    s.writeInt(elementData.length);

    // 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();

    }

}

每次序列化的时候调用这个方法，先调用defaultWriteObject()方法序列化ArrayList中的非transient元素，elementData不去序列化它，然后遍历elementData，只序列化那些有的元素，这样：

1、加快了序列化的速度

2、减小了序列化之后的文件大小

秒客网

Java中常见数据结构List之ArrayList

相关文章