插入、删除和搜索项目

到目前为止，我们只看到了插入节点和显示所有节点内容的操作。现在，我们将探讨链表中的其他操作。我们将主要关注以下操作：

  • 在第一个节点插入

  • 搜索节点

  • 在特定节点之前插入

  • 在特定节点后插入

  • 删除第一个节点

  • 删除最后一个节点

  • 搜索并删除一个节点

  • 反转链接表

  • 获取第 N 位元素

插入到第一个节点

当我们在前面或头部添加一个节点时，我们必须考虑两种简单的可能性。列表可能是空的，因此新节点就是头部。这种可能性非常简单。但是，如果列表中已经有了头部，我们就必须采取以下措施：

  1. 创建新节点。

  2. 将新节点设为第一个节点或头。

  3. 将前一个头节点或第一个节点指定为新创建的第一个节点的下一个节点。

这是代码：

Unresolved include directive in modules/ROOT/pages/ch03/ch3-03.adoc - include::example$Chapter03/1.php[]

搜索节点

搜索节点非常简单。我们需要遍历每个节点，检查目标数据是否与节点数据匹配。如果找到数据，则返回节点；否则，返回 FALSE。实现过程如下：

Unresolved include directive in modules/ROOT/pages/ch03/ch3-03.adoc - include::example$Chapter03/1.php[]

在特定节点之前插入

这个过程与我们看到的第一个操作类似。主要区别在于，我们需要找到特定的节点，然后在它之前插入一个新节点。找到目标节点后，我们可以更改下一个节点，使其指向新创建的节点，然后再更改新创建节点后面的节点，使其指向我们搜索的节点。如下图所示：

image 2023 11 07 13 35 39 912

下面是实现前面所示逻辑的代码：

Unresolved include directive in modules/ROOT/pages/ch03/ch3-03.adoc - include::example$Chapter03/1.php[]

如果我们检查前面的代码，就会发现其中的逻辑非常简单。该方法有两个参数：一个是数据，一个是查询。我们遍历每个节点。同时，我们还要跟踪当前节点和上一个节点。跟踪上一个节点非常重要，因为在找到目标节点时，我们会将上一个节点的下一个节点设置为新创建的节点。

在特定节点之后插入

这个过程类似于在目标节点之前插入节点。不同的是，我们需要在目标节点之后插入新节点。在这里，我们需要考虑目标节点以及它所指向的下一个节点。找到目标节点后，我们可以更改下一个节点，使其指向新创建的节点，然后再更改新创建节点之后的节点，使其指向目标节点之后的下一个节点。以下是用于实现这一功能的代码：

Unresolved include directive in modules/ROOT/pages/ch03/ch3-03.adoc - include::example$Chapter03/1.php[]

删除第一个节点

删除节点简单地说就是删除该节点，并重新排列前一个节点和后一个节点的链接。如果我们只是删除了一个节点，并将前一个节点的下一个链接与被删除节点之后的节点连接起来，那么删除操作就完成了。请看下面的示例：

image 2023 11 07 13 39 44 783

删除第一个节点后，我们只需将第二个节点设为头部或第一个节点。我们可以通过以下代码轻松实现这一目的：

Unresolved include directive in modules/ROOT/pages/ch03/ch3-03.adoc - include::example$Chapter03/1.php[]

现在，我们必须考虑一种特殊情况，即将总节点数减一。

删除最后一个节点

删除最后一个节点时，我们需要将从最后一个节点开始的第二个节点的下一个链接赋值为 NULL。我们将遍历直到最后一个节点，并在遍历过程中跟踪上一个节点。一旦我们到达最后一个节点，下一个节点的上一个节点属性将被设置为 NULL，如下例所示：

Unresolved include directive in modules/ROOT/pages/ch03/ch3-03.adoc - include::example$Chapter03/1.php[]

首先，我们检查列表是否为空。然后，我们检查列表是否有多个节点。根据答案，我们遍历最后一个节点，并跟踪前一个节点。然后，我们将前一个节点的下一个链接赋值为 NULL，以便从列表中省略最后一个节点。

搜索和删除节点

我们可以使用搜索和删除操作从列表中删除任何节点。首先，我们从列表中搜索节点，然后通过删除节点的引用来删除该节点。以下是实现这一目的的代码：

Unresolved include directive in modules/ROOT/pages/ch03/ch3-03.adoc - include::example$Chapter03/1.php[]

反转列表

反转链表的方法有很多。我们将使用一种简单的方法来逆转列表，即所谓的就地逆转。我们遍历节点，将下一个节点改为上一个节点，上一个节点改为当前节点，当前节点改为下一个节点。该逻辑的伪算法如下所示：

prev = NULL;
current = first_node;
next = NULL;
while (current != NULL)
{
    next = current->next;
    current->next = prev;
    prev = current;
    current = next;
}
first_node = prev;

如果我们基于此伪代码实现反向函数，它将如下所示：

Unresolved include directive in modules/ROOT/pages/ch03/ch3-03.adoc - include::example$Chapter03/1.php[]

获取第 N 个位置元素

由于列表不同于数组，直接从其位置获取元素并不容易。为了获取第 N 个位置上的元素，我们必须遍历该位置并获取该元素。以下是该方法的代码示例：

Unresolved include directive in modules/ROOT/pages/ch03/ch3-03.adoc - include::example$Chapter03/1.php[]

现在，我们已经编写了 LinkedList 类所需的所有操作。现在，让我们用不同的操作运行程序。如果我们运行下面的程序，就会基本涵盖我们编写的所有操作：

Unresolved include directive in modules/ROOT/pages/ch03/ch3-03.adoc - include::example$Chapter03/1.php[]
$BookTitles->display();
$BookTitles->deleteFirst();
$BookTitles->deleteLast();
$BookTitles->delete("Introduction to PHP and Data structures");
$BookTitles->reverse();
$BookTitles->display();
echo "2nd Item is: ".$BookTitles->getNthNode(2)->data;

前面代码的输出将如下所示：

Total book titles: 6
Mediawiki Administrative tutorial guide
Introduction to Algorithm
Introduction to PHP and Data structures
Introduction to Calculus
Programming Intelligence
Introduction to Calculus
Total book titles: 3
Programming Intelligence
Introduction to Calculus
Introduction to Algorithm
2nd Item is: Introduction to Calculus

现在我们已经用 PHP 7 完成了一个链表的实现。到目前为止，我们已经明白了一件事，那就是与数组的实现不同，我们必须通过编写代码来手动完成许多操作。我们还必须记住一点：这并不是实现链表的唯一方法。很多人喜欢跟踪列表的第一个和最后一个节点，以便更好地进行插入操作。现在，我们来看看在平均情况和最坏情况下链表操作的复杂性。