ArrayList 与 LinkedList

第一部分：ArrayList vs LinkedList（最常见的对比）

核心区别

特性	ArrayList	LinkedList
底层结构	动态数组	双向链表
随机访问	O(1) - 很快	O(n) - 较慢
头部插入/删除	O(n) - 慢	O(1) - 很快
尾部插入/删除	O(1) - 很快	O(1) - 很快
内存占用	较小（只存数据）	较大（每个元素都有前后指针）
遍历方式	用索引/迭代器	只能用迭代器
适用场景	查询多，增删少	增删多，查询少

ArrayList详解

1. 底层原理：动态数组

// ArrayList内部结构
public class ArrayList<E> {
    // 实际存储元素的数组
    private Object[] elementData;
    
    // 当前元素数量
    private int size;
    
    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 10;
}

2. 扩容机制

// ArrayList扩容流程
初始：数组长度 = 10
添加第11个元素时：
1. 创建新数组，长度 = 旧数组长度 * 1.5（15）
2. 将旧数组元素复制到新数组
3. 将新元素放入新数组
4. 更新引用指向新数组

3. 代码示例

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ArrayListDemo {
    public static void main(String[] args) {
        // 创建ArrayList
        List<String> arrayList = new ArrayList<>();
        
        // 1. 添加元素 - 尾部添加很快
        arrayList.add("Apple");
        arrayList.add("Banana");
        arrayList.add("Orange");
        
        // 2. 随机访问 - O(1)
        System.out.println("第一个元素: " + arrayList.get(0));  // Apple
        System.out.println("第二个元素: " + arrayList.get(1));  // Banana
        
        // 3. 遍历方式
        // 方式1: for循环（ArrayList适合，LinkedList不适合）
        for (int i = 0; i < arrayList.size(); i++) {
            System.out.println("索引" + i + ": " + arrayList.get(i));
        }
        
        // 方式2: 增强for循环
        for (String fruit : arrayList) {
            System.out.println("水果: " + fruit);
        }
        
        // 方式3: 迭代器
        Iterator<String> iterator = arrayList.iterator();
        while (iterator.hasNext()) {
            System.out.println("迭代器: " + iterator.next());
        }
        
        // 4. 中间插入 - 较慢（需要移动元素）
        arrayList.add(1, "Grape");  // 在索引1处插入，后面的元素都要后移
        
        // 5. 删除元素
        arrayList.remove(0);  // 删除第一个元素，后面的元素都要前移
        
        // 6. 转换为数组
        String[] array = arrayList.toArray(new String[0]);
        
        // 7. 性能测试
        testArrayListPerformance();
    }
    
    public static void testArrayListPerformance() {
        List<Integer> list = new ArrayList<>();
        
        // 测试尾部添加
        long start = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            list.add(i);  // 尾部添加，很快
        }
        long end = System.nanoTime();
        System.out.println("尾部添加10万元素耗时: " + (end - start) / 1000000 + "ms");
        
        // 测试头部添加
        list.clear();
        start = System.nanoTime();
        for (int i = 0; i < 10000; i++) {
            list.add(0, i);  // 头部添加，很慢
        }
        end = System.nanoTime();
        System.out.println("头部添加1万元素耗时: " + (end - start) / 1000000 + "ms");
    }
}

LinkedList详解

1. 底层原理：双向链表

// LinkedList内部结构
public class LinkedList<E> {
    // 节点内部类
    private static class Node<E> {
        E item;         // 存储的元素
        Node<E> prev;   // 前驱节点
        Node<E> next;   // 后继节点
    }
    
    Node<E> first;  // 头节点
    Node<E> last;   // 尾节点
    int size;       // 元素数量
}

2. 代码示例

import java.util.LinkedList;
import java.util.List;
import java.util.Deque;

