Java集合（2）——深入理解ArrayList、Vector和LinkedList

回顾

Java集合主要分为两个体系结构，Collection和Map。这篇博客主要介绍Collection子接口List下的三个经常使用的实现类：ArrayList、Vector和LinkedList。

先看下关系图：

1、ArrayList

这是List最常用的实现类，想一想为什么他最常用？

Array，在java中意为“数组”。猜想ArrayList和数组应该关系很密切，其实ArrayList可以看作是一个可以改变大小的数组。

举个简单的例子吧，看下他的使用：

       ArrayList<String> list1 = new ArrayList<>();

        list1.add("a");

        list1.add("b");

        list1.add("c");

        list1.set(2, "d");

        Iterator<String> iter = list1.iterator();

        while (iter.hasNext()) {

            System.out.println(iter.next());

        }

之后，我们就从源码看看他是如何设计的吧。

1）构造函数

提示：

默认ArrayList长度为10；

用于保存数据的elementData本身就是个Object[]；

ArrayList提供了三种构造函数，具体逻辑可以看下面的代码。

public class ArrayList<E> extends AbstractList<E>

        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

{

   //默认容量为10

    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] EMPTY_ELEMENTDATA = {};

    //调用无参数构造函数时，给一个空数据

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

   //保存元素的数据

    transient Object[] elementData; 

    //1、无参数构造函数，默认空数组

     public ArrayList() {

        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

    }

    //2、给定初始容量的构造函数

     public ArrayList(int initialCapacity) {

        //大于0时，创建一个Object数据，长度为传入的容量值

        if (initialCapacity > 0) {

            this.elementData = new Object[initialCapacity];

        } else if (initialCapacity == 0) {

            //等于0时，给一个空数组

            this.elementData = EMPTY_ELEMENTDATA;

        } else {

            //其他抛出容量不合法异常

            throw new IllegalArgumentException("Illegal Capacity: "+

                                               initialCapacity);

        }

    }

    //3、给定集合对象的构造函数

     public ArrayList(Collection<? extends E> c) {

        //放入数组

        elementData = c.toArray();

        //数组长度不等于0时，将进行复制

        if ((size = elementData.length) != 0) {

            // c.toArray might (incorrectly) not return Object[] (see 6260652)

            if (elementData.getClass() != Object[].class)

                elementData = Arrays.copyOf(elementData, size, Object[].class);

        } else {

            否则，返回空数组

            this.elementData = EMPTY_ELEMENTDATA;

        }

    }

}

2）动态扩充

在添加元素时，会涉及到扩充的问题，其中核心方法是grow()。

提示：

“>>” 右移运算符：

在二进制中比较容易理解，这里不是重点，大致相当于值的二分之一。因此，有的书上会说ArrayList扩容一次会增加原来的一半，就是从这里看出来的。

 private void grow(int minCapacity) {

        //获取原来的容量，即原来数组的长度

        int oldCapacity = elementData.length;

       //新容量

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

        if (newCapacity - minCapacity < 0)

            newCapacity = minCapacity;

        if (newCapacity - MAX_ARRAY_SIZE > 0)

            newCapacity = hugeCapacity(minCapacity);

       //复制数组

        elementData = Arrays.copyOf(elementData, newCapacity);

    }

2、Vector

Vector和ArrayList几乎完全相同，直接看源码就知道了，瞬间有种剽窃的赶脚……

但其实不是的，Vector是比ArrayList出现的要早的，也正是因为这样，很多方法都比较陈旧了，并不推荐适用男。

这里贴了一小部分代码，和ArrayList几乎一样，就不占用空间了，有兴趣可以去java.util.Vector里面翻一翻。

public class Vector<E>

    extends AbstractList<E>

    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

