Java LinkedList

在本教程中，我们将通过示例详细了解 Java LinkedList 类。

LinkedList 类使用双向链表数据结构实现了列表 List 和双端队列 Deque 接口的所有功能。

创建 LinkedList

按如下方式使用构造方法创建 LinkedList 对象：

LinkedList<Type> linkedList = new LinkedList<>();

这里， Type 表示元素的数据类型。例如，

LinkedList<Integer> linkedList = new LinkedList<>();
LinkedList<String> linkedList = new LinkedList<>();

示例：在 Java 中创建 LinkedList

import java.util.LinkedList;

public class Main {
  public static void main(String[] args) {
    // 创建 LinkedList
    LinkedList<String> animals = new LinkedList<>();

    // 添加元素
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Cow");
    System.out.println("LinkedList: " + animals);
  }
}

输出

LinkedList: [Dog, Cat, Cow]

在上面的例子中，我们创建了一个 LinkedList 对象 animals，然后，我们使用了 add() 方法向 LinkedList 添加元素。

Java LinkedList 实现原理

LinkedList 类内部使用双向链表作为底层出数据结构。

双向链表中每个节点都有指向前驱节点和后续节点的指针，可以从向前或向后两个方向遍历所有节点。每个节点都定义了 3 个字段：

prev - 指向前驱节点。第一个节点的前驱节点为 null 。
next - 指向后续节点。最后一个节点的后续节点为 null 。
data - 存储实际数据

下图是一个双向链表节点的示意图：

双链表的单个节点，具有 3 个字段 Prev、Data 和 Next。 — Java 双向链表

回到上面的例子中的链表包含了 3 个元素，则在链表中有 3 个节点存储元素，并且每个节点都有字段指向前驱节点和后续节点。就像下图展示的那样：

这里我们在一个链表中有 3 个元素：

Dog - 位于第一个节点，节点前驱节点是 null, 后续节点存储 Cat 元素。
Cat - 位于第二个节点，节点前驱节点存储 Dog 元素, 后续节点存储 Cow 元素。
Cow - 位于第二个节点，节点前驱节点存储 Cat 元素, 后续节点是 null。

LinkedList 的方法

LinkedList 提供了多种方法，允许我们在链表中执行不同的操作。我们将在本教程中介绍四种常用的 LinkedList 操作有：

添加元素
访问元素
更改元素
删除元素

向 LinkedList 添加元素

add() 方法在 LinkedList 的末尾添加一个元素（节点）。例如，

import java.util.LinkedList;

public class Main {
  public static void main(String[] args) {
    // 创建 LinkedList
    LinkedList<String> animals = new LinkedList<>();

    animals.add("Dog");
    animals.add("Cat");
    animals.add("Cow");
    System.out.println("LinkedList: " + animals);

    // 在指定位置添加元素
    animals.add(1, "Horse");
    System.out.println("Updated LinkedList: " + animals);
  }
}

输出

LinkedList: [Dog, Cat, Cow]
Updated LinkedList: [Dog, Horse, Cat, Cow]

在上面的例子中，我们创建了一个 LinkedList 对象，并使用了 add() 方法向添加元素。

注意语句：

animals.add(1, "Horse");

在这里，我们使用了索引号参数。它是一个可选参数，用于指定新添加元素的位置。

访问 LinkedList 元素

get()方法被用于从 LinkedList 对象获取元素。例如，

import java.util.LinkedList;

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

    languages.add("Python");
    languages.add("Java");
    languages.add("JavaScript");
    System.out.println("LinkedList: " + languages);

    String str = languages.get(1);
    System.out.print("Element at index 1: " + str);
  }
}

输出

LinkedList: [Python, Java, JavaScript]
Element at index 1: Java

在上面的例子中，我们使用了参数为 1 的 get() 方法返回索引 1 处的元素。

我们还可以使用 iterator() 和 listIterator() 方法访问 LinkedList 的元素。

改变链表的元素

set() 方法用于更改 LinkedList 指定位置上的元素。例如，

import java.util.LinkedList;

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

    languages.add("Java");
    languages.add("Python");
    languages.add("JavaScript");
    languages.add("Java");
    System.out.println("LinkedList: " + languages);

    languages.set(3, "Kotlin");
    System.out.println("Updated LinkedList: " + languages);
  }
}

输出

LinkedList: [Java, Python, JavaScript, Java]
Updated LinkedList: [Java, Python, JavaScript, Kotlin]

在上面的例子中，我们使用 languages.set(3, "Kotlin") 将索引 3 出的元素更改为 Kotlin。

从 LinkedList 中移除元素

remove() 方法用于从 LinkedList 中删除一个元素。例如，

import java.util.LinkedList;

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

    languages.add("Java");
    languages.add("Python");
    languages.add("JavaScript");
    languages.add("Kotlin");
    System.out.println("LinkedList: " + languages);

    String str = languages.remove(1);
    System.out.println("Removed Element: " + str);

    System.out.println("Updated LinkedList: " + languages);
  }
}

输出

