Java 中的 LinkedList 全面解析

简介

在 Java 编程中，LinkedList 是一个非常重要的数据结构，它是 List 接口的实现类，同时也实现了 Deque 接口，这使得它既可以作为列表使用，也能当作双端队列来用。与 ArrayList 不同，LinkedList 采用链表的数据结构，这决定了它在插入和删除操作上具有更好的性能，尤其适用于频繁进行插入和删除元素的场景。本文将详细介绍 LinkedList 的基础概念、使用方法、常见实践以及最佳实践，帮助读者深入理解并高效使用 LinkedList。

基础概念

链表结构

LinkedList 内部采用双向链表的数据结构来存储元素。每个节点（Node）包含三个部分：前一个节点的引用（prev）、当前节点存储的数据（item）以及后一个节点的引用（next）。这种结构使得 LinkedList 在插入和删除元素时，只需要修改相应节点的引用，而不需要像 ArrayList 那样移动大量元素，因此在插入和删除操作上效率更高。

继承与实现关系

LinkedList 继承自 AbstractSequentialList 类，实现了 List、Deque、Cloneable 和 java.io.Serializable 接口。这意味着 LinkedList 不仅具备列表的基本功能，还可以作为双端队列使用，支持从队列的两端进行元素的插入和删除操作。

使用方法

创建 LinkedList 对象

import java.util.LinkedList;

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

        // 创建一个包含初始元素的 LinkedList
        LinkedList<Integer> numbers = new LinkedList<>(java.util.Arrays.asList(1, 2, 3, 4, 5));
    }
}

添加元素

import java.util.LinkedList;

public class AddElementsExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();

        // 在列表末尾添加元素
        linkedList.add("Apple");
        linkedList.add("Banana");

        // 在指定位置插入元素
        linkedList.add(1, "Cherry");

        // 在列表头部添加元素
        linkedList.addFirst("Strawberry");

        // 在列表尾部添加元素
        linkedList.addLast("Grape");

        System.out.println(linkedList);
    }
}

删除元素

import java.util.LinkedList;

public class RemoveElementsExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>(java.util.Arrays.asList("Apple", "Banana", "Cherry"));

        // 删除指定位置的元素
        linkedList.remove(1);

        // 删除列表头部的元素
        linkedList.removeFirst();

        // 删除列表尾部的元素
        linkedList.removeLast();

        System.out.println(linkedList);
    }
}

获取元素

import java.util.LinkedList;

public class GetElementsExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>(java.util.Arrays.asList("Apple", "Banana", "Cherry"));

        // 获取指定位置的元素
        String element = linkedList.get(1);
        System.out.println("Element at index 1: " + element);

        // 获取列表头部的元素
        String firstElement = linkedList.getFirst();
        System.out.println("First element: " + firstElement);

        // 获取列表尾部的元素
        String lastElement = linkedList.getLast();
        System.out.println("Last element: " + lastElement);
    }
}

常见实践

作为队列使用

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        // 入队操作
        queue.add("Apple");
        queue.add("Banana");
        queue.add("Cherry");

        // 出队操作
        String firstElement = queue.poll();
        System.out.println("Dequeued element: " + firstElement);

        // 查看队首元素
        String peekElement = queue.peek();
        System.out.println("Peeked element: " + peekElement);
    }
}

作为栈使用

import java.util.LinkedList;

public class StackExample {
    public static void main(String[] args) {
        LinkedList<String> stack = new LinkedList<>();

        // 入栈操作
        stack.push("Apple");
        stack.push("Banana");
        stack.push("Cherry");

        // 出栈操作
        String topElement = stack.pop();
        System.out.println("Popped element: " + topElement);
    }
}

最佳实践

根据场景选择合适的数据结构

如果需要频繁进行随机访问操作，建议使用 ArrayList；如果需要频繁进行插入和删除操作，尤其是在列表的头部或尾部，LinkedList 是更好的选择。

避免在中间位置频繁插入和删除元素

虽然 LinkedList 在插入和删除操作上具有优势，但在中间位置插入和删除元素时，需要遍历链表找到指定位置，效率会有所下降。因此，尽量避免在中间位置频繁进行插入和删除操作。

注意内存开销

由于 LinkedList 每个节点都需要额外的引用指针，因此相对于 ArrayList，它的内存开销会更大。在内存有限的情况下，需要谨慎使用。

小结

本文详细介绍了 Java 中的 LinkedList，包括其基础概念、使用方法、常见实践以及最佳实践。LinkedList 作为一种灵活的数据结构，在插入和删除操作上具有显著优势，同时还可以作为队列和栈使用。但在使用时，需要根据具体场景选择合适的数据结构，并注意其内存开销。通过掌握 LinkedList 的使用方法和最佳实践，读者可以更加高效地使用 LinkedList 解决实际问题。

参考资料

《Effective Java》（第三版），作者：Joshua Bloch