JAVA List之AarrayList、LinkedList、Vector、Stack详细介绍

时间:2020-9-6 作者:admin


一、List常用的实现

List的常见的容器有 ArrayList、LinkedList、Vector、Stack,下面对
每个实现类的特点和实现进行分析。

二、AarrayList

1) 概述

是底层用数组来实现的存储容器,线程是不安全的。

2) 特点

a. 底层实现是通过数组
b. 查询效率高、增删效率低
c. 线程是不安全
d. 元素是有序的,可以包含重复元素

3) 问答

Q: 大家肯定会有这么一个疑问,既然是数组实现的话,那么数组长度是固定的,Arralist是怎么实现动态扩容的?
A: 通过观察源码分析是其实是通过数组的拷贝来实现的,ArrayList 内部会维护一个 Object[] 对象,并默认初始值为10,当超过这个值的时候,会通过拷贝旧的数组,来实现动态扩容。下面是具体实现的源码。

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    //  >> 1 右移操作 相当于 n/2   新数组的长度 为 旧数组的长度 + 旧数组长度/2
    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);
}

三、LinkedList

1) 概述

是底层用双向链表实现的存储容器,线程是不安全的,实现了Deque 和 List接口。

2) 特点

a.底层实现是双向链表,这代表增删效率高。
b.实现了 Deque 接口, 提供了对两端元素操作的方法,意味着可以当做 FIFO (先进先出) 队列 、LIFO(后进先出)栈使用。
c.线程是不安全的。
d.元素是有序的,可以包含重复元素

3)问答

Q: 都说是双向链表结构,那么到底他内部是怎么维护这个结构的呢?
A: Linked内部创建了一个维护 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 在内部维护了 first 首元素 和 last 尾元素,所以可以在内部方法中获得 首元素和尾元素。

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

在 调用add 方法的时候,尾元素添加为当前元素的的上一个元素 ,并设置上一个元素的下一元素为当前元素

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++;
}

四、Vector

1)概述

底层是数组结构,但是线程相对安全的容器。

2)特点

a. 底层是通过数组实现
b. 线程是相对安全的
c. 是有有序的,可以重复
d.实现了RandmoAccess接口,即提供了随机访问功能

3)问答

(1) Q:vector是怎么保证线程安全的呢
A:vector 在add 、remove上都加了 synchronzied 关键字来保证线程安全。但是这个安全是相对安全,下面这个例子有会体现vector线程不安全的的情况

public static void main(String[] args) {
    Vector vector = new Vector();
    for (int i = 0; i < 2; i++) {
        new Thread(()->{
            int count=0;
            while(count<10){
                vector.add(count);
                System.out.println("当前线程:"+Thread.currentThread().getName()+",vector大小:"+vector.size());
                count++;
            }
        }).start();
    }
}

打印结果,会出现大小的相同的情况,这是为什么呢,因为size和add方法是线程安全的,但是当两者结合会出现线程不安全的情况,比如 A、B线程 同时调用add ,然后size方法,可能出现 A add 完成后,B获得锁 ,执行 add 和size 方法,再 A线程 执行 size 方法 ,这时候就会导致线程不安全。

当前线程:Thread-1,vector大小:2
当前线程:Thread-0,vector大小:2

五、Stack

1) 概述

继承Vector,代表底层是数组的容器,但是他具有先进后出(FILO) 的特性

2)特点

a. 底层是数组
b. 具有先进后出(FILO)的特点,与栈相似。
c. 线程是相对安全的。

3)常用 API

             boolean       empty() // 判断栈是否为空
synchronized E             peek() // 返回栈顶元素,不执行删除操作
synchronized E             pop() //返回栈顶元素,并将其从栈中删除
             E             push(E object) // 将元素存入栈顶
synchronized int           search(Object o) // 查找“元素o”在栈中的位置:由栈底向栈顶方向数

4) 源码分析

(1)push 方法与 ArrayList和 Vector 相似,都是通过grow 实现动态扩容。

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

(2)pop 方法,是调用peek方法 返回当前数组下标最后的元素,然后将数组最后一位 置空。

public synchronized void removeElementAt(int index) {
    modCount++;
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                 elementCount);
    }
    else if (index < 0) {
        throw new ArrayIndexOutOfBoundsException(index);
    }
    // elementCount 是当前数组大小
    int j = elementCount - index - 1;
    // 如果当前移除对象索引不是最后一位,则进行数组拷贝,当指定移除元素时会进入判断
    if (j > 0) {
        // 从指定元素位置开始拷贝后面元素 比如 1 2 3 4 5 指定元素为3 则替换成 1 2 4 5 5
        System.arraycopy(elementData, index + 1, elementData, index, j);
    }
    elementCount--;
    // 将数组最后一位 置空
    elementData[elementCount] = null; /* to let gc do its work */
}

六、总结

最后总结下List各个实现类的特点
(1)保证线程相对安全的:Vector、Stack
(2)底层实现是数组的:ArrayList 、Vector、Stack,底层实现是双向链表的:LinkedList
(3)查询速度快:ArrayList、Vector、Stack ,增删速度快 LinkedList
(4)Vector可以当作 队列和栈使用,Stack可以当作使用

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。