跳到主要内容

Java LinkedList

提示
  1. 数据结构特点：LinkedList 是一个双向链表，其中每个节点包含前驱指针、数据和后继指针。
  2. 创建和基本操作：可创建类型特定的 LinkedList，支持添加、访问、修改和移除元素等基本操作。
  3. 多接口实现：除实现 List 接口外，LinkedList 也实现了 Queue 和 Deque 接口，支持队列和双端队列的操作。

Java 集合框架的 LinkedList 类提供了双向链表数据结构的功能。

一个双向链表的单个节点，包含 3 个字段：Prev、Data 和 Next。

链表中的每个元素被称为节点。它由 3 个字段组成：

  • Prev - 存储列表中前一个元素的地址。对于第一个元素来说是 null
  • Next - 存储列表中下一个元素的地址。对于最后一个元素来说是 null
  • Data - 存储实际的数据

创建 Java LinkedList​

以下是我们在 Java 中创建链表的方式：

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

这里，Type 指的是链表的类型。例如，

// 创建 Integer 类型的链表
LinkedList<Integer> linkedList = new LinkedList<>();

// 创建 String 类型的链表
LinkedList<String> linkedList = new LinkedList<>();

示例：在 Java 中创建 LinkedList​

import java.util.LinkedList;

class Main {
  public static void main(String[] args){

    // 创建链表
    LinkedList<String> animals = new LinkedList<>();

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

输出

LinkedList: [Dog, Cat, Cow]

在上面的示例中，我们创建了一个名为 animals 的 LinkedList。

这里，我们使用了 add() 方法向 LinkedList 添加元素。我们将在本教程后面更多地学习 add() 方法。

Java LinkedList 的工作原理​

链表中的元素不是按顺序存储的。相反，它们通过链接（Prev 和 Next）散布并相连。

3 个链表节点，通过指针互相连接

这里我们有一个链表中的 3 个元素。

  • Dog - 它是第一个元素，前一个地址持有 null，下一个地址是 Cat
  • Cat - 它是第二个元素，前一个地址是 Dog，下一个地址是 Cow
  • Cow - 它是最后一个元素，前一个地址是 Cat，下一个地址是 null

要了解更多，请访问 链表数据结构。

Java LinkedList 的方法​

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

  • 添加元素
  • 访问元素
  • 更改元素
  • 移除元素

1. 向 LinkedList 添加元素​

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

import java.util.LinkedList;

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

    // 没有索引参数的 add() 方法
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Cow");
    System.out.println("LinkedList: " + animals);

    // 带索引参数的 add() 方法
    animals.add(1, "Horse");
    System.out.println("更新后的 LinkedList: " + animals);
  }
}

输出

LinkedList: [Dog, Cat, Cow]
更新后的 LinkedList: [Dog, Horse, Cat, Cow]

在上述示例中，我们创建了一个名为 animals 的 LinkedList。这里，我们使用了 add() 方法向 animals 添加元素。

注意以下语句，

animals.add(1, "Horse");

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

要了解更多关于向 LinkedList 添加元素的信息，请访问 Java 程序：向 LinkedList 添加元素。

2. 访问 LinkedList 元素​

LinkedList 类的 get() 方法用于从 LinkedList 访问一个元素。例如，

import java.util.LinkedList;

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("索引 1 处的元素: " + str);
  }
}

输出

LinkedList: [Python, Java, JavaScript]
索引 1 处的元素: Java

在上述示例中，我们使用了带参数 1 的 get() 方法。这里，该方法返回索引 1 处的元素。

我们还可以使用 iterator() 和 listIterator() 方法访问 LinkedList 的元素。要了解更多，请访问 Java 程序：访问 LinkedList 的元素。

3. 更改 LinkedList 的元素​

LinkedList 类的 set() 方法用于更改 LinkedList 的元素。例如，

import java.util.LinkedList;

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);

    // 更改索引 3 处的元素
    languages.set(3, "Kotlin");
    System.out.println("更新后的 LinkedList: " + languages);
  }
}

输出

LinkedList: [Java, Python, JavaScript, Java]
更新后的 LinkedList: [Java, Python, JavaScript, Kotlin]

