【Java】Java 链表类详记

古城微笑少年丶 2023-10-12 21:46 16阅读 0赞

> **本文仅供学习参考！**
> 
> 相关文章链接：
> 
> https://www.runoob.com/java/java-linkedlist.html
> 
> https://www.developer.com/java/java-linkedlist-class/
> 
> https://www.w3schools.com/java/java\_linkedlist.asp

#### Java 中链表的类型 ####

从最基本的角度来说，链表的节点包含数据字段以及指向列表中下一个节点的“下一个”引用（链接）：

![image-20230626173334925][]

还有其他类型的链表，例如*循环链表*，它是一种单链表，其中最后一个节点和下一个字段指向序列中的第一个节点。它就像一个重复的 MP3 曲目列表：

![image-20230626173518079][]

Java LinkedList 类使用*双向链表*来存储元素。双向链表的节点还包含一个“prev”链接字段，该字段指向序列中的前一个节点。这允许向前和向后遍历：

![image-20230626173524127][]

#### 有关 LinkedList 类的更多信息 ####

**LinkedList**类与**ArrayList**共享许多功能。例如，两者都是**Collection**框架的一部分，并且驻留在**java.util**包中。然而，作为**LinkedList**数据结构的实现，元素并不存储在连续的位置，并且每个元素都是包含数据和地址组件的单独对象。**LinkedList**的另一个区别因素是它的元素称为节点。

如果程序员需要对元素/节点进行大量插入和删除，则 **LinkedList**比数组或**ArrayList**更好。缺点是无法直接访问节点；相反，Java 需要从头部开始，沿着链接到达我们希望访问的节点。这使得访问特定节点成为一个耗时的过程。

以下是需要记住的有关 Java **LinkedList**的一些更重要的功能：

*  **LinkedList类**可以包含重复的元素。
 *  **LinkedList**类维护插入顺序。
 *  **LinkedList**类是非同步的。
 *  如上所述，由于不需要进行换档，因此操作速度很快。
 *  **LinkedList**类可以用作列表、堆栈或队列，因为
    
    **LinkedList**类实现了**List**和**Deque**接口。完整的类声明显示了为什么这是可能的：
    
        public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Serializable

#### 如何在 Java 中创建链表 ####

在 Java 中创建链表有两种主要方法。第一种是使用无参构造函数：

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

这将创建一个空的**LinkedList**，然后开发人员可以将节点添加到其中：

import java.util.LinkedList;
    
    public class Main
    {
        
      public static void main(String[] args) {
        
      
        LinkedList<String> linkedNodes = new LinkedList<String>();
        
        for (int i=1; i<=5; i++) {
        
          linkedNodes.add("node"+i);
        }
        // 在指定索引处添加新项
        linkedNodes.add(1, "another node1");
        System.out.println(linkedNodes);
      }
    }

另一种选择是使用接受 Collection 的构造函数：

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

下面是一个示例 Java 程序，它创建一个字符串数组，然后将其转换为**List**。由于**Lists**实现了**Collections**接口，我们可以将其传递给**LinkedList**构造函数：

import java.util.Arrays;
    import java.util.Collections;
    import java.util.LinkedList;
    import java.util.List;
    
    public class Main {
        
    
      // 主驱动器方法
      public static void main(String[] args)
      {
        
        // 创建字符串数组
        String[] nodes = {
         "node1", "node2", "node3", "node4", "node5" };
        
        // 将数组转换为列表
        List<String> nodesList = Arrays.asList(nodes);
        
        // 创建LinkedList并在LinkedList构造函数中传递List
        LinkedList<String> linkedList = new LinkedList<>(nodesList);
        
        // 在LinkedList构造函数中传递List
        System.out.println(linkedList); //[node1, node2, node3, node4, node5]
      }
    }

#### 在 Java 中使用 LinkedList 的项目 ####

**LinkedList**提供了几种允许程序员对**LinkedList**进行操作的方法，例如：

*  添加元素 – **add(item)和add(index, item)**
 *  访问元素 – **get(index)**
 *  更改元素 – **set(index, item)**
 *  删除元素 – **remove(index)**

