Java面试之Java List集合

Java集合类存放于Java.util包中，主要有3种：List(列表包含Queue)、Set(集)、Map(映射)

List是有序的Collection。是线性数据结构的主要表现，存储的元素是有序的，可重复的。

一共三个实现类: 分别是ArrayList、Vector和LinkedList。

ArrayList底层使用数组实现，元素存储有序可重复，线程不安全，查询快增删慢，支持快速随机访问，扩容1.5倍。

ArrayList的自动扩容机制

ArrayList是一个数组结构的存储容器，默认情况下，数组的长度是10，当然我们可以在构建ArrayList对象的时候自己指定初始化长度。随着在程序里面不断的往ArrayList中添加数据，当添加的数据达到10个的时候，ArrayList就没有多余的容量可以存储后续的数据。

这个时候ArrayList就会自动触发扩容。扩容的具体流程很简单：

首先，创建一个新的数组，这个数组的长度是原来数组长度的1.5倍。

然后使用Arrays.copyOf方法把老数组里面的数据拷贝到新的数组里面。

扩容完成后再把当前要添加的元素加入到新的数组里面，从而完成动态扩容的过程。

LinkedList底层使用双向链表实现，元素存储排序有序可重复，线程不安全，查询慢增删快，不支持随机访问。

Vector1.0就存在，1.2出现在集合框架中。和ArrayList一样也是数组结构，是线程安全的，因此运行效率慢，每次扩容100%。

ArrayList与LinkedList区别

1.数据结构

ArrayList是基于动态数组实现的，它内部维护一个可变长度的数组，当元素数量增加时，会根据需要自动扩容。

LinkedList则是基于链表实现的，它内部维护一个双向链表。

2.访问效率

ArrayList是基于数组实现的，因此它能够随机访问集合中的元素，时间复杂度为O(1)，但在插入和删除元素时，需要将后续的元素向前或向后移动，时间复杂度为O(n)。

LinkedList则是基于链表实现的，因此在访问元素时需要从头或尾开始遍历链表，时间复杂度为O(n)，但在插入和删除元素时，由于只需要修改前后节点的引用，时间复杂度为O(1)。

3.空间占用

ArrayList需要维护一个动态数组，因此在一定程度上比LinkedList占用更多的空间。

但在实际应用中，ArrayList更常用，因为它能够提供更快的随机访问和更好的缓存性能。

4.线程安全

ArrayList和LinkedList都不是线程安全的，如果需要在多线程环境中使用，需要使用线程安全的集合类或者在访问时进行同步控制。

ArrayList与Vector区别

1.线程安全性

Vector是线程安全的，而ArrayList是非线程安全的。因此，在多线程的情况下，ArrayList的性能更好，而Vector的线程安全性可能会导致性能损失。

2.扩容机制

ArrayList和Vector在扩容时都会增加容量大小，不同之处在于，ArrayList扩容时会增加原始容量的一半，而Vector扩容时会将容量翻倍。因此，ArrayList相对于Vector更加灵活，可以更快地适应容量变化。

3.数据增删效率

ArrayList和Vector在数据增删时的效率也有所不同。由于Vector是线程安全的，在进行数据操作时需要进行同步，这会导致效率降低。而ArrayList不需要同步，因此数据操作效率更高。

4.性能

由于ArrayList不是线程安全的，因此其性能要比Vector高。

Iterator和ListIterator都是Java集合框架中的迭代器，用于遍历集合中的元素。Iterator可以遍历所有Collection接口的实现类，如List、Set等。但是只能单向遍历，即只能从前向后遍历，不能向后回退。Iterator提供的方法有：

hasNext()：判断是否还有下一个元素。

next()：返回下一个元素。

remove()：移除上一个元素(如果未调用next()方法则没有元素可删，如果连续调用两次remove()方法也会报错)。

ListIterator只能遍历List接口的实现类，而且是双向遍历。即可以从前向后遍历，也可以从后向前遍历。ListIterator提供的方法有：

hasNext()：判断是否还有下一个元素。

next()：返回下一个元素。

hasPrevious()：判断是否还有上一个元素。

previous()：返回上一个元素。

remove()：移除上一个元素（如果未调用next()或previous()方法则没有元素可删，如果连续调用两次remove()方法也会报错）。

add(E e)：在当前元素位置后添加一个元素。

set(E e)：修改当前元素。