public class LinkedListDemo {
    public static void main(String[] args) {
        // LinkedList实现了List和Deque接口
        LinkedList<String> linkedList = new LinkedList<>();
        
        // 1. 作为List使用
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Orange");
        
        // 2. 作为队列（Queue）使用
        // 添加元素
        linkedList.offer("Grape");      // 尾部添加
        linkedList.offerFirst("Pear");  // 头部添加
        linkedList.offerLast("Peach");  // 尾部添加
        
        // 获取但不移除
        System.out.println("队首: " + linkedList.peek());      // Pear
        System.out.println("队尾: " + linkedList.peekLast());  // Peach
        
        // 获取并移除
        System.out.println("出队: " + linkedList.poll());      // 移除Pear
        System.out.println("尾部出队: " + linkedList.pollLast()); // 移除Peach
        
        // 3. 作为栈（Stack）使用
        linkedList.push("Cherry");  // 压栈（添加到头部）
        System.out.println("栈顶: " + linkedList.pop());  // 出栈（移除头部）
        
        // 4. 双向链表特性
        linkedList.addFirst("First");
        linkedList.addLast("Last");
        
        // 5. 遍历（不要用for循环+get(i)）
        // 正确方式：迭代器
        for (String fruit : linkedList) {
            System.out.println("水果: " + fruit);
        }
        
        // 6. 性能测试
        testLinkedListPerformance();
    }
    
    public static void testLinkedListPerformance() {
        LinkedList<Integer> list = new LinkedList<>();
        
        // 测试头部添加
        long start = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            list.addFirst(i);  // 头部添加，很快
        }
        long end = System.nanoTime();
        System.out.println("头部添加10万元素耗时: " + (end - start) / 1000000 + "ms");
        
        // 测试随机访问
        start = System.nanoTime();
        for (int i = 0; i < 1000; i++) {
            list.get(i * 100);  // 随机访问，很慢
        }
        end = System.nanoTime();
        System.out.println("随机访问1000次耗时: " + (end - start) / 1000000 + "ms");
    }
}

实际应用场景

场景1：选择ArrayList

// 1. 需要频繁随机访问
List<Product> productList = new ArrayList<>();
// 假设显示商品列表，用户经常点击查看详情
public Product getProductById(int index) {
    return productList.get(index);  // O(1)操作
}

// 2. 大部分操作在尾部
List<Log> logList = new ArrayList<>();
public void addLog(Log log) {
    logList.add(log);  // 尾部添加，很快
}

// 3. 需要遍历
for (int i = 0; i < productList.size(); i++) {
    // 用索引访问
}

场景2：选择LinkedList

// 1. 实现队列/栈
Queue<Task> taskQueue = new LinkedList<>();
taskQueue.offer(new Task());  // 入队
Task task = taskQueue.poll(); // 出队

// 2. 需要频繁在头部插入/删除
LinkedList<Message> chatHistory = new LinkedList<>();
chatHistory.addFirst(new Message());  // 最新消息放头部
chatHistory.removeLast();             // 删除最旧消息

// 3. LRU缓存实现
class LRUCache<K, V> {
    private LinkedList<K> list = new LinkedList<>();
    private Map<K, V> map = new HashMap<>();
    
    public V get(K key) {
        if (map.containsKey(key)) {
            // 移动到头部
            list.remove(key);
            list.addFirst(key);
            return map.get(key);
        }
        return null;
    }
}

性能对比测试

import java.util.*;

public class ListPerformanceTest {
    public static void main(String[] args) {
        int size = 100000;
        
        // ArrayList测试
        List<Integer> arrayList = new ArrayList<>();
        long start = System.currentTimeMillis();
        
        // 1. 添加测试
        for (int i = 0; i < size; i++) {
            arrayList.add(i);  // 尾部添加
        }
        long arrayAddTime = System.currentTimeMillis() - start;
        
        // 2. 随机访问测试
        start = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            arrayList.get(i * 10);
        }
        long arrayGetTime = System.currentTimeMillis() - start;
        
        // 3. 中间插入测试
        start = System.currentTimeMillis();
        for (int i = 0; i < 1000; i++) {
            arrayList.add(50000, i);  // 在中间插入
        }
        long arrayInsertTime = System.currentTimeMillis() - start;
        
        // LinkedList测试
        List<Integer> linkedList = new LinkedList<>();
        start = System.currentTimeMillis();
        
        // 1. 添加测试
        for (int i = 0; i < size; i++) {
            linkedList.add(i);  // 尾部添加
        }
        long linkedAddTime = System.currentTimeMillis() - start;
        
