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

Myth丶恋晨 2022-07-29 11:57 209阅读 0赞

## 回顾 ##

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

详细内容参见[《Java基础——集合》][Java]

先看下关系图：  
![这里写图片描述][20160417150254020]

## 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。  
  
![这里写图片描述][20160417150837866]

下面来看下代码

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 \{\}

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

![这里写图片描述][20160417153812549]

代码实现如下

//在指定位置添加元素
     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次

![这里写图片描述][20160417155217697]

循环10W次

![这里写图片描述][20160417155308525]

循环100W次

等一下……  
等一下……  
再等一下……  
出去接杯水……

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

![这里写图片描述][20160417160310451]

嗯……这篇差不多了，over

[Java]: http://blog.csdn.net/u010066934/article/details/50610659
[20160417150254020]: /images/20220724/301e19cd9eaa4b1a98d2faa8cfae34aa.png
[20160417150837866]: /images/20220724/2c02be8cc56f453d8552f481c3c93407.png
[20160417153812549]: /images/20220724/9f9c6abc7d034117821d739a9882e7d9.png
[20160417155217697]: /images/20220724/083a3cd06aa345ee9ad0d1e796e4a85b.png
[20160417155308525]: /images/20220724/8a1ade603b7c4695a95d10fe324e2337.png
[20160417160310451]: /images/20220724/dbc6e79c9baf4dd5943d753569c83061.png