ArrayList、LinkedList与Vector的区别？

典型回答

List主要有ArrayList、LinkedList与Vector几种实现。这三者都实现了List 接口，使用方式也很相似,主要区别在于因为实现方式的不同,所以对不同的操作具有不同的效率。

ArrayList 是一个可改变大小的数组.当更多的元素加入到ArrayList中时,其大小将会动态地增长.内部的元素可以直接通过get与set方法进行访问,因为ArrayList本质上就是一个数组。

LinkedList 是一个双向链表，在添加和删除元素时具有比ArrayList更好的性能，但在get与set方面弱于ArrayList。当然,这些对比都是指数据量很大或者操作很频繁的情况下的对比,如果数据和运算量很小,那么对比将失去意义。

Vector 和ArrayList类似,但属于强同步类。如果你的程序本身是线程安全的(thread-safe,没有在多个线程之间共享同一个集合/对象),那么使用ArrayList是更好的选择。

Vector和ArrayList在更多元素添加进来时会请求更大的空间。Vector每次请求其大小的双倍空间，而ArrayList每次对size增长50%。

而 LinkedList 还实现了Queue和Deque接口,该接口比List提供了更多的方法,包括offer(),peek(),poll()等。

注意: 默认情况下ArrayList的初始容量非常小,所以如果可以预估数据量的话,分配一个较大的初始值属于最佳实践,这样可以减少调整大小的开销。

知识扩展

ArrayList是如何扩容的？

首先，我们要明白ArrayList是基于数组的，我们都知道，申请数组的时候，只能申请一个定长的数组，那么List是如何通过数组扩容的呢？ArrayList的扩容分为以下几步：
1.检查新增元素后是否会超过数组的容量，如果超过，则进行下一步扩容
2.设置新的容量为老容量的1.5倍，最多不超过2^31-1
3.之后，申请一个容量为1.5倍的数组，并将老数组的元素复制到新数组中，扩容完成

如何利用List实现LRU？

LRU，即最近最少使用策略，基于时空局部性原理（最近访问的，未来也会被访问），往往作为缓存淘汰的策略，如Redis和GuavaMap都使用了这种淘汰策略。
我们可以基于LinkedList来实现LRU，因为LinkedList基于双向链表，每个结点都会记录上一个和下一个的节点，具体实现方式如下：

public class LruListCache<E> {private final int maxSize;private final LinkedList<E> list = new LinkedList<>();public LruListCache(int maxSize) {this.maxSize = maxSize;}public void add(E e) {if (list.size() < maxSize) {list.addFirst(e);} else {list.removeLast();list.addFirst(e);}}public E get(int index) {E e = list.get(index);list.remove(e);add(e);return e;}@Overridepublic String toString() {return list.toString();}
}

数组和链表的区别

• 从定义上讲：数组和链表都是数据的集合。

1、数组中每个元素都是连续的，通过下标进行访问，当我们获取到下标后，就可以随意访问数组中的值

2、链表中的元素则是不连续的，必须获得链表中某个元素后，才能访问该链表中元素的周围元素，不可以随意链表中的元素。链表分为单向链表，双向链表，环形链表等

• 从实现上来讲：

1、数组可以由一块连续区域的内存实现，其中，内存地址可以作为数组的下标，该地址中的值就是数组中元素的值。因为数组占用的是一块空间，所以数组的大小申请之后就会固定；

2、链表可以由不连续的内存存储实现，每个元素都会存储下一个元素的地址。（如果是双向链表的话，元素则会还会存储上个链表的地址）。因为链表中存储了元素的地址，所以链表可以在内存足够的情况下随意申请空间