Java 中 LinkedList 与 ArrayList 的深度剖析

简介

在 Java 编程中，选择合适的数据结构对于程序的性能和可维护性至关重要。LinkedList 和 ArrayList 是两个常用的动态数组实现，它们在很多方面存在差异。本文将深入探讨这两者的基础概念、使用方法、常见实践以及最佳实践，帮助你在不同场景下做出更优的选择。

基础概念

LinkedList

LinkedList 是基于双向链表实现的。每个节点包含数据以及指向前一个节点和后一个节点的引用。这种结构使得在链表中间插入和删除元素的操作相对高效，因为只需修改相关节点的引用即可。但由于需要额外的引用存储，它占用的内存空间相对较大。

ArrayList

ArrayList 是基于动态数组实现的。它在内存中连续存储元素，这使得通过索引访问元素非常快速，时间复杂度为 O(1)。但在数组中间插入或删除元素时，需要移动大量元素，效率较低。随着元素的增加，ArrayList 会自动扩展其内部数组的大小。

使用方法

LinkedList 的常用操作

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // 创建 LinkedList
        LinkedList<String> linkedList = new LinkedList<>();

        // 添加元素
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.addFirst("Orange");
        linkedList.addLast("Mango");

        // 获取元素
        System.out.println("First element: " + linkedList.getFirst());
        System.out.println("Last element: " + linkedList.getLast());

        // 删除元素
        linkedList.remove("Banana");
        linkedList.removeFirst();
        linkedList.removeLast();

        // 遍历 LinkedList
        for (String fruit : linkedList) {
            System.out.println(fruit);
        }
    }
}

ArrayList 的常用操作

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        // 创建 ArrayList
        ArrayList<String> arrayList = new ArrayList<>();

        // 添加元素
        arrayList.add("Red");
        arrayList.add("Green");
        arrayList.add(1, "Blue");

        // 获取元素
        System.out.println("Element at index 1: " + arrayList.get(1));

        // 删除元素
        arrayList.remove(0);
        arrayList.remove("Green");

        // 遍历 ArrayList
        for (int i = 0; i < arrayList.size(); i++) {
            System.out.println(arrayList.get(i));
        }
    }
}

常见实践

遍历操作

LinkedList 的遍历

由于 LinkedList 是链表结构，使用迭代器遍历通常效率更高，尤其是在需要频繁删除或插入元素时。

LinkedList<Integer> linkedList = new LinkedList<>();
// 添加元素
for (int i = 0; i < 10; i++) {
    linkedList.add(i);
}

// 使用迭代器遍历
java.util.Iterator<Integer> iterator = linkedList.iterator();
while (iterator.hasNext()) {
    Integer num = iterator.next();
    System.out.println(num);
}

ArrayList 的遍历

ArrayList 基于数组，使用普通的 for 循环通过索引访问元素的效率最高。

ArrayList<Integer> arrayList = new ArrayList<>();
// 添加元素
for (int i = 0; i < 10; i++) {
    arrayList.add(i);
}

// 使用普通 for 循环遍历
for (int i = 0; i < arrayList.size(); i++) {
    Integer num = arrayList.get(i);
    System.out.println(num);
}

插入和删除操作

LinkedList 的插入和删除

在链表的开头、结尾或中间插入和删除元素的时间复杂度为 O(1)，因为只需修改节点的引用。

LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);

// 在中间插入元素
linkedList.add(1, 4);

// 删除元素
linkedList.remove(2);

ArrayList 的插入和删除

在 ArrayList 中间插入或删除元素时，需要移动大量元素，时间复杂度为 O(n)。在末尾插入或删除元素的时间复杂度为 O(1)。

ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);

// 在中间插入元素
arrayList.add(1, 4);

// 删除元素
arrayList.remove(2);

最佳实践

何时选择 LinkedList

当需要频繁在列表中间进行插入和删除操作时，LinkedList 更合适，因为其插入和删除操作的时间复杂度为 O(1)。
当内存使用不是主要考虑因素，且需要高效的队列或栈操作时，LinkedList 提供了方便的方法，如 addFirst、addLast、removeFirst、removeLast 等。

何时选择 ArrayList

如果需要频繁通过索引访问元素，ArrayList 是更好的选择，因为其通过索引访问的时间复杂度为 O(1)。
当内存使用较为关键，且插入和删除操作主要在列表末尾进行时，ArrayList 由于其紧凑的内存布局，更为合适。

小结

LinkedList 和 ArrayList 都是 Java 中强大的数据结构，各有优缺点。理解它们的基础概念、使用方法以及在不同场景下的性能表现，有助于编写高效、可维护的代码。在实际应用中，应根据具体需求和数据操作模式，明智地选择合适的数据结构。