LinkedList: [Java, Python, JavaScript, Kotlin]
Removed Element: Python
Updated LinkedList: [Java, JavaScript, Kotlin]

这里，remove() 方法以索引号为参数，删除由索引号指定的元素。

其他方法

方法	描述
`contains()`	检查 LinkedList 是否包含该元素
`indexOf()`	返回指定元素第一次出现的索引
`lastIndexOf()`	返回指定元素最后一次出现的索引
`clear()`	删除 LinkedList 的所有元素
`iterator()`	返回一个迭代器来迭代 LinkedList

LinkedList 作为 Deque 和 Queue

由于 LinkedList 该类还实现了Queue和Deque接口，因此它也可以实现这些接口的方法。以下是一些常用的方法：

方法	说明
`addFirst()`	在队列的开头添加指定的元素
`addLast()`	在队列末尾添加指定元素
`getFirst()`	返回队列第一个元素
`getLast()`	返回队列最后一个元素
`removeFirst()`	删除队列第一个元素
`removeLast()`	删除队列最后一个元素
`peek()`	返回队列的第一个元素（头）
`poll()`	返回并移除队列中的第一个元素
`offer()`	在队列末尾添加指定元素

示例：LinkedList 用作队列

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

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

    // 添加元素
    languages.add("Python");
    languages.add("Java");
    languages.add("C");
    System.out.println("LinkedList: " + languages);

    // 获取队列第一个元素
    String str1 = languages.peek();
    System.out.println("Accessed Element: " + str1);

    // 删除队列第一个元素
    String str2 = languages.poll();
    System.out.println("Removed Element: " + str2);
    System.out.println("LinkedList after poll(): " + languages);

    // 在队尾添加元素
    languages.offer("Swift");
    System.out.println("LinkedList after offer(): " + languages);
  }
}

输出

LinkedList: [Python, Java, C]
Accessed Element: Python
Removed Element: Python
LinkedList after poll(): [Java, C]
LinkedList after offer(): [Java, C, Swift]

示例：LinkedList 用作双端队列

import java.util.LinkedList;
import java.util.Deque;

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

    // 在队头添加元素
    animals.add("Cow");
    System.out.println("LinkedList: " + animals);

    animals.addFirst("Dog");
    System.out.println("LinkedList after addFirst(): " + animals);

    // 在队尾添加元素
    animals.addLast("Zebra");
    System.out.println("LinkedList after addLast(): " + animals);

    // 删除队头元素
    animals.removeFirst();
    System.out.println("LinkedList after removeFirst(): " + animals);

    // 删除队尾元素
    animals.removeLast();
    System.out.println("LinkedList after removeLast(): " + animals);
  }
}

输出

LinkedList: [Cow]
LinkedList after addFirst(): [Dog, Cow]
LinkedList after addLast(): [Dog, Cow, Zebra]
LinkedList after removeFirst(): [Cow, Zebra]
LinkedList after removeLast(): [Cow]

遍历 LinkedList

我们可以使用 Java for-each 循环遍历 LinkedList。例如，

import java.util.LinkedList;

public class Main {
  public static void main(String[] args) {
    LinkedList<String> animals = new LinkedList<>();
    animals.add("Cow");
    animals.add("Cat");
    animals.add("Dog");
    System.out.println("LinkedList: " + animals);

    System.out.println("Accessing linked list elements:");
    for (String animal : animals) {
      System.out.print(animal);
      System.out.print(", ");
    }
  }
}

输出

LinkedList: [Cow, Cat, Dog]
Accessing linked list elements:
Cow, Cat, Dog,

LinkedList 与 ArrayList

在 Java 集合框架中，ArrayList 和 LinkedList 都实现了 List 接口，但它们之间存在一些差异。

下面列举了 LinkedList 与 ArrayList 之间的差异：

LinkedList 实现了 List ， Queue 和 Deque 接口；ArrayList 只实现了实现 List 接口。
LinkedList 使用双向链表作为底层数据结构； ArrayList 使用数组作为底层数据结。
LinkedList 使用索引随机访问速度慢； ArrayList 使用索引随机访问速度快。
LinkedList 插入元素效率高，只需要修改节点的指针； ArrayList 插入元素效率低，需要插入位置之后的所有元素，如果数组满了之后还需要对数组扩容

注意：我们还可以使用 Java 中的接口创建 LinkedList。例如，

LinkedList 的不同表现

LinkedList 实现了 List ， Queue 和 Deque 接口，每个接口的行为是不一样的，因此如果我们根据不同的接口构造了LinkedList 对象，则每个对象表现出来的行为是不同的。

如下：

// 使用 LinkedList 创建 List 对象
List<String> animals1 = new LinkedList<>();

// 使用 LinkedList 创建 Queue 对象
Queue<String> animals2 = new LinkedList<>();

// 使用 LinkedList 创建 Deque 对象
Deque<String> animals3 = new LinkedList<>();

上面 3 个对象虽然都由 LinkedList 构造出来，但是 animals1 不能使用 poll() 方法的，同样 animals2 不能使用 pollFirst() 方法。

实际开发中，我们要根据自己的需要构造对象。