【Java面试】List接口

冷不防 2024-03-31 12:23 125阅读 0赞

#### 文章目录 ####

*  介绍一下ArrayList的数据结构？
 *  Iterator 和 ListIterator 有什么区别？
 *  谈谈CopyOnWriteArrayList的原理
 *  遍历一个 List 有哪些不同的方式？每种方法的实现原理是什么？Java中List 遍历的最佳实践是什么？（我面试被问到过）
 *  说一下 ArrayList 的优缺点
 *  如何实现数组和 List 之间的转换？
 *  ArrayList 和 LinkedList 的区别是什么？
 *  ArrayList 和 Vector 的区别是什么？
 *  有哪些线程安全的List？
 *  插入数据时，ArrayList、LinkedList、Vector谁速度较快？阐述 ArrayList、Vector、LinkedList 的存储性能和特性？
 *  多线程场景下如何使用 ArrayList？
 *  为什么 ArrayList 的 elementData 加上 transient 修饰？
 *  List 和 Set 的区别
 *  Set篇
 *  Map篇

## 介绍一下ArrayList的数据结构？ ##

ArrayList的底层是用数组来实现的，默认第一次插入元素时创建大小为10的数组，超出限制时会增加50%的容量，并且数据以 System.arraycopy() 复制到新的数组，因此最好能给出数组大小的预估值。

按数组下标访问元素的性能很高，这是数组的基本优势。直接在数组末尾加入元素的性能也高，但如果按下标插入、删除元素，则要用 System.arraycopy() 来移动部分受影响的元素，性能就变差了，这是基本劣势。

## Iterator 和 ListIterator 有什么区别？ ##

*  Iterator 可以遍历 Set 和 List 集合，而 ListIterator 只能遍历 List。
 *  Iterator 只能单向遍历，而 ListIterator 可以双向遍历（向前/后遍历）。
 *  ListIterator 实现 Iterator 接口，然后添加了一些额外的功能，比如添加一个元 素、替换一个元素、获取前面或后面元素的索引位置。

## 谈谈CopyOnWriteArrayList的原理 ##

CopyOnWriteArrayList是Java并发包里提供的并发类，简单来说它就是一个线程安全且读操作无锁的ArrayList。正如其名字一样，在写操作时会复制一份新的List，在新的List上完成写操作，然后再将原引用指向新的List。这样就保证了写操作的线程安全。

CopyOnWriteArrayList允许线程并发访问读操作，这个时候是没有加锁限制的，性能较高。而写操作的时候，则首先将容器复制一份，然后在新的副本上执行写操作，这个时候写操作是上锁的。结束之后再将原容器的引用指向新容器。注意，在上锁执行写操作的过程中，如果有需要读操作，会作用在原容器上。因此上锁的写操作不会影响到并发访问的读操作。

优点：读操作性能很高，因为无需任何同步措施，比较适用于读多写少的并发场景。在遍历传统的List时，若中途有别的线程对其进行修改，则会抛出ConcurrentModificationException异常。而CopyOnWriteArrayList由于其"读写分离"的思想，遍历和修改操作分别作用在不同的List容器，所以在使用迭代器进行遍历时候，也就不会抛出ConcurrentModificationException异常了。

缺点：一是内存占用问题，毕竟每次执行写操作都要将原容器拷贝一份，数据量大时，对内存压力较大，可能会引起频繁GC。二是无法保证实时性，Vector对于读写操作均加锁同步，可以保证读和写的强一致性。而CopyOnWriteArrayList由于其实现策略的原因，写和读分别作用在新老不同容器上，在写操作执行过程中，读不会阻塞但读取到的却是老容器的数据。

## 遍历一个 List 有哪些不同的方式？每种方法的实现原理是什么？Java中List 遍历的最佳实践是什么？（我面试被问到过） ##

遍历方式有以下几种：

1.  for 循环遍历，基于计数器。在集合外部维护一个计数器，然后依次读 取每一个位置的元素，当读取到最后一个元素后停止。
2.  迭代器遍历，Iterator。Iterator 是面向对象的一个设计模式，目的是屏 蔽不同数据集合的特点，  
    统一遍历集合的接口。Java 在 Collections 中支 持了 Iterator 模式。
