Java LinkedList

📌 目录

1. 什么是 LinkedList？
2. LinkedList 的特性
3. 创建和初始化 LinkedList
4. LinkedList 常用方法
   • 4.1 添加元素
   • 4.2 访问元素
   • 4.3 修改元素
   • 4.4 删除元素
   • 4.5 检查元素
   • 4.6 清空集合
5. LinkedList 性能
6. LinkedList 和 ArrayList 的比较
7. 总结
8. 参考资料
9. 出站链接

1. 什么是 LinkedList？

LinkedList 是 Java 集合框架中的一个实现类，属于 List 接口的实现。与 ArrayList 不同，LinkedList 是基于双向链表实现的，它可以方便地在列表头部或尾部进行插入和删除操作。LinkedList 可以存储重复的元素，并且元素是有序的。

LinkedList 提供了对元素的高效插入、删除和查找操作，尤其适用于频繁进行插入和删除的场景。

2. LinkedList 的特性

• 基于双向链表：每个元素都包含指向前一个元素和下一个元素的指针。
• 允许重复元素：与 ArrayList 一样，LinkedList 允许存储重复元素。
• 有序：LinkedList 保持元素的插入顺序，访问时按照插入顺序返回。
• 线程不安全：LinkedList 不是线程安全的，如果在多线程环境中使用，需手动同步。
• 插入/删除操作高效：LinkedList 在列表头部或尾部进行插入和删除操作时时间复杂度为 O(1)，在列表中间进行操作时，仍然需要遍历链表。

3. 创建和初始化 LinkedList

创建空的 LinkedList

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        System.out.println("LinkedList created: " + list);
    }
}

创建并初始化 LinkedList

import java.util.LinkedList;
import java.util.Arrays;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>(Arrays.asList("Java", "Python", "C++"));
        System.out.println("LinkedList initialized: " + list);
    }
}

4. LinkedList 常用方法

4.1 添加元素

• add(E e)：将指定元素添加到 LinkedList 的末尾。
• addFirst(E e)：将指定元素添加到列表的头部。
• addLast(E e)：将指定元素添加到列表的尾部。

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.addFirst("C++");  // 在头部添加元素
list.addLast("Python");  // 在尾部添加元素

4.2 访问元素

• get(int index)：返回指定位置的元素。
• getFirst()：返回第一个元素。
• getLast()：返回最后一个元素。

String language = list.get(1);  // 获取索引为 1 的元素
String first = list.getFirst();  // 获取第一个元素
String last = list.getLast();  // 获取最后一个元素

4.3 修改元素

• set(int index, E element)：将指定位置的元素替换为新的元素。

list.set(0, "Go");  // 将索引为 0 的元素修改为 "Go"

4.4 删除元素

• remove(int index)：删除指定位置的元素。
• remove(Object o)：删除指定的元素。
• removeFirst()：删除第一个元素。
• removeLast()：删除最后一个元素。

list.remove(1);  // 删除索引为 1 的元素
list.remove("Python");  // 删除元素 "Python"
list.removeFirst();  // 删除第一个元素
list.removeLast();  // 删除最后一个元素

4.5 检查元素

• contains(Object o)：判断集合中是否包含指定元素。
• size()：返回集合中元素的个数。
• isEmpty()：判断集合是否为空。

boolean contains = list.contains("Go");  // 判断是否包含 "Go"
int size = list.size();  // 获取集合的大小
boolean isEmpty = list.isEmpty();  // 判断集合是否为空

4.6 清空集合

• clear()：删除集合中的所有元素。

list.clear();  // 清空集合

5. LinkedList 性能

• 访问元素：通过索引访问元素的时间复杂度为 O(n)，因为需要遍历链表。
• 添加元素：在头部或尾部添加元素的时间复杂度为 O(1)。
• 删除元素：删除元素的时间复杂度为 O(1)，尤其是在头部或尾部。
• 查找元素：查找元素的时间复杂度为 O(n)，需要遍历链表。

6. LinkedList 和 ArrayList 的比较

• LinkedList 适用于频繁进行插入和删除操作，特别是当操作发生在列表的头部或尾部时。
• ArrayList 适用于频繁进行随机访问操作，特别是在元素数量较大时。

7. 总结

LinkedList 是 Java 集合框架中的一种基于链表的数据结构，适合于需要频繁插入、删除操作的场景。与 ArrayList 相比，LinkedList 在插入和删除操作上具有更高的性能，尤其是在头部或尾部进行操作时。但它的缺点是访问元素的效率较低，需要遍历链表。

8. 参考资料

• Java Collections Framework Documentation
• GeeksforGeeks – LinkedList in Java
• Baeldung – Guide to Java LinkedList

9. 出站链接

• W3Schools – Java LinkedList
• TutorialsPoint – LinkedList in Java