Java LinkedList 是 Java 的 List 和 Deque 接口的 doubly linked list 实现。它是 Java 集合框架的一部分。这是LinkedList的类层次结构

以下是有关 Java 中的 LinkedList 的一些注意事项 -

• Java LinkedList 维护元素的插入顺序。
• LinkedList 可以有重复值和空值。
• LinkedList 类实现了 [Queue](https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html) 和 [Deque](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) 接口。因此，它也可以用作 Queue、Deque 或 Stack。
• Java LinkedList 不是线程安全的。您必须在多线程环境中显式同步对 LinkedList 的并发修改。

Java ArrayList 与 LinkedList

ArrayList 和 LinkedList 都实现了 List 接口。但是，它们在存储和链接到元素的方式上完全不同。

ArrayList 根据元素的索引顺序存储元素。但是，LinkedList 使用双向链表来存储其元素。

双向链表由节点集合组成，其中每个节点包含三个字段 -

• 该节点的数据。
• 指向列表中下一个节点的指针/引用。
• 指向列表中前一个节点的指针/引用。

以下是 ArrayList 和 LinkedList 数据结构的示意图：

以下是 LinkedList 和 ArrayList 之间的一些主要区别：

• LinkedList 比 ArrayList 消耗更多内存，因为它还存储下一个和上一个引用以及数据。
• 您可以在 O(1) 时间内访问 ArrayList 中的元素。但是访问 LinkedList 中的元素需要 O(n) 时间，因为它需要按照 next/prev 引用遍历到所需的元素。
• 在 ArrayList 中添加或删除元素通常比 LinkedList 慢。这是因为如果在 ArrayList 中间添加一个新元素，则需要移动 ArrayList 中的元素。 ArrayList 可能还需要调整大小以适应新元素。同样，在移除的情况下，需要将 ArrayList 中的元素移动到新位置。

创建一个 LinkedList 并向其中添加新元素

以下示例显示了如何创建 LinkedList 并向其添加新元素。请注意示例中 addFirst() 和 addLast() 方法的使用。这些方法来自 Deque 接口。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class CreateLinkedListExample {
    public static void main(String[] args) {
        // Creating a LinkedList
        LinkedList<String> friends = new LinkedList<>();

        // Adding new elements to the end of the LinkedList using add() method.
        friends.add("Rajeev");
        friends.add("John");
        friends.add("David");
        friends.add("Chris");

        System.out.println("Initial LinkedList : " + friends);

        // Adding an element at the specified position in the LinkedList
        friends.add(3, "Lisa");
        System.out.println("After add(3, \"Lisa\") : " + friends);

        // Adding an element at the beginning of the LinkedList
        friends.addFirst("Steve");
        System.out.println("After addFirst(\"Steve\") : " + friends);

        // Adding an element at the end of the LinkedList (This method is equivalent to the add() method)
        friends.addLast("Jennifer");
        System.out.println("After addLast(\"Jennifer\") : " + friends);

        // Adding all the elements from an existing collection to the end of the LinkedList
        List<String> familyFriends = new ArrayList<>();
        familyFriends.add("Jesse");
        familyFriends.add("Walt");

        friends.addAll(familyFriends);
        System.out.println("After addAll(familyFriends) : " + friends);
    }
}

# Output
Initial LinkedList : [Rajeev, John, David, Chris]
After add(3, "Lisa") : [Rajeev, John, David, Lisa, Chris]
After addFirst("Steve") : [Steve, Rajeev, John, David, Lisa, Chris]
After addLast("Jennifer") : [Steve, Rajeev, John, David, Lisa, Chris, Jennifer]
After addAll(familyFriends) : [Steve, Rajeev, John, David, Lisa, Chris, Jennifer, Jesse, Walt]

从 LinkedList 中检索元素

以下示例显示：

• 如何获取 LinkedList 中的第一个元素。
• 如何获取 LinkedList 中的最后一个元素。
• 如何获取 LinkedList 中给定索引处的元素。

import java.util.LinkedList;

