LinkedList

在 Java 中，LinkedList 是 java.util 包中的一个类，实现了 List 接口和 Deque 接口。它是基于双向链表的数据结构，适合频繁插入和删除数据的场景。

---

✅ 1. LinkedList 的特点

• 链表结构：每个节点包含数据和指向前后节点的引用。
• 插入和删除效率高：在链表中增加或删除元素的时间复杂度为 O(1)。
• 访问效率低：由于不是基于数组的结构，查找元素的时间复杂度为 O(n)。
• 双向链表：支持从头到尾和从尾到头的遍历。

---

✅ 2. 创建 LinkedList

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // 创建一个存储字符串的 LinkedList
        LinkedList<String> list = new LinkedList<>();

        // 添加元素
        list.add("苹果");
        list.add("香蕉");
        list.add("橘子");

        System.out.println("初始链表: " + list);
    }
}

---

✅ 3. 常用方法

方法	描述
add(E e)	添加元素到链表尾部
addFirst(E e)	在链表头部添加元素
addLast(E e)	在链表尾部添加元素
remove()	删除并返回头部元素
removeFirst()	删除并返回头部元素
removeLast()	删除并返回尾部元素
get(int index)	获取指定位置的元素
getFirst()	获取头部元素
getLast()	获取尾部元素
size()	获取链表长度
isEmpty()	判断链表是否为空
contains(Object o)	判断链表是否包含某个元素
clear()	清空链表

---

✅ 4. 示例：基本操作

import java.util.LinkedList;

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

        // 添加元素
        list.add("Java");
        list.add("Python");
        list.addFirst("C++");    // 添加到头部
        list.addLast("JavaScript"); // 添加到尾部

        System.out.println("链表内容: " + list);

        // 获取元素
        System.out.println("第一个元素: " + list.getFirst());
        System.out.println("最后一个元素: " + list.getLast());
        System.out.println("索引1的元素: " + list.get(1));

        // 删除元素
        list.removeFirst();  // 删除头部元素
        list.removeLast();   // 删除尾部元素
        System.out.println("删除后的链表: " + list);

        // 判断元素是否存在
        System.out.println("是否包含 Python: " + list.contains("Python"));

        // 清空链表
        list.clear();
        System.out.println("清空后链表是否为空: " + list.isEmpty());
    }
}

---

✅ 5. LinkedList 的遍历方式

方式一：普通 for 循环

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

方式二：增强 for 循环

for (String s : list) {
    System.out.println(s);
}

方式三：使用 Iterator

import java.util.Iterator;

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

方式四：使用 Lambda 表达式

list.forEach(s -> System.out.println(s));

---

✅ 6. LinkedList vs ArrayList

特性	LinkedList	ArrayList
底层结构	双向链表	动态数组
插入和删除	O(1)（在头部或尾部）	O(n)（中间位置需要移动元素）
查找元素	O(n)	O(1)
内存占用	较高（需要额外存储前后指针）	较低（只存储数据）
适用场景	频繁插入、删除数据	频繁随机访问数据

• 如果需要快速插入和删除，使用 LinkedList。
• 如果需要频繁访问元素，使用 ArrayList。

---

✅ 总结

• LinkedList 是基于双向链表实现的，插入和删除效率高。
• 支持队列和栈操作，可以当作双端队列使用。
• 不适合大量的随机访问，推荐在需要频繁增删的场景中使用。