3.  foreach 循环遍历。foreach 内部也是采用了 Iterator 的方式实现，使 用时不需要显式声明  
    Iterator 或计数器。优点是代码简洁，不易出错；缺 点是只能做简单的遍历，不能在遍历过程中操作数据集合，例如删除、替换。
4.  stream流。

最佳实践：Java Collections 框架中提供了一个 RandomAccess 接口，用来标 记 List 实现是否支持  
Random Access。如果一个数据集合实现了该接口，就意味着它支持 Random Access，按位置读 取元素的平均时间复杂度为 O(1)，如ArrayList。如果没有实现该接口，表示不支持 Random Access，如LinkedList。 推荐的做法就是，支持Random Access 的列表可用 for 循环遍历，否则建议 用 Iterator 或 foreach 遍历。  
例如ArrayList推荐使用for循环遍历，LinkedList推荐使用Iterator或者foreach遍历。  
![在这里插入图片描述][c95aaf0e62e94bd2a033bfecf925d330.png]  
![在这里插入图片描述][9f24441efbcf44a6a1fc83919afc99d6.png]

## 说一下 ArrayList 的优缺点 ##

ArrayList的优点如下：

*  ArrayList 底层以数组实现，是一种随机访问模式。ArrayList 实现了 RandomAccess 接口，因此查  
    找的时候非常快。
 *  ArrayList 在顺序添加一个元素的时候非常方便。

ArrayList 的缺点如下：

*  删除元素的时候，需要做一次元素复制操作。如果要复制的元素很多，那么就会比较耗费性能。
 *  插入元素的时候，也需要做一次元素复制操作，缺点同上。  
    ArrayList 比较适合顺序添加、随机访问的场景。

## 如何实现数组和 List 之间的转换？ ##

数组转 List：使用 Arrays. asList(array) 进行转换。  
List 转数组：使用 List 自带的 toArray() 方法。代码示例：

1 // list to array
    2 List<String> list = new ArrayList<String>();
    3 list.add("123");
    4 list.add("456");
    5 list.toArray();
    6
    7 // array to list
    8 String[] array = new String[]{
        "123","456"};
    9 Arrays.asList(array);

## ArrayList 和 LinkedList 的区别是什么？ ##

*  数据结构实现：ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实  
    现。
 *  随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数  
    据存储方式，所以需要移动指针从前往后依次查找。
 *  增加和删除效率：在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为  
    ArrayList 增删操作要影响数组内的其他数据的下标。所以如果数据插入的位置是中间那么尽可能选择LinkedList，否则ArrayList是最优解。
 *  内存空间占用：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储  
    了两个引用，一个指向前一个元素，一个指向后一个元素。
 *  线程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；

综合来说，在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推荐使用 LinkedList。  
补充：数据结构基础之双向链表  
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

## ArrayList 和 Vector 的区别是什么？ ##

这两个类都实现了 List 接口（List 接口继承了 Collection 接口），他们都是有序集合。

*  线程安全：  
    Vector 使用了 Synchronized 来实现线程同步，是线程安全的，而ArrayList 是非线程安全的。
 *  性能：ArrayList 在性能方面要优于 Vector。
 *  扩容：ArrayList 和 Vector 都会根据实际的需要动态的调整容量，只不过在Vector 扩容每次会增加 1 倍，而 ArrayList 只会增加 50%。
 *  Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。  
    Arraylist不是同步的，所以在不需要保证线程安全时时建议使用Arraylist。

## 有哪些线程安全的List？ ##

Vector  
Vector是比较古老的API，虽然保证了线程安全，但是由于效率低一般不建议使用。

Collections.SynchronizedList  
SynchronizedList是Collections的内部类，Collections提供了synchronizedList方法，可以将一个线程不安全的List包装成线程安全的List，即SynchronizedList。它比Vector有更好的扩展性和兼容性，但是它所有的方法都带有同步锁，也不是性能最优的List。

CopyOnWriteArrayList  
CopyOnWriteArrayList是Java 1.5在java.util.concurrent包下增加的类，它采用复制底层数组的方式来实现写操作。当线程对此类集合执行读取操作时，线程将会直接读取集合本身，无须加锁与阻塞。当线程对此类集合执行写入操作时，集合会在底层复制一份新的数组，接下来对新的数组执行写入操作。由于对集合的写入操作都是对数组的副本执行操作，因此它是线程安全的。在所有线程安全的List中，它是性能最优的方案。

