Java LinkedList addFirst() 方法详解

Java LinkedList Java LinkedList

addFirst() 是 LinkedList 类中的一个重要方法，用于在链表的开头插入指定元素。

方法语法

public void addFirst(E e)

参数说明

E e：要添加到链表开头的元素

返回值

此方法没有返回值（void）。

addFirst() 方法的工作原理

addFirst() 方法的工作原理可以简单描述为：

  1. 创建一个新的节点（Node）对象
  2. 将新节点的 next 指针指向当前的头节点
  3. 将当前头节点的 prev 指针指向新节点
  4. 将链表的 head 指针更新为新节点
  5. 如果链表之前为空，则将尾节点也指向新节点
  6. 增加链表的大小计数（size++）

时间复杂度

addFirst() 方法的时间复杂度是 O(1)，因为无论链表有多大，它只需要执行固定数量的操作。

使用示例

让我们通过几个例子来看看 addFirst() 方法的具体用法。

示例 1：基本用法

实例

import java.util.LinkedList;

public class AddFirstExample {
    public static void main(String[] args) {
        // 创建一个 LinkedList
        LinkedList<String> fruits = new LinkedList<>();
       
        // 添加初始元素
        fruits.add("Banana");
        fruits.add("Orange");
       
        System.out.println("原始链表: " + fruits);  // 输出: [Banana, Orange]
       
        // 使用 addFirst() 在开头添加元素
        fruits.addFirst("Apple");
       
        System.out.println("添加后链表: " + fruits);  // 输出: [Apple, Banana, Orange]
    }
}

示例 2：连续添加

实例

import java.util.LinkedList;

public class ContinuousAddFirst {
    public static void main(String[] args) {
        LinkedList<Integer> numbers = new LinkedList<>();
       
        // 连续使用 addFirst() 添加元素
        numbers.addFirst(3);
        numbers.addFirst(2);
        numbers.addFirst(1);
       
        System.out.println(numbers);  // 输出: [1, 2, 3]
       
        // 注意添加顺序和最终结果的顺序关系
    }
}

示例 3：与 add() 方法的区别

实例

import java.util.LinkedList;

public class AddVsAddFirst {
    public static void main(String[] args) {
        LinkedList<String> list1 = new LinkedList<>();
        LinkedList<String> list2 = new LinkedList<>();
       
        // 使用 add() 方法添加元素
        list1.add("A");
        list1.add("B");
        list1.add("C");
       
        // 使用 addFirst() 方法添加相同的元素
        list2.addFirst("C");
        list2.addFirst("B");
        list2.addFirst("A");
       
        System.out.println("使用 add(): " + list1);    // 输出: [A, B, C]
        System.out.println("使用 addFirst(): " + list2); // 输出: [A, B, C]
       
        // 虽然最终结果相同，但添加顺序相反
    }
}

注意事项

在使用 addFirst() 方法时，需要注意以下几点：

1.与add()方法的区别

  • add()方法默认将元素添加到链表末尾
  • addFirst()方法将元素添加到链表开头

2.与offerFirst()方法的区别

  • addFirst()在容量受限的队列中可能会抛出异常
  • offerFirst()在容量受限的队列中会返回false而不是抛出异常

3.空值处理

LinkedList允许添加null值，因此addFirst(null)是合法的。

4.线程安全

LinkedList不是线程安全的，如果在多线程环境中使用addFirst()，需要外部同步。

实际应用场景

addFirst() 方法在以下场景中特别有用：

1. 实现栈结构

由于栈是"后进先出"(LIFO)的结构，可以使用 addFirst() 和 removeFirst() 来模拟栈的操作。

实例

LinkedList<String> stack = new LinkedList<>();
stack.addFirst("Task1");  // 入栈
stack.addFirst("Task2");  // 入栈
String top = stack.removeFirst();  // 出栈，返回 "Task2"

2. 最近使用列表

在实现最近使用(MRU)列表时，新访问的项目可以添加到列表开头。

3. 反转操作

通过将元素逐个 addFirst() 到新列表，可以实现列表反转。

实例

LinkedList<Integer> original = new LinkedList<>(Arrays.asList(1, 2, 3));
LinkedList<Integer> reversed = new LinkedList<>();

for (Integer num : original) {
    reversed.addFirst(num);
}

System.out.println(reversed);  // 输出: [3, 2, 1]

性能考虑

addFirst() 方法在 LinkedList 中的性能非常好，因为它只需要：

  1. 创建一个新节点
  2. 调整几个指针

无论链表有多大，这些操作的时间都是恒定的（O(1)时间复杂度）。这与 ArrayList 的 add(0, element) 操作形成鲜明对比，后者需要移动所有现有元素（O(n)时间复杂度）。

因此，如果需要频繁在集合开头添加元素，LinkedList 是比 ArrayList 更好的选择。

常见问题解答

Q1: addFirst() 会覆盖现有元素吗？

不会，addFirst()只是在链表开头插入一个新元素，不会覆盖任何现有元素。

Q2: 如果链表为空，addFirst() 还能工作吗？

可以，如果链表为空，addFirst() 会将新元素作为链表的第一个也是唯一一个元素。

Q3: addFirst() 和 push() 有什么区别？

在LinkedList中，addFirst()和push()是完全相同的方法。push()只是addFirst()的另一个名称，用于使LinkedList可以作为栈使用。

Q4: 为什么我的 IDE 提示 addFirst() 是 Deque 的方法？

因为LinkedList实现了Deque接口，addFirst()实际上是Deque接口中定义的方法，LinkedList提供了它的实现。

总结

LinkedList 的 addFirst() 方法是一个高效的操作，它允许我们在链表的开头插入元素。理解这个方法对于有效使用 LinkedList 非常重要，特别是在需要频繁在集合开头插入元素的场景中。

关键点回顾：

  • addFirst() 在链表开头插入元素
  • 时间复杂度为 O(1)
  • 与 add() 方法添加位置不同
  • 常用于实现栈结构和最近使用列表
  • 在多线程环境中需要额外同步

通过合理使用 addFirst() 方法，可以充分发挥 LinkedList 在特定场景下的性能优势。

Java LinkedList Java LinkedList