下面是一些 Java 示例，演示了上述所有**LinkedList**方法的使用：

import java.util.LinkedList;
    
    public class Main
    {
        
      public static void main(String[] args) {
        
        LinkedList<String> guitars = new LinkedList<>();
        
        guitars.add("Fender");
        guitars.add("Gibson");
        guitars.add("Jackson");
        System.out.println(guitars);
        
        // 在第二个位置插入新项目
        guitars.add(1, "Washburn");
        System.out.println(guitars);
        
        // 将Jackson改为Charvel
        guitars.set(3, "Charvel");
        System.out.println(guitars);
        
        // 删除第一个元素
        guitars.remove(0);
        System.out.println(guitars);
      }
    }

程序输出如下所示：

![Java 链表][Java]

#### 将 LinkedList 视为 Deque 和/或 Queue ####

由于**LinkedList**类还实现了**Queue**和**Deque**接口，因此我们可以调用两者的方法。以下是一些常用的方法：

*  **addFirst()** – 将指定元素添加到链表的开头
 *  **addLast()** – 将指定元素添加到链表末尾
 *  **getFirst()** – 返回第一个元素
 *  **getLast()** – 返回最后一个元素
 *  **removeFirst()** – 删除第一个元素
 *  **removeLast()** – 删除最后一个元素
 *  **peek()** – 返回链表的第一个元素（头）
 *  **poll()** – 返回并删除链表中的第一个元素
 *  **Offer()** – 在链表末尾添加指定元素

如果您只对特定于一个接口（即**List**、**Queue**或**Deque ）的方法感兴趣，那么您始终可以将LinkedList**实例化为该接口！例如：

// 使用List创建链表
    List<String> list = new LinkedList<>();
    
    // 使用Queue创建链表
    Queue<String> 队列 = new LinkedList<>();
    
    // 使用 Deque 创建链表
    Deque<String> deque = new LinkedList<>();

请记住，将**LinkedList**实例化为特定接口会限制对该接口提供的方法的访问。因此，在上面的示例中，**Queue**不能使用**Deque**或**List**接口中的方法。

在下面的程序中，**LinkList**充当**Queue**，那么为什么不将其实例化为一个Queue 呢？

import java.util.Arrays;
    import java.util.Collections;
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class Main
    {
        
      public static void main(String[] args) {
        
    
        Queue<String> queue = new LinkedList<>();
    
        for (int i=1; i<=5; i++) {
        
          queue.add("node"+i);
        }
        
        System.out.println(queue);
    
        // 访问第一个元素
        String str1 = queue.peek();
        System.out.println("Accessed Element: " + str1);
    
        // 访问并移除第一个元素
        String str2 = queue.poll();
        System.out.println("Removed Element: " + str2);
        System.out.println("LinkedList after poll(): " + queue);
    
        // 在末尾添加元素
        queue.offer("node6");
        System.out.println("LinkedList after offer(): " + queue);
      }
    }

正如您在下面的程序输出中看到的，只要我们将自己限制为**Queue**类的方法，一切都会正常工作：

![Java 链表教程][Java 1]

#### End ####

Java的**LinkedList**类是一个双向链表，允许向前和向后遍历。当您需要执行大量元素插入和删除操作或者需要访问**Queue**和**Deque**接口的方法时，它通常比数组或**ArrayList**更可取。

[image-20230626173334925]: https://img-blog.csdnimg.cn/img_convert/f3339c5496f4b0d6a6260e03b176530c.png
[image-20230626173518079]: https://img-blog.csdnimg.cn/img_convert/bf0ffdd2b07dcb2543d4c127c7c37dd1.png
[image-20230626173524127]: https://img-blog.csdnimg.cn/img_convert/3bf77bc4a6a6582e46291d6688da8d95.png
[Java]: https://img-blog.csdnimg.cn/img_convert/0b5b2fa6bbfa38dece152cb0f577678f.jpeg
[Java 1]: https://img-blog.csdnimg.cn/img_convert/c03f02ea5f01f24ae8d32bdf33920304.jpeg