在上述示例中，我们创建了一个名为 languages 的 LinkedList。注意以下行，

languages.set(3, "Kotlin");

这里，set() 方法更改了索引 3 处的元素为 Kotlin。

4. 从 LinkedList 中移除元素​

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

import java.util.LinkedList;

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

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

    // 从索引 1 处移除元素
    String str = languages.remove(1);
    System.out.println("移除的元素: " + str);

    System.out.println("更新后的 LinkedList: " + languages);
  }
}

输出

LinkedList: [Java, Python, JavaScript, Kotlin]
移除的元素: Python
更新后的 LinkedList: [Java, JavaScript, Kotlin]

这里，remove() 方法以索引号作为参数，并移除了由该索引号指定的元素。

要了解更多关于从链表中移除元素的信息，请访问 Java 程序：从 LinkedList 中移除元素。

其他方法​

方法描述
contains()检查 LinkedList 是否包含元素
indexOf()返回第一次

出现的元素的索引 | | lastIndexOf() | 返回最后一次出现的元素的索引 | | clear() | 移除 LinkedList 中的所有元素 | | iterator() | 返回一个迭代器，用于遍历 LinkedList |

LinkedList 作为 Deque 和 Queue​

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

方法描述
addFirst()在链表的开头添加指定的元素
addLast()在链表的末尾添加指定的元素
getFirst()返回第一个元素
getLast()返回最后一个元素
removeFirst()移除第一个元素
removeLast()移除最后一个元素
peek()返回链表的第一个元素（头部）
poll()返回并移除链表的第一个元素
offer()在链表的末尾添加指定的元素

示例：Java LinkedList 作为 Queue​

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

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("访问的元素: " + str1);

    // 访问并移除第一个元素
    String str2 = languages.poll();
    System.out.println("移除的元素: " + str2);
    System.out.println("poll() 后的 LinkedList: " + languages);

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

输出

LinkedList: [Python, Java, C]
访问的元素: Python
移除的元素: Python
poll() 后的 LinkedList: [Java, C]
offer() 后的 LinkedList: [Java, C, Swift]

示例：LinkedList 作为 Deque​

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

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("addFirst() 后的 LinkedList: " + animals);

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

    // 移除第一个元素
    animals.removeFirst();
    System.out.println("removeFirst() 后的 LinkedList: " + animals);

    // 移除最后一个元素
    animals.removeLast();
    System.out.println("removeLast() 后的 LinkedList: " + animals);
  }
}

输出

LinkedList: [Cow]
在 addFirst() 后的 LinkedList: [Dog, Cow]
在 addLast() 后的 LinkedList: [Dog, Cow, Zebra]
在 removeFirst() 后的 LinkedList: [Cow, Zebra]
在 removeLast() 后的 LinkedList: [Cow]

遍历 LinkedList​

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

import java.util.LinkedList;

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);

        // 使用 forEach 循环
        System.out.println("访问链表中的元素:");
        for(String animal: animals) {
            System.out.print(animal);
            System.out.print(", ");
        }
    }
}

输出

LinkedList: [Cow, Cat, Dog]
访问链表中的元素:
Cow, Cat, Dog,

LinkedList 与 ArrayList 的比较​

Java ArrayList 和 LinkedList 都实现了 Collections 框架的 List 接口。然而，它们之间存在一些区别。

LinkedListArrayList
实现了 List、Queue 和 Deque 接口。实现了 List 接口。
在一个位置存储 3 个值（前一个地址、数据 和 下一个地址）。在一个位置存储单个值。
提供双向链表的实现。提供可调整大小的数组实现。
每当添加一个元素时，需要更改 prev 和 next 地址。每当添加一个元素时，该位置后的所有元素都会被移动。
要访问一个元素，我们需要从头开始遍历到该元素。可以使用索引随机访问元素。

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

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

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

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

这里，如果 LinkedList 是使用一个接口创建的，那么我们不能使用其他接口提供的方法。即 animals1 不能使用 Queue 和 Deque 接口特有的方法。

最后于 更新