{

   protected Object[] elementData;

   protected int elementCount;

   public Vector() {

        this(10);

    }

   public Vector(int initialCapacity, int capacityIncrement) {

        super();

        if (initialCapacity < 0)

            throw new IllegalArgumentException("Illegal Capacity: "+

                                               initialCapacity);

        this.elementData = new Object[initialCapacity];

        this.capacityIncrement = capacityIncrement;

    }

当然Vector也有一些自己的特点，随便拿几个方法来看看。他的方法中几乎都用到了synchronized关键字，开销会比较大，而且运行会比较慢。

 public synchronized void copyInto(Object[] anArray) {

        System.arraycopy(elementData, 0, anArray, 0, elementCount);

    }

     public synchronized void setSize(int newSize) {

     }

      public synchronized int capacity() {

        return elementData.length;

    }

    //数组个数

      public synchronized int size() {

        return elementCount;

    }

    //获取元素

    public Enumeration<E> elements() {

        return new Enumeration<E>() {

            int count = 0;

            public boolean hasMoreElements() {

                return count < elementCount;

            }

            public E nextElement() {

                synchronized (Vector.this) {

                    if (count < elementCount) {

                        return elementData(count++);

                    }

                }

                throw new NoSuchElementException("Vector Enumeration");

            }

        };

    }

3、LinkedList

是一个双链表，在add和remove时比ArrayList性能好，但get和set时就特别慢了。

恶补下：

双向链表，链表的一种。每个数据结点中都有两个指针，分别指向直接前驱和直接后继。因此，我们可以方便的访问他的前驱结点和后继结点。

下图是一个双向链表的图，element为元素，pre指向直接前驱（前一个元素），next指向直接后继（后一个元素）。而LinkedList还不只是双向链表，他是双向循环链表。也就是第一个pre指针指向最后一个节点，最后一个节点的next指针指向第一个节点，形成一个环路，而不是下图中的Null。

下面来看下代码

public class LinkedList<E>

    extends AbstractSequentialList<E>

    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{

    //元素个数

    transient int size = 0;

    //相当于pre指针

    transient Node<E> first;

    //相当于next指针

    transient Node<E> last;

    //Node内部类（双链表结构）

    private static class Node<E> {

        E item;

        Node<E> next;

        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {

            this.item = element;

            this.next = next;

            this.prev = prev;

        }

    }

    ......

}

Tips:

Deque，他是双端队列的接口，支持在两端插入和移除元素。

public interface Deque extends Queue {}

那么如何进行操作呢？这里以在中间位置添加元素为例。

代码实现如下



  //在指定位置添加元素

 public void add(int index, E element) {

        //检查索引是否有效

        checkPositionIndex(index);

        //索引值等于集合大小，直接添加在末尾

        if (index == size)

            linkLast(element);

        else

            linkBefore(element, node(index));

    }

    //返回索引处的非空Node

     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;

        }

    }

    //中间插入元素（核心方法！！！！）

     void linkBefore(E e, Node<E> succ) {

        final Node<E> pred = succ.prev;

        final Node<E> newNode = new Node<>(pred, e, succ);

        succ.prev = newNode;

        if (pred == null)

            first = newNode;

        else

            pred.next = newNode;

        size++;

        modCount++;

    }

对于性能这块，在大数据量重复试验下得出的结论才比较有说服力，小编就随手贴上自己的测试结果，有兴趣看看就可以了。

测试代码差不多都是这样子的……

ArrayList<Integer> arrayList = new ArrayList<Integer>();

        LinkedList<Integer> linkedList = new LinkedList<Integer>();

        // add操作

        int count = 100000;

        System.out.println("ArrayList--add()-------------------");

        long startTime = System.nanoTime();

        for (int i = 0; i < count; i++) {

            arrayList.add(i);

        }

        long endTime = System.nanoTime();

        System.out.println(endTime - startTime + "--------");

        System.out.println("LinkedList--add()-------------------");

        startTime = System.nanoTime();

        for (int i = 0; i < count; i++) {

            linkedList.add(i);

        }

        endTime = System.nanoTime();

        System.out.println(endTime - startTime + "--------");

循环1W次

循环10W次

循环100W次

等一下……

等一下……

再等一下……

出去接杯水……

结果还是这个样子，直接给个图吧，LinkedList还没get出来(⊙﹏⊙)b

嗯……这篇差不多了，over

巴特西

Java集合（2）——深入理解ArrayList、Vector和LinkedList

回顾

1、ArrayList

2、Vector

3、LinkedList

最新文章

热门文章