Java List集合详解：选择合适的数据结构！

开篇语

哈喽，各位小伙伴们，你们好呀，我是喵手。运营社区：C站/掘金/腾讯云/阿里云/华为云/51CTO；欢迎大家常来逛逛

  今天我要给大家分享一些自己日常学习到的一些知识点，并以文字的形式跟大家一起交流，互相学习，一个人虽可以走的更快，但一群人可以走的更远。

  我是一名后端开发爱好者，工作日常接触到最多的就是Java语言啦，所以我都尽量抽业余时间把自己所学到所会的，通过文章的形式进行输出，希望以这种方式帮助到更多的初学者或者想入门的小伙伴们，同时也能对自己的技术进行沉淀，加以复盘，查缺补漏。

小伙伴们在批阅的过程中，如果觉得文章不错，欢迎点赞、收藏、关注哦。三连即是对作者我写作道路上最好的鼓励与支持！

前言

在Java的集合框架中，List接口是一个非常常用的集合类型，它代表了一个有序的元素集合。与其他集合不同，List集合允许重复元素并保证元素的插入顺序。Java中有多种List的实现类，其中最常用的包括ArrayList、LinkedList、Vector等。理解它们的实现原理、性能特点以及使用场景，将帮助你选择最合适的集合类，从而提升程序的效率和性能。

在本篇文章中，我们将深入探讨List集合的实现原理，分析ArrayList和LinkedList的底层实现，比较Vector与ArrayList的区别，最后还会进行性能分析，帮助你做出合适的选择。

1. List集合基础：概述与应用

在Java中，List是一个接口，提供了对元素的有序操作。常见的List实现类有：

• ArrayList：基于动态数组实现，适用于查找频繁、插入和删除较少的场景。
• LinkedList：基于双向链表实现，适用于插入和删除操作频繁的场景。
• Vector：类似于ArrayList，但线程安全，性能较差。

List接口常用方法：

• add(E e)：将元素添加到列表的末尾。
• get(int index)：根据索引获取列表中的元素。
• remove(int index)：删除指定位置的元素。
• size()：返回列表中的元素个数。
• contains(Object o)：判断列表中是否包含指定的元素。

2. ArrayList实现原理和源码分析

ArrayList是List接口的一个常用实现，底层使用数组来存储元素。它提供了高效的随机访问，但对于插入和删除操作，尤其是在中间位置，性能较差，因为涉及到数组的元素移动。

ArrayList底层结构：

• ArrayList的底层是一个Object数组，通过数组来存储元素。数组大小会根据需要动态扩展。
• 默认初始容量为10，当数组满时，ArrayList会自动扩展数组的大小，通常是原数组大小的1.5倍。
• 在扩容时，ArrayList会创建一个新的数组，并将原数组中的元素复制到新数组中。

扩容机制：

当ArrayList的数组存满时，它会通过以下方式进行扩容：

private void grow(int minCapacity) {
    // 扩容至原数组大小的1.5倍
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // 扩容为原来的1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    elementData = Arrays.copyOf(elementData, newCapacity);
}

ArrayList性能分析：

• 查询操作（get）：O(1)，直接通过数组索引访问，效率很高。
• 插入操作：O(n)，当在中间插入元素时，后面的元素需要进行移动，导致时间复杂度为O(n)。
• 删除操作：O(n)，类似于插入操作，删除时后面的元素需要移动。

示例代码：

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
System.out.println(list.get(0)); // 输出 Apple

3. LinkedList实现原理

LinkedList是另一种实现List接口的类，它使用双向链表来存储元素。与ArrayList不同，LinkedList在插入和删除操作上更为高效，尤其是当操作位于链表的开头或中间时，因为它不需要移动元素。

LinkedList底层结构：

• LinkedList的底层是双向链表，每个元素（节点）包含三个部分：

  • 数据元素。
  • 指向前一个元素的引用。
  • 指向下一个元素的引用。

  这样可以方便地进行插入和删除操作。

性能分析：

• 查询操作（get）：O(n)，由于需要从链表的头或尾开始遍历到指定位置，因此效率较低。
• 插入操作：O(1)，在链表头、尾或指定位置进行插入时，时间复杂度是常数级别的。
• 删除操作：O(1)，与插入类似，删除操作的时间复杂度为常数级别。

示例代码：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
System.out.println(list.get(0)); // 输出 Apple

4. Vector和ArrayList的区别

Vector和ArrayList都实现了List接口，底层都使用了动态数组来存储元素。但它们之间有一些关键的区别：

线程安全性：

• Vector：Vector是线程安全的，所有的方法都被sychronized关键字修饰，这意味着它的每个操作都能保证线程安全。
• ArrayList：ArrayList是非线程安全的。虽然它没有内置的同步机制，但它的性能在单线程环境下更优。

扩容机制：

• Vector：Vector的扩容是按照原数组的2倍进行扩展，这使得在空间不够时，Vector会增加更多的内存。
• ArrayList：ArrayList的扩容机制是按照1.5倍进行扩展，相对来说更加保守。

性能差异：

• 由于Vector的同步机制，它的性能相对较低，适用于多线程环境下对线程安全有要求的场景。
• ArrayList在单线程环境下性能更好，且使用更为广泛。

示例代码：

Vector<String> vector = new Vector<>();
vector.add("Apple");
vector.add("Banana");

ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("Apple");
arrayList.add("Banana");

5. List集合的选择和性能分析

在选择使用List集合时，我们需要根据实际的业务需求和性能要求来做决策。下面是根据不同场景的性能比较和建议：

1. 查找操作频繁，插入删除不频繁：ArrayList

• 优点：ArrayList提供O(1)的随机访问时间，适用于频繁查找的场景。
• 缺点：插入和删除时需要移动元素，因此性能较差。

2. 插入和删除操作频繁：LinkedList

• 优点：LinkedList在插入和删除操作上的时间复杂度为O(1)，适合频繁进行插入和删除的场景。
• 缺点：查找操作较慢，需要O(n)时间。

3. 需要线程安全的集合：Vector或CopyOnWriteArrayList

• 优点：Vector提供线程安全的操作，但性能较差。如果需要线程安全的List，CopyOnWriteArrayList可能是更好的选择，尤其是在读操作远多于写操作时。
• 缺点：同步会带来一定的性能开销。

4. 不考虑线程安全性：ArrayList

• 优点：性能高，适合大多数单线程环境下的使用。
• 缺点：不提供线程安全性，如果多个线程同时操作，可能会导致数据不一致。

性能比较：

结语：选择合适的List实现，提升程序性能

List集合是Java开发中非常常见的数据结构，理解不同List实现类的原理、性能特点以及使用场景，将帮助你做出更好的选择。在频繁查询的场景下，ArrayList无疑是最好的选择；而在需要频繁插入或删除元素时，LinkedList则是更合适的选择；如果你需要线程安全的操作，可以考虑使用Vector或者CopyOnWriteArrayList。总之，选择合适的List集合类型，可以帮助你更高效地实现需求，提升程序性能。

… …

文末

好啦，以上就是我这期的全部内容，如果有任何疑问，欢迎下方留言哦，咱们下期见。

… …

学习不分先后，知识不分多少；事无巨细，当以虚心求教；三人行，必有我师焉！！！

wished for you successed ！！！

⭐️若喜欢我，就请关注我叭。

⭐️若对您有用，就请点赞叭。
⭐️若有疑问，就请评论留言告诉我叭。

版权声明：本文由作者原创，转载请注明出处，谢谢支持！