Java集合之List篇(知识点与面试题)

在面试中，集合应当是Java基础中必问的一块了，无论是Map，还是List、Set，总有一款会问到。这一篇就来聊聊这个List的一些常见问题。

我还记得校招有一次面试的时候，面试官就问我LinkedList底层是什么？
我就说LInkedList的底层是双向链表。
面试官：你确定么？
“对啊，LinkedList底层就是双向链表啊。”
“ 你再好好想想。”
我：？？？？是我记错了么？

这特喵就是双向链表啊。没毛病啊，就是双向链表。

后来我查了下，确实是双向链表。可能是这个面试官故意搞事情。

好了，废话也就不那个多说，本文主要围绕ArrayList、LinkedList、Vector这三个点来看下常见的一些问题。

ArrayList

什么是Arraylist

ArrayList是数组列表，可以用来存储数据，他的底层实现是Object类型的数组，因此各种数据类型的数值都可以存储。

因为底层是数组，数组在内存中是连续存储的，因此它对元素的查找速度是比较快的。但是新增与删除元素可能会涉及到生成新的数组，所以增加与删除元素的速度是比较慢的。ArrayLsit的使用频率是最高的。

ArrayList是不是线程安全的

ArrayList不是线程安全的。可以看一下ArrayList是怎么添加数据的：

  /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

在ArrayList添加数据的时候，只是判断下是否需要扩容，然后就写入数据，数据的操作没有加锁，因此不是线程安全的。

如果想保证线程安全，可以使用Vector。Vector是在对数据的操作时，都给方法加上了synchronized锁。

当然了，除了使用Vector，也可以使用Collections.synchronizedList来实现线程安全：

Collections.synchronizedList(new ArrayList<>())

Collections.synchronizedList也是在对数据的操作时加上synchronized锁。

使用CopyOnWriteArrayList：写操作时复制，也能够保证线程安全。

ArrayList插入删除操作一定慢么

这个还是要看具体的情况的。先看下ArrayList是如何删除、添加元素的：

假如原先的集合中有五个元素，要删除第三个，ArrayList是新建一个数组，将前两个元素放到新的集合后，再将第四个、第五个放进新的集合中。所以ArrayList的删除速度慢不慢是取决于它的位置的。如果是在集合的尾部，那肯定不慢，直接去掉就OK了。但是如果在其它位置嘛，那就得新建一个数组了。

那你说说ArrayList是怎么实现的吧，为什么ArrayList就不用创建大小呢

在ArrayList中：定义了两个构造方法：

/**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    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);
        }
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

我们可以在创建ArrayList时不指定大小，这样就会使用第二个构造方法。如果空参或者初始值为0，那么就先创建一个空的数组。只有当添加数据的时候才会去赋予初值10，每次添加值都会先判断，如果不能继续添加，就会触发扩容。

ArrayList是如何扩容的？

ArrayList扩容后的大小等于扩容前大小的1.5倍。比如ArrayList默认大小为10，第一次扩容后大小就是10*(1+.05)，源码：

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

在添加数据的时候会先进行下判断，看是否需要进行扩容（ensureCapacityInternal(size + 1);）

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

不过如果在使用中，还是尽量提前设置一个比较合适的初值，避免因为数组扩容带来一些别的问题。

ArrayList用来做队列合适么？

队列一般是FIFO（先进先出）的，如果用ArrayList做队列，就需要在数组的一端追加数据，在数组的另一端删除数组。可以搭配上面的扩容一块理解，
无论是删除还是增加，总会有一个操作会涉及到新建数组，将原先的数据迁移到新的数组。毕竟扩容是非常花费资源的，所以ArrayList并不适合做队列。

LinkedList

什么是LinkedList

LinkedList也实现了List接口，与ArrayList相比，LinkedList的底层结构是一个双向链表（就是双向链表）。我们都知道，链表在内存中不是连续存储的，他的前一个节点通过指针指向下一个节点。这样的特性也就导致了增加、删除元素不会像数组那般麻烦，他只需要改变指针的指向，就可以完成数据的增加、删除。当然了，作为增加、删除速度快的代价就是查询慢。

LinkedList是否安全

LinkedList同样是线程不安全的，因为他对于数据的操作同样没有加锁。要想保证安全性，同样可以使用synchronizedList。

 Collections.synchronizedList(new LinkedList<>());

是否支持快速随机访问

LinkedList不支持快速随机访问。在ArrayList中，因为它的底层是数组，数组又是连续存储的，所以可以通过指定位置就可以实现快速随机访问。但是LinkedList就不一样了，因为LinkedList又不是连续存储的，无法指定具体位置。

Vector

关于Vector的使用，其实还是比较少的，主要将它与ArrayList在几个方面做一个对比。

1、同步和线程安全

Vector和ArrayList之间的主要区别在于Vector是同步的而ArrayList不是，意思是Vector的方法是同步的，这也就是它为什么是线程安全的并且允许它在多线程和并发环境中安全地使用。而ArrayList的方法不同步，所以不适合在多线程环境中使用。

2、速度和性能

ArrayList比Vector更快。由于Vector在方法上会加锁，加锁与释放锁就会消耗一定的时间。而ArrayList不会对数据的操作加锁，这使得他的速度会快一点，但是它的读写一致安全就不会得到保障。但是在多线程中，如果你只想读数据的话，那么使用ArrayList也是可以的。

3、扩容

只要Vector超过指定的大小，它就会通过capacityIncrement字段中指定的值增加自身容量。ArrayList的初始大小与Vector一样，都是10。但是ArrayList的扩容方式是变为原先的1.5倍。而Vector则是翻倍。

其它

个人感觉最常用的，并且问的多的是Map，其次是List，然后是Set。
关于Map可以看下我的：那些年一起看过的HashMap面试题

Set的一些基础知识：Java集合之Set篇（知识点）