public class RetrieveLinkedListElementsExample {
    public static void main(String[] args) {
        // A LinkedList containing Stock Prices of a company for the last 6 days
        LinkedList<Double> stockPrices = new LinkedList<>();

        stockPrices.add(45.00);
        stockPrices.add(51.00);
        stockPrices.add(62.50);
        stockPrices.add(42.75);
        stockPrices.add(36.80);
        stockPrices.add(68.40);

        // Getting the first element in the LinkedList using getFirst()
        // The getFirst() method throws NoSuchElementException if the LinkedList is empty
        Double firstElement = stockPrices.getFirst();
        System.out.println("Initial Stock Price : " + firstElement);

        // Getting the last element in the LinkedList using getLast()
        // The getLast() method throws NoSuchElementException if the LinkedList is empty
        Double lastElement = stockPrices.getLast();
        System.out.println("Current Stock Price : " + lastElement);

        // Getting the element at a given position in the LinkedList
        Double stockPriceOn3rdDay = stockPrices.get(2);
        System.out.println("Stock Price on 3rd Day : " + stockPriceOn3rdDay);
    }
}

# Output
Initial Stock Price : 45.0
Current Stock Price : 68.4
Stock Price on 3rd Day : 62.5

从 LinkedList 中删除元素

下面的示例显示：

• 如何删除 LinkedList 中的第一个元素。
• 如何删除 LinkedList 中的最后一个元素。
• 如何删除 LinkedList 中给定元素的第一次出现。
• 如何从 LinkedList 中删除所有满足给定谓词的元素。
• 如何彻底清除 LinkedList。

import java.util.LinkedList;

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

        programmingLanguages.add("Assembly");
        programmingLanguages.add("Fortran");
        programmingLanguages.add("Pascal");
        programmingLanguages.add("C");
        programmingLanguages.add("C++");
        programmingLanguages.add("Java");
        programmingLanguages.add("C#");
        programmingLanguages.add("Kotlin");

        System.out.println("Initial LinkedList = " + programmingLanguages);

        // Remove the first element in the LinkedList
        String element = programmingLanguages.removeFirst();  // Throws NoSuchElementException if the LinkedList is empty
        System.out.println("Removed the first element " + element + " => " + programmingLanguages);

        // Remove the last element in the LinkedList
        element = programmingLanguages.removeLast();   // Throws NoSuchElementException if the LinkedList is empty
        System.out.println("Removed the last element " + element + " => " + programmingLanguages);

        // Remove the first occurrence of the specified element from the LinkedList
        boolean isRemoved = programmingLanguages.remove("C#");
        if(isRemoved) {
            System.out.println("Removed C# => " + programmingLanguages);
        }

        // Remove all the elements that satisfy the given predicate
        programmingLanguages.removeIf(programmingLanguage -> programmingLanguage.startsWith("C"));
        System.out.println("Removed elements starting with C => " + programmingLanguages);

        // Clear the LinkedList by removing all elements
        programmingLanguages.clear();
        System.out.println("Cleared the LinkedList => " + programmingLanguages);
    }
}

