实现List接口的三类-ArrayList -Vector -LinkedList

一、ArrayList

1. 数据结构与存储原理
   • ArrayList是基于动态数组实现的。它在内存中是一块连续的存储空间。当创建一个ArrayList时，会初始化一个默认大小（通常为10）的数组。随着元素的不断添加，如果数组容量不够，会进行扩容操作，一般是创建一个更大的数组（如原数组大小的1.5倍），然后将原数组中的元素复制到新数组中。
2. 性能特点
   • 随机访问性能好：由于其基于数组的存储方式，通过索引访问元素非常快速，时间复杂度为O(1)。例如，使用get(int index)方法获取指定索引的元素时，直接通过数组下标就可以定位到元素。
   • 插入和删除性能较差（除末尾操作）：在中间位置插入或删除元素时，需要移动后面的元素，时间复杂度为O(n)。比如在索引为3的位置插入一个元素，那么索引3及其后面的所有元素都要向后移动一位。不过，在末尾添加元素的时间复杂度为O(1)。
3. 常用场景
   • 适用于需要频繁进行随机访问操作，并且对元素的添加和删除操作主要在末尾进行的场景。例如，存储一组学生的成绩，需要经常查询某个学生的成绩（随机访问），偶尔在末尾添加新的成绩数据。

二、Vector

1. 数据结构与存储原理
   • Vector和ArrayList类似，也是基于动态数组实现的。不同的是，Vector是线程安全的，它的很多方法都是通过synchronized关键字修饰的，这意味着在多线程环境下多个线程访问同一个Vector对象时会进行同步控制。
2. 性能特点
   • 线程安全带来的性能损耗：由于其线程安全的特性，在多线程并发访问时需要进行同步锁的获取和释放操作，这使得它的性能相对ArrayList要低。在单线程环境下，它的性能和ArrayList类似。
   • 随机访问性能好：同样基于数组结构，随机访问元素的时间复杂度为O(1)。
   • 插入和删除性能较差（除末尾操作）：在中间插入或删除元素时需要移动元素，时间复杂度为O(n)，在末尾添加元素时间复杂度为O(1)。
3. 常用场景
   • 在多线程环境下，如果需要一个线程安全的动态数组结构来存储数据时可以使用Vector。不过在Java 5之后，更推荐使用Collections.synchronizedList(new ArrayList<>())这种方式来创建线程安全的列表，因为它比Vector更灵活，并且在非并发情况下性能更好。

三、LinkedList

1. 数据结构与存储原理
   • LinkedList是基于双向链表实现的。每个节点包含了数据元素、指向前一个节点的引用和指向后一个节点的引用。
2. 性能特点
   • 随机访问性能差：由于链表结构，要访问链表中的某个元素，需要从链表头（或尾）开始逐个节点遍历，时间复杂度为O(n)。例如，使用get(int index)方法获取指定索引的元素时，需要遍历链表找到该元素。
   • 插入和删除性能好（特别是在中间位置）：在链表中插入或删除一个元素，只需要修改节点之间的引用关系，时间复杂度为O(1)（如果已经定位到要插入或删除的节点位置）。但是，如果要根据索引插入或删除元素，需要先遍历链表找到该索引对应的节点，这个遍历过程的时间复杂度为O(n)。
3. 常用场景
   • 适用于需要频繁进行插入和删除操作（尤其是在列表中间），而对随机访问操作要求不高的场景。例如，实现一个简单的队列或者栈结构，使用LinkedList就比较合适。

ArrayList的常用方法

ArrayList是Java中常用的动态数组，它实现了List接口，提供了一系列用于操作数组的方法。以下是一些ArrayList的常用方法：

1. add(E e)：将指定的元素添加到列表的末尾。
2. add(int index, E element)：将指定的元素插入到指定位置。
3. remove(int index)：移除指定位置的元素。
4. remove(Object o)：移除指定的元素。
5. get(int index)：获取指定位置的元素。
6. set(int index, E element)：替换指定位置的元素。
7. size()：返回列表中的元素个数。
8. isEmpty()：判断列表是否为空。
9. contains(Object o)：判断列表是否包含指定的元素。
10. clear()：清空列表中的所有元素。
11. toArray()：将列表转换为数组。
12. sort(Comparator<? super E> c)：对列表中的元素进行排序。

Vector的常用方法

Vector是Java中的一个动态数组，它与ArrayList类似，但Vector是线程安全的。以下是一些Vector的常用方法：

1. add(E e)：将指定的元素添加到向量的末尾。
2. add(int index, E element)：将指定的元素插入到指定位置。
3. remove(int index)：移除指定位置的元素。
4. remove(Object o)：移除指定的元素。
5. get(int index)：获取指定位置的元素。
6. set(int index, E element)：替换指定位置的元素。
7. size()：返回向量中的元素个数。
8. isEmpty()：判断向量是否为空。
9. contains(Object o)：判断向量是否包含指定的元素。
10. clear()：清空向量中的所有元素。
11. toArray()：将向量转换为数组。
12. sort(Comparator<? super E> c)：对向量中的元素进行排序。

LinkedList的常用方法

LinkedList是Java中的一个双向链表，它实现了List接口，提供了一系列用于操作链表的方法。以下是一些LinkedList的常用方法：

1. add(E e)：将指定的元素添加到链表的末尾。
2. add(int index, E element)：将指定的元素插入到指定位置。
3. remove(int index)：移除指定位置的元素。
4. remove(Object o)：移除指定的元素。
5. get(int index)：获取指定位置的元素。
6. set(int index, E element)：替换指定位置的元素。
7. size()：返回链表中的元素个数。
8. isEmpty()：判断链表是否为空。
9. contains(Object o)：判断链表是否包含指定的元素。
10. clear()：清空链表中的所有元素。
11. toArray()：将链表转换为数组。
12. sort(Comparator<? super E> c)：对链表中的元素进行排序。

总结

ArrayList、Vector和LinkedList都是Java中常用的集合类，它们都实现了List接口，提供了一系列用于操作列表的方法。ArrayList和Vector都是基于数组实现的，而LinkedList是基于双向链表实现的。ArrayList和Vector在大多数情况下可以互换使用，但Vector是线程安全的，因此在多线程环境下可能更适合。LinkedList在插入和删除操作上比ArrayList和Vector更高效，但在随机访问上比它们慢。