List 接口的三种实现类：ArrayList、LinkedList 和 Vector

大家好，我是香香。

前面给大家介绍了 Collection 容器，今天带来的是更细节的实现类介绍。

（这也将是一个新的 “集合” 合集）

可以看到 Collection 容器中最常见的两个接口：List、Set。

就让我们深入了解下 List 接口。

List 接口表示一个有序的集合，它允许重复的元素。

List 接口的实现类包括 ArrayList、LinkedList 和 Vector。

ArrayList

ArrayList 是基于动态数组实现的 List 接口的实现类。

它可以自动扩容，也可以设置初始容量。

由于是基于数组实现的，因此 ArrayList 可以随机访问元素，时间复杂度为 O(1)。

在尾部添加元素的时间复杂度也为 O(1)。

但在中间插入或删除元素时，需要移动其他元素，时间复杂度为 O(n)。

使用方式：

ArrayList 的使用方式非常简单。

可以通过以下代码创建一个 ArrayList 对象：

List<String> list = new ArrayList<>();

接下来可以使用 List 接口中定义的方法来操作 ArrayList 对象，如添加元素、删除元素、获取元素等。

例如：

list.add("apple");list.add("banana");list.add("orange");String fruit = list.get(1);list.remove("orange");

注意：由于 ArrayList 是基于数组实现的，因此在大量插入或删除元素时，可能会导致性能下降。

LinkedList

LinkedList 是基于双向链表实现的 List 接口的实现类。

它可以高效地在头部和尾部插入或删除元素，时间复杂度为 O(1)。

但是在随机访问元素时需要遍历链表，时间复杂度为 O(n)。

使用方式：

LinkedList 的使用方式与 ArrayList 类似。

可以通过以下代码创建一个 LinkedList 对象：

List<String> list = new LinkedList<>();

接下来可以使用 List 接口中定义的方法来操作 LinkedList 对象，如添加元素、删除元素、获取元素等。

例如：

list.add("apple");list.add("banana");list.add("orange");String fruit = list.get(1);list.remove("orange");

注意：由于 LinkedList 是基于链表实现的，因此在大量随机访问元素时，可能会导致性能下降。

Vector

Vector 是一个线程安全的List接口的实现类。

它与 ArrayList 类似，也是基于动态数组实现的，可以自动扩容，可以设置初始容量。

由于是基于数组实现的，因此 Vector 可以随机访问元素，时间复杂度为 O(1)。

在尾部添加元素的时间复杂度也为 O(1)。

但在中间插入或删除元素时，需要移动其他元素，时间复杂度为 O(n)。

使用方式：

Vector 的使用方式与 ArrayList 类似。

可以通过以下代码创建一个 Vector 对象：

List<String> list = new Vector<>();

接下来可以使用 List 接口中定义的方法来操作 Vector 对象，如添加元素、删除元素、获取元素等。

例如：

list.add("apple");list.add("banana");list.add("orange");String fruit = list.get(1);list.remove("orange");

注意：由于 Vector 是线程安全的，因此在多线程环境下使用时可以保证数据的安全性，但也会影响性能。

三者之间的区别比较

ArrayList、LinkedList 和 Vector 都是 List 接口的实现类，它们都可以用来存储有序的元素，允许重复。

其中，ArrayList 和 Vector 都是基于动态数组实现的。

它们可以随机访问元素，时间复杂度为 O(1)。

在尾部添加元素的时间复杂度也为 O(1)。

但在中间插入或删除元素时，需要移动其他元素，时间复杂度为 O(n)。

---

ArrayList 和 Vector的区别在于，ArrayList 不是线程安全的，而Vector是线程安全的。

LinkedList 是基于双向链表实现的，可以高效地在头部和尾部插入或删除元素，时间复杂度为 O(1)。

但是在随机访问元素时需要遍历链表，时间复杂度为 O(n)。

因此，在选择使用 ArrayList、LinkedList 和 Vector 时，需要根据具体的需求来进行选择。

总结：

如果需要随机访问元素，并且没有多线程并发访问的需求，可以选择 ArrayList；

如果需要高效地在头部和尾部插入或删除元素，并且不需要随机访问元素，可以选择 LinkedList；

如果需要多线程并发访问，并且不需要高效地在头部和尾部插入或删除元素，可以选择 Vector。