        // 2. 随机访问测试
        start = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            linkedList.get(i * 10);
        }
        long linkedGetTime = System.currentTimeMillis() - start;
        
        // 3. 中间插入测试
        start = System.currentTimeMillis();
        for (int i = 0; i < 1000; i++) {
            linkedList.add(50000, i);  // 在中间插入
        }
        long linkedInsertTime = System.currentTimeMillis() - start;
        
        // 打印结果
        System.out.println("========== 性能测试结果 ==========");
        System.out.println("操作\t\tArrayList\tLinkedList");
        System.out.println("尾部添加\t\t" + arrayAddTime + "ms\t\t" + linkedAddTime + "ms");
        System.out.println("随机访问\t\t" + arrayGetTime + "ms\t\t" + linkedGetTime + "ms");
        System.out.println("中间插入\t\t" + arrayInsertTime + "ms\t\t" + linkedInsertTime + "ms");
        
        // 头部添加测试
        List<Integer> arrayList2 = new ArrayList<>();
        List<Integer> linkedList2 = new LinkedList<>();
        
        start = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            arrayList2.add(0, i);  // 头部添加
        }
        long arrayAddFirstTime = System.currentTimeMillis() - start;
        
        start = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            linkedList2.addFirst(i);  // 头部添加
        }
        long linkedAddFirstTime = System.currentTimeMillis() - start;
        
        System.out.println("头部添加\t\t" + arrayAddFirstTime + "ms\t\t" + linkedAddFirstTime + "ms");
    }
}

内存占用对比

public class MemoryTest {
    public static void main(String[] args) {
        Runtime runtime = Runtime.getRuntime();
        
        // 测试ArrayList
        runtime.gc();
        long startMemory = runtime.totalMemory() - runtime.freeMemory();
        
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < 100000; i++) {
            arrayList.add(i);
        }
        
        long endMemory = runtime.totalMemory() - runtime.freeMemory();
        System.out.println("ArrayList占用内存: " + (endMemory - startMemory) / 1024 + "KB");
        
        // 测试LinkedList
        runtime.gc();
        startMemory = runtime.totalMemory() - runtime.freeMemory();
        
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < 100000; i++) {
            linkedList.add(i);
        }
        
        endMemory = runtime.totalMemory() - runtime.freeMemory();
        System.out.println("LinkedList占用内存: " + (endMemory - startMemory) / 1024 + "KB");
    }
}

最佳实践建议

1. 选择策略

// 选择ArrayList的情况：
// 1. 需要频繁随机访问
// 2. 元素数量大致已知
// 3. 大部分操作是遍历或尾部操作

// 选择LinkedList的情况：
// 1. 需要频繁在头部插入/删除
// 2. 需要实现栈/队列/双端队列
// 3. 元素数量变化很大

2. 初始化容量

// ArrayList指定初始容量（避免多次扩容）
List<String> list = new ArrayList<>(1000);

// LinkedList没有容量概念

3. 遍历方式

// ArrayList：三种方式都可以
for (int i = 0; i < list.size(); i++) {  // 最快
    list.get(i);
}

// LinkedList：只能用迭代器
for (String s : list) {  // 使用迭代器
    // ...
}

如果"QurryList"指的是其他

可能性1：QueryList（可能是自定义的查询列表）

// 假设这是一个封装了查询功能的List
public class QueryList<T> extends ArrayList<T> {
    
    // 添加查询方法
    public List<T> query(Predicate<T> predicate) {
        return this.stream()
                  .filter(predicate)
                  .collect(Collectors.toList());
    }
    
    // 使用示例
    public static void main(String[] args) {
        QueryList<User> users = new QueryList<>();
        users.add(new User("Alice", 25));
        users.add(new User("Bob", 30));
        
        // 查询年龄大于25的用户
        List<User> result = users.query(u -> u.getAge() > 25);
    }
}

可能性2：Queue相关的List

// Queue接口的实现
Queue<String> queue = new LinkedList<>();  // LinkedList实现了Queue

// 或者PriorityQueue
Queue<Integer> priorityQueue = new PriorityQueue<>();

总结

ArrayList：

• 数组实现，查询快，增删慢
• 需要连续内存空间
• 尾部操作效率高
• 适合：查询多、增删少的场景

LinkedList：

• 链表实现，增删快，查询慢
• 不需要连续内存
• 头尾操作效率高
• 适合：频繁增删、实现队列/栈的场景

选择原则：

• 80%的情况用ArrayList
• 需要队列/栈功能时用LinkedList
• 不确定时先用ArrayList，性能有问题再优化

记住：ArrayList是"数组列表"，LinkedList是"链表"，根据你的具体需求选择。