Java LinkedList 示例详解

简介

在 Java 编程中，LinkedList 是一个非常重要的数据结构。它实现了 List 接口和 Deque 接口，提供了基于链表的数据存储方式。与数组不同，LinkedList 在内存中并非连续存储元素，而是通过节点之间的引用关系来组织数据。这使得它在插入和删除操作上具有较高的效率，尤其适用于需要频繁进行此类操作的场景。本文将通过一系列示例深入探讨 LinkedList 的基础概念、使用方法、常见实践以及最佳实践。

目录

1. 基础概念
2. 使用方法
   • 创建 LinkedList
   • 添加元素
   • 访问元素
   • 修改元素
   • 删除元素
3. 常见实践
   • 遍历 LinkedList
   • 查找元素
   • 排序 LinkedList
4. 最佳实践
   • 选择合适的操作方法
   • 内存管理
   • 性能优化
5. 小结
6. 参考资料

基础概念

LinkedList 由一系列节点组成，每个节点包含数据以及指向前一个节点和后一个节点的引用（双向链表）。这种结构使得在链表的任意位置插入和删除元素的时间复杂度为 O(1)，而访问元素的时间复杂度为 O(n)，因为需要从链表头部或尾部开始遍历查找。

使用方法

创建 LinkedList

import java.util.LinkedList;

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

添加元素

import java.util.LinkedList;

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

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

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

        System.out.println(linkedList);
    }
}

访问元素

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Cherry");

        // 获取指定位置的元素
        String element = linkedList.get(1);
        System.out.println(element);

        // 获取链表头部元素
        String firstElement = linkedList.getFirst();
        System.out.println(firstElement);

        // 获取链表尾部元素
        String lastElement = linkedList.getLast();
        System.out.println(lastElement);
    }
}

修改元素

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Cherry");

        // 修改指定位置的元素
        linkedList.set(1, "Durian");
        System.out.println(linkedList);
    }
}

删除元素

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Cherry");

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

        // 删除指定元素
        linkedList.remove("Apple");
        System.out.println(linkedList);

        // 删除链表头部元素
        linkedList.removeFirst();
        System.out.println(linkedList);

        // 删除链表尾部元素
        linkedList.removeLast();
        System.out.println(linkedList);
    }
}

常见实践

遍历 LinkedList

• 使用 for 循环

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Cherry");

        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.get(i));
        }
    }
}

• 使用 foreach 循环

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Cherry");

        for (String element : linkedList) {
            System.out.println(element);
        }
    }
}

• 使用迭代器

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

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Cherry");

        Iterator<String> iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

查找元素

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Cherry");

        boolean contains = linkedList.contains("Banana");
        System.out.println(contains);

        int index = linkedList.indexOf("Cherry");
        System.out.println(index);
    }
}

排序 LinkedList

import java.util.Collections;
import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.add(3);
        linkedList.add(1);
        linkedList.add(2);

        Collections.sort(linkedList);
        System.out.println(linkedList);
    }
}

最佳实践

选择合适的操作方法

在需要频繁插入和删除元素时，LinkedList 是一个很好的选择。但如果需要频繁随机访问元素，数组或 ArrayList 可能更合适。例如，在实现一个任务队列时，LinkedList 可以高效地进行任务的添加和取出操作。

内存管理

由于 LinkedList 每个节点都包含额外的引用，相比于数组，它会占用更多的内存。因此，在处理大量数据时，需要注意内存的使用情况。可以适时地清理不再使用的链表节点，以释放内存。

性能优化

尽量避免在 LinkedList 中进行大量的随机访问操作，因为这会导致性能下降。如果需要频繁访问元素，可以考虑将 LinkedList 转换为 ArrayList。另外，在遍历 LinkedList 时，使用迭代器比使用 for 循环通过索引访问更高效。

小结

通过本文的介绍，我们深入了解了 Java 中 LinkedList 的基础概念、使用方法、常见实践以及最佳实践。LinkedList 在处理需要频繁插入和删除操作的数据时具有显著优势，但在使用过程中需要根据具体需求选择合适的操作方法，并注意内存管理和性能优化。希望这些知识能帮助读者在实际编程中更高效地使用 LinkedList。

参考资料

• Oracle Java 官方文档 - LinkedList
• 《Effective Java》
• 《Java 核心技术》