Java-08：Vector、ArrayList、LinkedList有何区别？

迷南。 2023-01-09 03:57 120阅读 0赞

三个集合都是我们常用的数据集合，在看它们之间的区别前，我们先来看看它们的继承结构。

#### 1、继承结构图 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4NTM1_size_16_color_FFFFFF_t_70_pic_center]

Collection接口是层次结构中的根接口，构成Collection的单元称为元素。Collection接口提供了添加元素，删除元素，管理数据的方法 。

List接口表示这是一个元素有序，可以重复，可以为null的集合，那它又是凭借什么实现有序的。List数据结构在内存中会开辟一块连续的空间，然后将内存地址与索引对应。

Queue接口在Collection基础上添加操作队列方法，Deque接口是一个双向队列，同时也添加相应的方法。

#### 2、读写效率 ####

我们可以看出ArrayList和Vector是一个有序的数组，底层数据结构为数组；LinkedList是一个有序的双向链表，底层的数据为链表。

那既然是数组和链表，在数据的插入、删除，就会有自己的优势和劣势。

*  数组在中间插入数据时，会将插入位置之后的数据向后移动，同理删除中间数据，会将后面的数据前移，不过在访问数据时，可以依据随机访问的特性能很高效地访问；
 *  链表在插入或删除数据时，只需要修改next的指向就能很高效插入数据，不过在查询数据时，只能从头部或者尾部开始逐步遍历，直到遍历完链表或找到。

我们就要根据具体场景来选择数据结构，如果添加/删除数据多，查询少，链表再适合不过；如果查询多，添加/删除数据少，那就选择数组。

Vector和ArrayList最根本的区别是Vector是一个线程安全的集合，它的所有方法上都有着`ssynchronized`关键字，不过保证线程安全，避免不了额外的性能消耗，在不是多并发的场景下，ArrayList合适的多。

看完读写效率方面的差距，我们再来看看，再插入数据时，集合的具体表现。

#### 3、读写机制 ####

我们需要关注的点有存放数据的结构，初始容量，如何扩容，添加数据时的操作

##### 3.1 ArrayList #####

**存放数据的结构？**

transient Object[] elementData;

在ArrayList中，我们能很容易发现这个存放数据的结构`elementData`，当时为啥它需要`transient`关键字修饰呢。

`transient`关键字只能修饰成员变量，在对象进行序列化时，由该关键字修饰的成员变量不会序列化。但是elementData不是存放数据的嘛，不能序列化，我如何将它持久化或者传输呢。

elementData被transient关键字修饰的关键所在：例如Object\[\]长度为20，但是只存放了10个数据，还会有10个空位，Java不想让这10个空位也序列化，一起传输过去。所以ArrayList中提供了writeObject和readObject方法来序列化和反序列化。

**数组的初始容量？**

那我们就来看下它的构造函数

// 没有指定大小
        public ArrayList() { 
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    
    	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
    
    	// 传入指定大小
        public ArrayList(int initialCapacity) { 
            if (initialCapacity > 0) { 
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) { 
                this.elementData = EMPTY_ELEMENTDATA;
            } else { 
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }
    
    	private static final Object[] EMPTY_ELEMENTDATA = { };

*  第一种情况：空参构造器，elementData被赋值空数组，数组的长度为0
 *  第二种情况：传入指定大小，如果initialCapacity为0，则被赋值空数组；如果initialCapacity>0，则创建一个initialCapacity大小的数组。

那`EMPTY_ELEMENTDATA`和`DEFAULTCAPACITY_EMPTY_ELEMENTDATA`又是什么情况呢？后面揭晓！

**数组怎么进行扩容？**

private static final int DEFAULT_CAPACITY = 10;
    
    	// mincapacity = size + 1传入
    	private void ensureCapacityInternal(int minCapacity) { 
            // 如果是由空参构造器构造出来ArrayList实例，
            // 从DEFAULT_CAPACITY和minCapacity选择一个大的
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    
            ensureExplicitCapacity(minCapacity);
        }
    
        private void ensureExplicitCapacity(int minCapacity) { 
            // 集合的总操作+1
            modCount++;
            // 如何数值正确，继续执行
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
        private void grow(int minCapacity) { 
            // 
            int oldCapacity = elementData.length;
            // 新容量为1.5倍的原始数值
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            // 将minCapacity与newCapacity进行比较，同时注意容量数值的边界
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // 复制数组到新数组
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    
        private static int hugeCapacity(int minCapacity) { 
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }

我们来总结下，ArrayList如何扩容？

*  将size+1作为最小容量闯入扩容方法，如果是空参构造器生成的实例，则从DEFAULT\_CAPACITY和size+1中选择一个大的数
 *  生成一个newCapacity，大小为1.5倍的旧容量，将newCapacity与minCapacity进行比较取较大值
 *  如果比较出来的数值大于Integer.MAX\_VALUE - 8，那数组的新容量为Integer.MAX\_VALUE
 *  赋值旧数组的数据到新数组

**add操作？**

public boolean add(E e) { 
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }

知道扩容方法的原理后，add方法就很明显了。

##### 3.2 LinkedList #####

**存放数据的结构？**

链表嘛，还是双向的，我们就很容易能脑补到具体的情景

先来看下节点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;
            }
        }

在根据LinkedList中两个引用，一个指向链表头，一个指向链表结尾

transient Node<E> first;
    
        transient Node<E> last;

**如何添加数据？**

public boolean add(E e) { 
            linkLast(e);
            return true;
        }
    
        void linkLast(E e) { 
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(l, e, null);
            last = newNode;
            // 考虑空链表的情况
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }
    
        private void linkFirst(E e) { 
            final Node<E> f = first;
            final Node<E> newNode = new Node<>(null, e, f);
            first = newNode;
            // 考虑空链表的情况
            if (f == null)
                last = newNode;
            else
                f.prev = newNode;
            size++;
            modCount++;
        }

简单看一下，我们发现，添加的数据的思路很简单，如果脑补不出来，建议手写一个链表操作，很容易，也会很深刻的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4NTM1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/5757563fde04406b9bb87e38d49133c9.png