线性集合:ArrayList,LinkedList,Vector/Stack

发布于:2024-05-16 ⋅ 阅读:(69) ⋅ 点赞:(0)

共同点:都是线性集合

ArrayList

ArrayList 底层是基于数组实现的,并且实现了动态扩容(当需要添加新元素时,如果 elementData 数组已满,则会自动扩容,新的容量将是原来的 1.5 倍),来看一下 ArrayList 的部分源码(PS:以下代码均来自Java8,不同版本可能存在细微差距)。

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

    private static final int DEFAULT_CAPACITY = 10; // 默认容量

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    transient Object[] elementData; // 存储元素的数组,数组类型:Object

    private int size; // 列表的大小,即列表中元素的个数

ArrayList 还实现了 RandomAccess 接口,这是一个标记接口

public interface RandomAccess {
}

内部是空的,标记“实现了这个接口的类支持快速(通常是固定时间)随机访问”。快速随机访问是什么意思呢?就是说不需要遍历,就可以通过下标(索引)直接访问到内存地址。而 LinkedList 没有实现该接口,表示它不支持高效的随机访问,需要通过遍历来访问元素。

ArrayList 还实现了 Cloneable 接口,并且重写了 Object 类的 clone() 方法,但只是浅拷贝,还是要根据需求使用。

public Object clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

ArrayList 还实现了 Serializable 接口,支持序列化:

但是关键字段 elementData 使用了 transient 关键字修饰,这个关键字的作用是,让它修饰的字段不被序列化。

看到这里是不是心里出现了很多问好?

我们这样来看:elementData 是一个数组,数组是定长的,如果一个新创建的ArrayList,并且我们只往里添加了2个元素,如果我们默认序列化就会多序列化8个空的内存空间,我们再反序列化出来的时候需要更大的空间去接收这个数组。如下例子中可以更好的反应该问题,可能出现很大的bug:

public class Main {

    public static void main(String[] args) throws Exception {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 100000; i++) {
            list.add(i);
        }
        System.out.println(list.size());
        list.clear();
        Class<? extends List> listClass = list.getClass();
        Field field = listClass.getDeclaredField("elementData");
        field.setAccessible(true);
        Object[] o = (Object[]) field.get(list);
        System.out.println(o.length);
    }
}

输出如下:
100000
106710

 于是,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();
    }
}

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

从源码中可以看出序列化和反序列化时,只保存了list的大小和所有元素。

还需要注意 ArrayList 在序列化时,不允许有并发的修改操作。

Vector/Stack

Vector 也是基于数组实现的,但是是线程安全的,其他和 ArrayList 基本没有区别,源码注释中有句话也可以看出

{@code Vector} is synchronized.  If a thread-safe
implementation is not needed, it is recommended to use {@link
ArrayList} in place of {@code Vector}.

// Vector的序列化和反序列化的方法与ArrayList略有差异
private void readObject(ObjectInputStream in)
        throws IOException, ClassNotFoundException {
    ObjectInputStream.GetField gfields = in.readFields();
    int count = gfields.get("elementCount", 0);
    Object[] data = (Object[])gfields.get("elementData", null);
    if (count < 0 || data == null || count > data.length) {
        throw new StreamCorruptedException("Inconsistent vector internals");
    }
    elementCount = count;
    elementData = data.clone();
}

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
    final java.io.ObjectOutputStream.PutField fields = s.putFields();
    final Object[] data;
    synchronized (this) {
        fields.put("capacityIncrement", capacityIncrement);
        fields.put("elementCount", elementCount);
        data = elementData.clone();
    }
    fields.put("elementData", data);
    s.writeFields();
}

 Stack 继承了 Vector,同时Stack添加了 push/pop/peek 等方法,实现了后进先出(LIFO)。

LinkedList

LinkedList 是一个继承自 AbstractSequentialList 的双向链表,同时实现了 Deque 双向队列接口,因此它也可以被当作堆栈、队列或双向队列进行操作。

 部分源码

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0; // 表示链表中的节点个数

    transient LinkedList.Node<E> first; // 链表中的第一个节点

    transient LinkedList.Node<E> last; // 链表中的最后一个节点

可以看到 LinkedList 同样实现了 Serializable 接口,支持序列化。但是上面源码中 LinkedList 的所有属性都是 transient 修饰的,这又让我们想到了 ArrayList 的序列化实现,果然找到了writeObject和readObject方法的实现:

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 (LinkedList.Node<E> x = first; x != null; x = x.next)
        s.writeObject(x.item);
}

@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());
}

仔细琢磨,发现不仅尽可能少的占用存储空间,反序列化时还巧妙的恢复了原来的顺序。