一文讲解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 能够高效地实现队列。
- 1. 同样基于双向链表的特性，LinkedList 可以方便地实现栈的操作。对于入栈操作，可以使用 addFirst(E e) 方法将元素添加到链表的头部；对于出栈操作，可以使用 removeFirst() 方法将链表头部的元素移除。在链表头部进行插入和删除操作的时间复杂度为，因此 LinkedList 能高效地实现栈。

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