链接列表如何工作？链表初学者指南

谁践踏了优雅 2024-03-22 19:10 14阅读 0赞

链表是一种线性数据结构，用于存储元素的集合。与数组不同，链表使用节点来存储未存储在连续内存位置的元素。

在本文中，您将了解链表是什么、它们如何工作以及如何构建链表。

虽然所讨论的概念并不特定于任何特定的编程语言，但本文将使用 Java 来演示如何以编程方式创建链表。

什么是链表？  
链表是节点的集合，其中每个节点包含数据以及列表中下一个节点的内存地址。  
![在这里插入图片描述][a0cad6993be34250bb2b88aad0bdf5e4.png]  
具有三个节点的链表的图示  
在这里，您可以看到节点的地址不一定是立即连续的。第一个节点的地址为200，第二个节点的地址为801，而不是您可能期望的201 。

那么节点是如何线性存储的呢？

即使节点不在连续内存中，节点也会通过链接线性存储。每个节点都有其后续节点的地址。这就是每个节点可以访问其后续节点的方式。

链表中的节点  
节点是链表的构建块。毕竟，链表是节点的集合。  
![示例节点][096c1eb0a1b54ac3b345a85fa83e6f2f.png]  
链表中的节点由两部分组成：

data表示节点的值。  
next这是对后续节点的引用。  
链表中的头部和尾部  
如前所述，链表是节点的集合。  
![在这里插入图片描述][393e696b8c96478a878695f612f1145c.png]  
显示头部和尾部的链表的插图  
链表的第一个节点称为节点head。它是链表的起点。

最后一个节点称为tail节点。由于最后一个节点之后没有节点，所以最后一个节点始终指向null.

指针null不指向任何内存位置。

如何以编程方式创建链表  
此时，您应该对链表的工作原理及其结构有基本的了解。让我们通过以下步骤创建一个链表：

创建节点。  
连接节点。  
追加节点。  
插入节点。  
删除节点。  
如何在链表中创建节点  
如您所知，一个节点由两部分组成：数据和下一个节点的地址。

![在这里插入图片描述][3f89ffd6ca5a4fcc8f895d93c28f91c9.png]  
单节点示意图  
以下是创建一个名为的类的方法Node：

class Node {
       
        
        int data;
        Node next;
     
        Node(int data) {
       
        
            this.data = data;
            this.next = null;
        }
    }

该类Node表示链表中的一个节点，具有两个实例变量：data（保存存储在节点中的数据）和 next（保存对列表中下一个节点的引用）。

构造函数采用int参数数据来初始化数据变量，并默认将下一个变量设置为 null。

现在，您可以通过创建类的新实例来简单地创建节点并向它们添加数据Node：

// create nodes
    Node node1 = new Node(11);
    Node node2 = new Node(18);
    Node node3 = new Node(24);

在上面的代码中，我们创建了三个节点：  
![在这里插入图片描述][557df1e489064dc285835ca8f8e9e011.png]  
显示我们用上面的代码创建的三个节点  
如何链接链表中的节点  
创建节点后，您必须将它们连接起来形成链表。

为此，您首先需要创建一个带有head节点的链表。

class LinkedList {
       
        
    
        Node head;
    
            LinkedList() {
       
        
            this.head = null;
        }
    
    }

最初head节点被设置为null因为链表中还没有节点。

现在要在链表中将节点连接在一起，您可以首先将head节点设置为列表中的第一个节点，在本例中为node1。

head = node1;

然后使 next of node1point tonode2和 next of node2point to node3。那是：

node1.next = node2;
    node2.next = node3;

![在这里插入图片描述][db9248f35fa448f5907f286c837f5ffe.png]  
显示节点链接的插图  
您已成功创建链表并连接节点。

如何将节点附加到链表  
追加节点意味着将节点添加到链表的末尾。添加节点时需要考虑两种情况：

追加到空链表。  
附加到非空链表。  
如何将节点附加到空链表  
如果链表中没有节点，则它是一个空链表。要将节点附加到空链表，必须首先确保链表为空。您可以通过检查head节点是否为来执行此操作null。

如果head节点是null那么你可以简单地设置head为新节点：

if (head == null) {
       
        
        head = newNode;
    }

![在这里插入图片描述][e7e5554fb9ea47e7b500379dd30900c0.png]  
头节点为空  
如何将节点附加到非空链表  
如果链表中有一个或多个节点，则它是一个非空链表。  
![在这里插入图片描述][ed56cb271db44f1ba35f03a0baa5b24c.png]  
非空链表示意图  
要将节点附加到非空链表，请将最后一个节点链接到新节点。

与数组不同，我们不能直接访问链表中的任何元素。我们必须从一个head节点遍历到另一个last节点。

为此，创建一个current指向头节点的临时指针（您可以称为指针）。

![在这里插入图片描述][e1d15f9f6955400283eb75b9b0893549.png]  
插图显示指向头节点的临时指针（当前）  
接下来指向current它的next节点，直到next当前节点的 指向null。

[a0cad6993be34250bb2b88aad0bdf5e4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/1cf351b3c7b54b99beac3bbc57c085e0.png
[096c1eb0a1b54ac3b345a85fa83e6f2f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/30bca1080eeb4901baa20c0616b86b0a.png
[393e696b8c96478a878695f612f1145c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/abda351c532b44b587c5c3cf686afe05.png
[3f89ffd6ca5a4fcc8f895d93c28f91c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/18c44964f4f943068b702c2dcfd19b5a.png
[557df1e489064dc285835ca8f8e9e011.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/f75c75d3017c4447a35e675b4069973b.png
[db9248f35fa448f5907f286c837f5ffe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/6e9c9e4808184ca294deafd2cfc244b6.png
[e7e5554fb9ea47e7b500379dd30900c0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/e24f75797d6949f08c17a6248d8c1a4b.png
[ed56cb271db44f1ba35f03a0baa5b24c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/827b7381e1e444188855dec5eb74046d.png
[e1d15f9f6955400283eb75b9b0893549.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/11a8cf2714164c598a8a971089c555de.png