一文讲解Java中的ArrayList和LinkedList

ArrayList和LinkedList有什么区别？

• ArrayList 是基于数组实现的，LinkedList 是基于链表实现的。
  
  二者用途有什么不同？

• 多数情况下，ArrayList更利于查找，LinkedList更利于增删

  1. 由于 ArrayList 是基于数组实现的，所以 get(int index) 可以直接通过数组下标获取，时间复杂度是 O(1)；LinkedList 是基于链表实现的，get(int index) 需要遍历链表，时间复杂度是 O(n)。
     当然，get(E element) 这种查找，两种集合都需要遍历通过 equals 比较获取元素，所以时间复杂度都是 O(n)。

  2. ArrayList 如果增删的是数组的尾部，直接插入或者删除就可以了，时间复杂度是 O(1)；如果 add 的时候涉及到扩容，时间复杂度会提升到 O(n)。

     但如果插入的是中间的位置，就需要把插入位置后的元素向前或者向后移动，甚至还有可能触发扩容，效率就会低很多，O(n)。

     LinkedList 因为是链表结构，插入和删除只需要改变前置节点、后置节点和插入节点的引用就行了，不需要移动元素。

     如果是在链表的头部插入或者删除，时间复杂度是 O(1)；如果是在链表的中间插入或者删除，时间复杂度是 O(n)，因为需要遍历链表找到插入位置；如果是在链表的尾部插入或者删除，时间复杂度是 O(1)。

• 注意，这里有个陷阱，LinkedList 更利于增删不是体现在时间复杂度上，因为二者增删的时间复杂度都是 O(n)，都需要遍历列表；而是体现在增删的效率上，因为 LinkedList 的增删只需要改变引用，而 ArrayList 的增删可能需要移动元素。

二者是否支持随机访问呢？

• ①、ArrayList 是基于数组的，也实现了 RandomAccess 接口，所以它支持随机访问，可以通过下标直接获取元素。
• ②、LinkedList 是基于链表的，所以它没法根据下标直接获取元素，不支持随机访问，所以它也没有实现 RandomAccess 接口。

二者的内存占用有何不同？

• ArrayList 是基于数组的，是一块连续的内存空间，所以它的内存占用是比较紧凑的；但如果涉及到扩容，就会重新分配内存，空间是原来的 1.5 倍，存在一定的空间浪费。
• LinkedList 是基于链表的，每个节点都有一个指向下一个节点和上一个节点的引用，于是每个节点占用的内存空间稍微大一点。

二者的使用场景有什么不同呢？

ArrayList 适用于：

• 随机访问频繁：需要频繁通过索引访问元素的场景。
• 读取操作远多于写入操作：如存储不经常改变的列表。
• 末尾添加元素：需要频繁在列表末尾添加元素的场景。

LinkedList 适用于：

• 频繁插入和删除：在列表中间频繁插入和删除元素的场景。
• 不需要快速随机访问：顺序访问多于随机访问的场景。
  • 在日志记录处理的场景中，通常是按照日志产生的先后顺序依次读取和处理日志信息，不需要随机访问某一条特定的日志。例如，从日志文件中逐行读取日志内容，对每一条日志进行解析和分析。此时使用 LinkedList 存储日志信息，通过迭代器进行顺序访问，可以高效地完成日志处理任务。

import java.util.Iterator;
import java.util.LinkedList;

public class LogProcessingExample {
    public static void main(String[] args) {
        LinkedList<String> logList = new LinkedList<>();
        logList.add("Log entry 1");
        logList.add("Log entry 2");
        logList.add("Log entry 3");

        // 顺序访问日志
        Iterator<String> iterator = logList.iterator();
        while (iterator.hasNext()) {
            String log = iterator.next();
            System.out.println("Processing log: " + log);
        }
    }
}

• 队列和栈：由于其双向链表的特性，LinkedList 可以高效地实现队列（FIFO）和栈（LIFO）。
  • 1. 双向链表在头部和尾部进行插入和删除操作的时间复杂度都是 ，所以 LinkedList 能够高效地实现队列。
  • 2. 同样基于双向链表的特性，LinkedList 可以方便地实现栈的操作。对于入栈操作，可以使用 addFirst(E e) 方法将元素添加到链表的头部；对于出栈操作，可以使用 removeFirst() 方法将链表头部的元素移除。在链表头部进行插入和删除操作的时间复杂度为 ，因此 LinkedList 能高效地实现栈。

链表和数组又有什么区别？

• 数组在内存中占用的是一块连续的存储空间，因此我们可以通过数组下标快速访问任意元素。数组在创建时必须指定大小，一旦分配内存，数组的大小就固定了。
• 链表的元素（节点）存储在内存中的任意位置，每个节点通过指针（引用）指向下一个节点。链表不需要指定大小，可以在运行时动态变化。