## 插入数据时，ArrayList、LinkedList、Vector谁速度较快？阐述 ArrayList、Vector、LinkedList 的存储性能和特性？ ##

*  速度：  
    ArrayList、Vector 底层的实现都是使用数组方式存储数据。数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢。  
    而LinkedList 使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，但插入数据时只需要记录当前项的前后项即可，所以 LinkedList插入速度较快。
 *  特性：  
    Vector 中的方法由于加了 synchronized 修饰，因此 Vector是线程安全容器，但性能上较ArrayList差。  
    ArrayList 采用的是数组形式来保存对象的，这种方式将对象放在连续的位置中，所以最大的缺点就是插入删除时非常消耗性能。  
    LinkedList 采用的将对象存放在独立的空间中，而且在每个空间中还保存下一个链接的索引，但是缺点就是查找非常麻烦，要丛第一个索引开始。  
    ArrayList和Vector都是用数组方式存储数据，此数组元素数要大于实际的存储空间，以便进行元素增加和插入操作，他们都允许直接用序号索引元素，但是插入数据元素涉及到元素移动等内存操作,所以查询数据快而插入数据慢。  
    LinkedList使用双向链表方式存储数据,按序号索引数据需要前向或后向遍历数据，所以查询数据慢,是插入数据时只需要记录前后项即可,所以插入的速度快。

## 多线程场景下如何使用 ArrayList？ ##

ArrayList 不是线程安全的，如果遇到多线程场景，可以通过 Collections 的synchronizedList 方法将其转换成线程安全的容器后再使用。例如像下面这样：

1 List<String> synchronizedList = Collections.synchronizedList(list);
    2 synchronizedList.add("aaa");
    3 synchronizedList.add("bbb");
    4
    5 for (int i = 0; i < synchronizedList.size(); i++) {
        
    6 	System.out.println(synchronizedList.get(i));
    7 }

## 为什么 ArrayList 的 elementData 加上 transient 修饰？ ##

ArrayList 中的数组定义如下：

private transient Object[] elementData;

再看一下 ArrayList 的定义：

public class ArrayList<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

可以看到 ArrayList 实现了 Serializable 接口，这意味着 ArrayList 支持序列化。  
transient 的作用是说不希望 elementData 数组被序列化，重写了 writeObject 实现：

1 private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOE
    xception{
        
    2 *// Write out element count, and any hidden stuff*
    3 int expectedModCount = modCount;
    4 s.defaultWriteObject();
    5 *// Write out array length*
    6 s.writeInt(elementData.length);
    7 *// Write out all elements in the proper order.*
    8 for (int i=0; i<size; i++)
    9 s.writeObject(elementData[i]);
    10 if (modCount != expectedModCount) {
        
    11 throw new ConcurrentModificationException();
    12 }

每次序列化时，先调用 defaultWriteObject() 方法序列化 ArrayList 中的非transient 元素，然后再遍历  
elementData。只序列化已存入的元素，这样既加快了序列化的速度，又减小了序列化之后的文件大  
小。

## List 和 Set 的区别 ##

List , Set 都是继承自Collection 接口  
List 特点：一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多个null元素，元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。  
Set 特点：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个null元素，必须保证元素唯一性。Set 接口常用实现类是HashSet、LinkedHashSet 以及 TreeSet。

另外 List 支持for循环，也就是通过下标来遍历，也可以用迭代器，但是set只能用迭代，因为他无序，  
无法用下标来取得想要的值。

Set和List对比  
Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。  
List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变。

## Set篇 ##

[Set篇][Set]

## Map篇 ##

[Map篇][Map]

[c95aaf0e62e94bd2a033bfecf925d330.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/ef8bc7812c6e4bdcaba9a87c83189c97.png
[9f24441efbcf44a6a1fc83919afc99d6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/a9e938362f4e42758088d1de2e877b5f.png
[Set]: https://blog.csdn.net/Zhangsama1/article/details/128068449?csdn_share_tail=%7B%22type%22:%22blog%22,%22rType%22:%22article%22,%22rId%22:%22128068449%22,%22source%22:%22Zhangsama1%22%7D
[Map]: https://blog.csdn.net/Zhangsama1/article/details/128068705?spm=1001.2014.3001.5502