Java 链表

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

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

<图>

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

上一页 - 存储列表中前一个元素的地址。它是null 对于第一个元素
下一步 - 存储列表中下一个元素的地址。 null 最后一个元素
数据 - 存储实际数据

创建一个 Java 链表

下面是我们如何在 Java 中创建链表：

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

在这里，类型 表示链表的类型。例如，

// create Integer type linked list
LinkedList<Integer> linkedList = new LinkedList<>();

// create String type linked list
LinkedList<String> linkedList = new LinkedList<>();

示例：在 Java 中创建 LinkedList

import java.util.LinkedList;

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

    // create linkedlist
    LinkedList<String> animals = new LinkedList<>();

    // Add elements to LinkedList
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Cow");
    System.out.println("LinkedList: " + animals);
  }
}

输出

LinkedList: [Dog, Cat, Cow]

在上面的例子中，我们创建了一个 LinkedList 命名为动物 .

在这里，我们使用了 add() 将元素添加到 LinkedList 的方法。我们将详细了解 add() 本教程后面的方法。

Java 链表的工作

链表中的元素不是按顺序存储的。相反，它们通过链接（Prev 和下一个 )。

<图>

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

狗 - 它是第一个包含 null 的元素作为以前的地址和 Cat 的地址作为下一个地址
猫 - 它是第二个拥有 Dog 地址的元素作为之前的地址和Cow的地址作为下一个地址
牛 - 它是保存 Cat 地址的最后一个元素作为前一个地址和 null 作为下一个元素

要了解更多信息，请访问 LinkedList 数据结构。

Java LinkedList的方法

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

添加元素
访问元素
改变元素
移除元素

1。将元素添加到 LinkedList

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

import java.util.LinkedList;

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

    // add() method without the index parameter
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Cow");
    System.out.println("LinkedList: " + animals);

    // add() method with the index parameter
    animals.add(1, "Horse");
    System.out.println("Updated LinkedList: " + animals);
  }
}

输出

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

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

注意声明，

animals.add(1, "Horse");

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

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

2.访问 LinkedList 元素

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

import java.util.LinkedList;

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

    // add elements in the linked list
    languages.add("Python");
    languages.add("Java");
    languages.add("JavaScript");
    System.out.println("LinkedList: " + languages);

    // get the element from the linked list
    String str = languages.get(1);
    System.out.print("Element at index 1: " + str);
  }
}

输出

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

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

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

3。更改 LinkedList 的元素

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

import java.util.LinkedList;

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

    // add elements in the linked list
    languages.add("Java");
    languages.add("Python");
    languages.add("JavaScript");
    languages.add("Java");
    System.out.println("LinkedList: " + languages);

    // change elements at index 3
    languages.set(3, "Kotlin");
    System.out.println("Updated LinkedList: " + languages);
  }
}

输出

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

在上面的示例中，我们创建了一个名为 Languages 的 LinkedList。注意这一行，

languages.set(3, "Kotlin");

这里，set() 方法更改索引 3 处的元素到 Kotlin .

4。从 LinkedList 中删除元素

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

import java.util.LinkedList;

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

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

    // remove elements from index 1
    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
New LinkedList: [Java, JavaScript, Kotlin]

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

要了解有关从链表中删除元素的更多信息，请访问 Java 程序以从链表中删除元素..

其他方法

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

LinkedList 作为双端队列和队列

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

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

示例：Java LinkedList 作为队列

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

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

    // add elements
    languages.add("Python");
    languages.add("Java");
    languages.add("C");
    System.out.println("LinkedList: " + languages);

    // access the first element
    String str1 = languages.peek();
    System.out.println("Accessed Element: " + str1);

    // access and remove the first element
    String str2 = languages.poll();
    System.out.println("Removed Element: " + str2);
    System.out.println("LinkedList after poll(): " + languages);

    // add element at the end
    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;

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

    // add element at the beginning
    animals.add("Cow");
    System.out.println("LinkedList: " + animals);

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

    // add elements at the end
    animals.addLast("Zebra");
    System.out.println("LinkedList after addLast(): " + animals);

    // remove the first element
    animals.removeFirst();
    System.out.println("LinkedList after removeFirst(): " + animals);

    // remove the last element
    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;

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

        // Using forEach loop
        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 对比。数组列表

Java ArrayList 和 LinkedList 实现 List Collections的界面框架。但是，它们之间存在一些差异。

LinkedList	数组列表
实现 `List` , `Queue` , 和 `Deque` 接口。	实现 `List` 界面。
存储 3 个值（上一个地址 , 数据, 和下一个地址 ) 在一个位置。	在单个位置存储单个值。
提供双向链表实现。	提供可调整大小的数组实现。
每当添加一个元素时，`prev` 和 `next` 地址变了。	每当添加一个元素时，该位置之后的所有元素都会移动。
要访问一个元素，我们需要从头开始迭代。	可以使用索引随机访问元素。

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

// create linkedlist using List
List<String> animals1 = new LinkedList<>();

// creating linkedlist using Queue
Queue<String> animals2 = new LinkedList<>();

// creating linkedlist using Deque
Deque<String> animals3 = new LinkedList<>();

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

Java 双端队列接口 Java ArrayDeque

java