Java LinkedList链表教程-6ren

Java LinkedList链表教程

转载作者：知者更新时间：2024-03-11 23:51:10

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。

文章推荐： Java ConcurrentHashMap: reduce() 方法示例

文章推荐： Spring Boot模板引擎FreeMarker、Groovy、Thymeleaf、Mustache介绍

文章推荐：如何从命令行运行 Spring Boot 应用程序

文章推荐： JavaArrayList列表介绍

数据结构-链表
今天我们将开始第二个数据类型-链表的学习，同样我们还是用最原始的方式，自己申请内存管理内存来实现一个链表。 01、01、定义什么是链表？链表在物理存储结构上表现为非顺序性和非连续性，因此链表
Java数据结构与算法学习笔记【链表】
前言：笔记是参考B站up主尚硅谷，图片、代码都是哦。在blog写笔记~（图片、代码来源尚硅谷，侵权必删！）尚硅谷数据结构学习路线B站网站：https://www.bilibili.com/video
C——链表
这个问题不太可能对任何 future 的访客有帮助；它只与一个较小的地理区域、一个特定的时间点或一个非常狭窄的情况相关，通常不适用于全世界的互联网受众。如需帮助使此问题更广泛适用，visit the
复制指向函数中结构体的指针(链表)
我想创建一个没有全局变量的单个链表。我用 NULL 初始化了第一个元素，然后想将第一个元素 node 复制到 list_。它被复制到函数中，但副作用不起作用。在我的主函数中，该值仍然是NULL。如果我
C++链表
我正在尝试使链表与此处的链表相似: linked list in C 那就是在另一个结构中有“头”，我首先称它为“头”。但是我发现做那个改变。很难向 list_item 结构添加值。我已经尝试了一些东
C - 链表
我正在尝试理解链表的代码。我明白他们是如何工作的。我正在查看一些与动态内存和链表有关的代码，我在此处对其进行了简化: #include #include typedef struct nod
C语言与队列/链表
有人可以解释下面的代码吗？我是 C 的新手，正在努力弄清楚。为什么我们最后有 queueNodeT？ typedef char queueElementT; typedef struct queueN
算法题..链表
场景如下:- 我想反转单链表的方向，换句话说，反转后所有指针现在应该指向后.. 这个算法应该需要线性时间。我想到的解决方案是使用另一个数据结构 A Stack.. 借助它可以轻松反转单向链表，所有指
Python 链表
在 python 中使用链表最简单的方法是什么？在 scheme 中，链表由 '(1 2 3 4 5) 定义。 Python 的列表 [1, 2, 3, 4, 5] 和元组 (1, 2, 3, 4,
图解LeetCode算法汇总——链表
本文首发公众号：小码A梦一般数据主要存储的形式主要有两种，一种是数组，一种是链表。数组是用来存储固定大小的同类型元素，存储在内存中是一片连续的空间。而链表就不同于数组。链表
arrays - 链表、数组和硬件内存缓存
虽然之前有人问过关于链表与数组的问题，但答案大多归结为我们大多数人在某个时候可能已经学到的东西: 列表擅长插入和删除数组擅长随机访问现在像 Bjarne Stroustrup 这样受人尊敬的人有
c - 链表。在哪里分配以及如何应对碎片化？
位置在堆中，碎片化(每个节点的 malloc) - 在几种不同的方式(缓慢分配，缓慢访问，内存碎片)方面效率低下在堆中，在一个大块中 - 当需要重新分配时，数据结构获得的所有灵活性都将丢失在堆
Java 泛型，链表
我完成了泛型的学习，但并不容易。不过，我确实明白了。这是我的理解。我希望您纠正我的错误并回答几个问题:)。 public class LinkedList { //class definition }
ocaml - 链表 OCaml
我将如何创建一个链接列表来在 OCaml 中保存我的数据？我正在尝试制作一个单链表，但是我遇到了语法问题。我只想制作一个模块来简单地从链表中获取'a，插入'a或删除'a。有人知道吗？最佳答案正如
C编程，动态分配+链表
我在使用这段代码时遇到了问题，我不确定我做错了什么 #include #include #include #include typedef struct flight_struct{
javascript - 链表 - 删除最后一个节点
我正在创建一个函数来删除给定列表的最后一个节点(作为参数输入)。该函数本身非常简单，如下所示。 function popBack(list) { var current = list.head
java - 链表 - 在当前节点之前插入一个节点
我正在尝试开发一种方法，该方法将在链接列表中的当前节点之前插入传递给它的节点。它有3个条件。对于此实现，不能有任何头节点(仅对列表中第一个节点的引用)，并且我无法添加更多变量。如果列表为空，则将传递
Scala 链表 stackoverflow
使用 scala，我已将大约 100000 个节点添加到链表中。当我使用函数 length 时，例如 mylist.length。我收到“java.lang.StackOverflowError”错误
java - 递归地添加节点项。链表
所以我正在学习处理链表。我将如何递归地添加节点内的项目。我可以通过执行 sum = h.item +h.next.item+h.next.next.item 添加它们，但这只有在我有小的链接列表时才有
C 链表/-> 运算符
所以我一直在努力理解链表的概念(一直在看一些示例代码，我在互联网上找到了这个。现在如果我能请别人确认我是否正确掌握了一些概念。我将绘制图表，说明我认为每个代码链接的作用。 #include #inc

知者

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城