# Output
Initial LinkedList = [Assembly, Fortran, Pascal, C, C++, Java, C#, Kotlin]
Removed the first element Assembly => [Fortran, Pascal, C, C++, Java, C#, Kotlin]
Removed the last element Kotlin => [Fortran, Pascal, C, C++, Java, C#]
Removed C# => [Fortran, Pascal, C, C++, Java]
Removed elements starting with C => [Fortran, Pascal, Java]
Cleared the LinkedList => []

在 LinkedList 中搜索元素

下面的示例显示：

• 如何检查一个元素是否存在于 LinkedList 中。
• 如何在 LinkedList 中找到元素第一次出现的索引。
• 如何在 LinkedList 中查找元素最后一次出现的索引。

import java.util.LinkedList;

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

        employees.add("John");
        employees.add("David");
        employees.add("Lara");
        employees.add("Chris");
        employees.add("Steve");
        employees.add("David");

        // Check if the LinkedList contains an element
        System.out.println("Does Employees LinkedList contain \"Lara\"? : " + employees.contains("Lara"));

        // Find the index of the first occurrence of an element in the LinkedList
        System.out.println("indexOf \"Steve\" : " + employees.indexOf("Steve"));
        System.out.println("indexOf \"Mark\" : " + employees.indexOf("Mark"));

        // Find the index of the last occurrence of an element in the LinkedList
        System.out.println("lastIndexOf \"David\" : " + employees.lastIndexOf("David"));
        System.out.println("lastIndexOf \"Bob\" : " + employees.lastIndexOf("Bob"));
    }
}

# Output
Does Employees LinkedList contain "Lara"? : true
indexOf "Steve" : 4
indexOf "Mark" : -1
lastIndexOf "David" : 5
lastIndexOf "Bob" : -1

遍历链表

下面的例子展示了如何迭代一个 LinkedList 使用

• Java 8 forEach() 和 lambda 表达式。
• 迭代器（）
• iterator() 和 Java 8 forEachRemaining() 方法
• 降序迭代器()
• 列表迭代器（）
• 简单的 for-each 循环。

import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;

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

        humanSpecies.add("Homo Sapiens");
        humanSpecies.add("Homo Neanderthalensis");
        humanSpecies.add("Homo Erectus");
        humanSpecies.add("Home Habilis");

        System.out.println("=== Iterate over a LinkedList using Java 8 forEach and lambda ===");
        humanSpecies.forEach(name -> {
            System.out.println(name);
        });


        System.out.println("\n=== Iterate over a LinkedList using iterator() ===");
        Iterator<String> humanSpeciesIterator = humanSpecies.iterator();
        while (humanSpeciesIterator.hasNext()) {
            String speciesName = humanSpeciesIterator.next();
            System.out.println(speciesName);
        }

        System.out.println("\n=== Iterate over a LinkedList using iterator() and Java 8 forEachRemaining() method ===");
        humanSpeciesIterator = humanSpecies.iterator();
        humanSpeciesIterator.forEachRemaining(speciesName -> {
            System.out.println(speciesName);
        });

        System.out.println("\n=== Iterate over a LinkedList using descendingIterator() ===");
        Iterator<String> descendingHumanSpeciesIterator = humanSpecies.descendingIterator();
        while (descendingHumanSpeciesIterator.hasNext()) {
            String speciesName = descendingHumanSpeciesIterator.next();
            System.out.println(speciesName);
        }


        System.out.println("\n=== Iterate over a LinkedList using listIterator() ===");
        // ListIterator can be used to iterate over the LinkedList in both forward and backward directions
        // In this example, we start from the end of the list and traverse backwards
        ListIterator<String> humanSpeciesListIterator = humanSpecies.listIterator(humanSpecies.size());
        while (humanSpeciesListIterator.hasPrevious()) {
            String speciesName = humanSpeciesListIterator.previous();
            System.out.println(speciesName);
        }

        System.out.println("\n=== Iterate over a LinkedList using simple for-each loop ===");
        for(String speciesName: humanSpecies) {
            System.out.println(speciesName);
        }
    }
}

# Output
=== Iterate over a LinkedList using Java 8 forEach and lambda ===
Homo Sapiens
Homo Neanderthalensis
Homo Erectus
Home Habilis

=== Iterate over a LinkedList using iterator() ===
Homo Sapiens
Homo Neanderthalensis
Homo Erectus
Home Habilis

=== Iterate over a LinkedList using iterator() and Java 8 forEachRemaining() method ===
Homo Sapiens
Homo Neanderthalensis
Homo Erectus
Home Habilis

=== Iterate over a LinkedList using descendingIterator() ===
Home Habilis
Homo Erectus
Homo Neanderthalensis
Homo Sapiens

=== Iterate over a LinkedList using listIterator() ===
Home Habilis
Homo Erectus
Homo Neanderthalensis
Homo Sapiens

=== Iterate over a LinkedList using simple for-each loop ===
Homo Sapiens
Homo Neanderthalensis
Homo Erectus
Home Habilis

结论

这就是所有人！在本文中，您了解了什么是 LinkedList、LinkedList 和 ArrayList 之间的区别、如何创建 LinkedList、如何在 LinkedList 中添加、删除和搜索元素，以及如何迭代 LinkedList。