ArrayList、LinkedList、Vector

ArrayList 和 LinkedList 的区别是什么？
数据结构实现：ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实
现。
随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数
据存储方式，所以需要移动指针从前往后依次查找。
增加和删除效率：在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为
ArrayList 增删操作要影响数组内的其他数据的下标。
内存空间占用：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储
了两个引用，一个指向前一个元素，一个指向后一个元素。
线程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
综合来说，在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推
荐使用 LinkedList。
补充：数据结构基础之双向链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前
驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

ArrayList 和 Vector 的区别是什么？
这两个类都实现了 List 接口（List 接口继承了 Collection 接口），他们都是有序集合
ArrayList 是非线程安全的。
性能：ArrayList 在性能方面要优于 Vector。
扩容：ArrayList 和 Vector 都会根据实际的需要动态的调整容量，只不过在
Vector 扩容每次会增加 1 倍，而 ArrayList 只会增加 50%。
Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对
象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。
Arraylist不是同步的，所以在不需要保证线程安全时时建议使用Arraylist。

插入数据时，ArrayList、LinkedList、Vector谁速度较快？阐述 ArrayList、
Vector、LinkedList 的存储性能和特性？
ArrayList、LinkedList、Vector 底层的实现都是使用数组方式存储数据。数组
元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉

速度比较

1. 查询速度：

   • Vector≈ArrayList>LinkedList。由于ArrayList和Vector的底层都是数组结构，支持通过索引直接访问元素，时间复杂度为O(1)，因此查询速度较快。而LinkedList的底层是链表结构，不支持通过索引直接访问，需要从头节点或尾节点开始遍历，时间复杂度为O(n)，因此查询速度较慢。

2. 增删改速度：

   • LinkedList>ArrayList>Vector。LinkedList的链表结构使得插入和删除元素时只需修改相邻节点的指针，时间复杂度为O(1)（在头部或中间位置插入或删除时）。而ArrayList和Vector在插入或删除元素时，需要移动相邻的元素以保持连续性，时间复杂度为O(n)。此外，由于Vector实现了线程同步，因此在增删改操作时会带来额外的性能开销，速度较ArrayList更慢。

及数组元素移动等内存操作，所以索引数据快而插入数据慢。
Vector 中的方法由于加了 synchronized 修饰，因此 Vector是线程安全容器，但性能上较ArrayList差。
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);
线程安全：Vector 使用了 Synchronized 来实现线程同步，是线程安全的，而
LinkedList 使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，但插入数据时只需要记
录当前项的前后项即可，所以 LinkedList插入速度较快。
多线程场景下如何使用 ArrayList？
ArrayList 不是线程安全的，如果遇到多线程场景，可以通过 Collections 的
synchronizedList 方法将其转换成线程安全的容器后再使用。例如像下面这样：

为什么 ArrayList 的 elementData 加上 transient 修饰？ ArrayList 中的数组定
义如下：
再看一下 ArrayList 的定义：
可以看到 ArrayList 实现了 Serializable 接口，这意味着 ArrayList 支持序列
化。transient 的作用是说不希望 elementData 数组被序列化，重写了 writeObject 实现：
每次序列化时，先调用 defaultWriteObject() 方法序列化 ArrayList 中的非transient 元素，然后遍历
elementData，只序列化已存入的元素，这样既加快了序列化的速度，又减小了序列化之后的文件大
小。