PHP中单链接列表和基本操作简介-DEV365 开发者社区

关于一个节点

在单链接列表中，节点是一个基本单元，可存储一个数据，并引用列表中的下一个节点。

这是php中的节点类的示例：

class Node
{
  public $value;
  public $next;

  public function __construct($value)
  {
    $this->value = $value;
    $this->next = null;
  }
}

此节点类有两个字段：
1，存储元素的数据，
2，下一步，是对列表中的下一个节点的引用。

下一个字段初始化为null，以指示节点是列表中的最后一个节点。

这是如何创建节点并将其链接到另一个节点的示例：

$nodeFirst = new Node(10);
$nodeNext = new Node(20);

// connect $nodeNext to nodeFirst
$nodeFirst->next = $nodeNext; // 10->20->null

// now you can receive value from second node
$nodeFirst->next->value; // 20

此代码使用数据值10和20创建两个节点，并通过将nodeFirst的下一个字段设置为nodeNext将它们链接在一起。由此产生的单链接列表看起来像这样：

$nodeFirst->$nodeNext->null

单链接列表

构造函数

让我们创建一个代表链接列表数据结构的类。

此LinkedList类有三个实例变量：

$head：对列表中的第一个节点的引用，
$tail：对列表中的最后一个节点的引用，
$length：一个数量计算列表中节点数的整数。

注意： 如果列表中只有一个节点，则 head 和 tail 指向同一节点。

class LinkedList
{
    public $head;
    public $tail;
    public $length;

    public function __construct(public $value)
    {
        $newNode = new Node($value);
        $this->head = $newNode;
        $this->tail = $newNode;
        $this->length = 1;
    }
}

__construct将整数值作为参数，并创建一个具有该值的新节点。然后将此新节点设置为列表的头部和尾部，并且长度设置为1。

注意： 我们不必使构造函数中的一个新节点归化，但是对于此解释很方便。
注释2： 在本文中，我将整数用作数据类型作为节点值。

打印所有节点

在转到基本操作之前，让我们创建一个辅助方法来打印单链接列表中的所有节点。

解释：

在方法printAll()中，我们定义了局部变量$temp，并分配了 $ this-> head的值，这是对列表中的第一个节点的引用。

然后，它进入一个段循环，直到$temp不为空，这意味着没有更多的 next 节点。

呼应值后，该函数分配了$temp $temp->next，的值，将$temp移至列表中的下一个节点 ，以继续循环。

public function printAll()
{
    $temp = $this->head;
    while ($temp != null) {
        echo $temp->value . '->';
        $temp = $temp->next;
    }
}

基本操作：

1.附加

附加节点意味着在链接列表的末尾添加新节点。

左侧是一个链接列表（图中仅显示一个节点），右侧是我们要附加的节点。结果链接列表看起来像图像底部所示的列表。

解释：

我们创建一个具有值的新节点。
如果链接列表为空，我们将头和尾部分配给新节点，因为它是列表中唯一的节点。
否则，我们将链接列表中的最后一个节点链接到使用$this->tail->next = $newNode的新列表，然后用$this->tail = $newNode将尾巴更改为新的尾部。
我们将链接列表的计数（长度）增加。

// add to the linked list Class
public function append($value)
{
    $newNode = new Node($value);
    if ($this->length == 0) {
        $this->head = $newNode;
        $this->tail = $newNode;
    } else {
        $this->tail->next = $newNode;
        $this->tail = $newNode;
    }
    $this->length++;
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);

$l->printAll();
// 4->3->5->

2.获取

获得节点意味着在链接列表中的某个索引中检索节点，从0开始。该方法返回节点对象，而不仅仅是节点的值。

。

解释：

首先，我们确保索引在链接列表的范围内；它应该大于零，小于单链接列表的计数。
我们将链接列表的头部分配给变量$temp，以便我们可以在穿越列表时跟踪我们的位置。
然后我们循环浏览列表，直到达到所需的索引。
该方法在指定索引处返回节点。

public function getNode($index)
{
    if ($index < 0 || $index >= $this->length) {
        return null;
    }
    $temp = $this->head;
    for ($i = 0; $i < $index; $i++) {
        $temp = $temp->next;
    }
    return $temp;
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);

$node = $l->getNode(2);
echo $node->value;
// 5

3.设置

设置节点是用新值替换某些索引的现有节点的值。

解释：

我们使用现有的getNode（）方法在指定索引处找到节点，或者如果索引不超出界限，则返回null。
我们为检索的节点分配了一个新值。

public function setNode($index, $value)
{
    $temp = $this->getNode($index);
    if ($temp) {
        $temp->value = $value;
    }
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);
$l->setNode(2,11); // set a value of 11 at index 2 if node exists

$l->printAll();
// 4->3->11->

4.预登

预处节点意味着在链接列表的开头添加新节点。

右侧是一个链接列表，左侧是我们要预处的节点。结果链接列表看起来像图像底部所示的列表。

我们需要做两件事：

1，将新节点连接到现有链接列表的头部。
2，将头更改为新创建的节点。

解释：

1，我们创建一个具有值的新节点。
2，如果链接列表中没有节点，我们将头和尾部分配给新节点。
3，否则，我们将新节点与$newNode->next = $this->head链接到头部，然后用$this->head = $newNode将头更改为新节点。
4，最后，我们增加链接列表的计数（长度）。

public function prepend($value)
{
    $newNode = new Node($value);
    if ($this->length == 0) {
        $this->head = $newNode;
        $this->tail = $newNode;
    } else {
        $newNode->next = $this->head;
        $this->head = $newNode;
    }
    $this->length++;
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);
$l->prepend(48);

$l->printAll();
// 48->4->3->5->

5.插入

要在链接列表中插入一个节点，意味着在特定位置将新节点添加到列表中，将任何后续节点转移到权利中，以腾出新节点。例如，如果我们有一个带有三个节点（3、4、7）的链接列表，并且我们想在节点4和7之间插入一个新节点（x），则结果链接列表看起来像（3、4，x ，7）。

解释：

我们检查索引是否在链接列表的范围内。
如果索引为0，我们不需要穿越列表，并且可以使用现有的prepend($value)方法将新节点插入列表的开头。如果索引是列表中的最后一个位置（索引等于列表的长度），我们可以使用append($value)方法将新节点插入列表末尾。
否则，我们创建一个具有给定值的新节点。
我们需要在要插入新节点的位置之前立即在索引处找到节点。我们将此节点分配给临时变量。
我们将新节点链接到链接列表中的下一个节点。
然后，我们将先前的节点（存储在临时变量中的节点）指向新节点。
最后，我们将链接列表的计数（长度）增加。

注意： 步骤5和6必须按顺序排列。我们无法将临时（以前的节点）链接到新节点，因为它会取消链接列表的其余部分。

public function insert($index, $value)
{
    if ($index < 0 || $index >= $this->length) {
        return null;
    }
    if ($index == 0) {
        $this->prepend($value);
        return;
    } elseif ($index == $this->length) {
        $this->append($value);
        return;
    }
    $newNode = new Node($value);
    $temp = $this->getNode($index - 1);
    $newNode->next = $temp->next;
    $temp->next = $newNode;
    $this->length++;
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);
$l->insert(1,22);

$l->printAll();
// 4->22->3->5->

6.首先弹出

首先要删除链接列表开头的节点。

解释：

我们检查链接列表是否没有空。
如果列表中只有一个节点，我们将头部和尾巴重置为null。
否则，我们创建一个名为$temp的临时变量并将其分配给头部。
然后，我们将头分配到下一个节点
和通过将temp->next更改为null的UNINK $temp。
我们减少了链接列表的计数（长度）。

public function popFirst()
{
    if ($this->length == 0) {
        return null;
    }
    if ($this->length == 1) {
        $this->head = null;
        $this->tail = null;
    } else {
        $temp = $this->head;
        $this->head = $temp->next;
        $temp->next = null;
    }
    $this->length--;
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);
$l->popFirst();

$l->printAll();
// 3->5->

7. pop last

pop last节点是删除链接列表中的最后一个节点。

解释：

我们检查链接列表是否没有空。
如果链接列表中只有一个节点，我们将头部和尾巴重置为null。
否则，我们需要将列表遍历到最后，并在最后一个节点之前找到一个节点。我们可以通过创建两个称为“ temp”和“ prev”的临时变量来做到这一点，其中“ temp”变量是领先的一步。
我们循环浏览整个链接列表，只是为了在最后一个列表之前找到节点。
然后，我们将尾巴分配给“上prev”。
我们取消了最后一个节点（新尾部的下一个节点）。
我们减少了链接列表的计数（长度）。

public function pop()
{
    if ($this->length == 0) {
        return null;
    }

    if ($this->length == 1) {
        $this->head = null;
        $this->tail = null;
    } else {
        $temp = $this->head;
        $prev = $this->head;
        while ($temp->next) {
            $prev = $temp;
            $temp = $temp->next;
        }
        $this->tail = $prev;
        $this->tail->next = null;
    }
    $this->length--;
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);
$l->pop();

$l->printAll();
// 4->3->

8.删除

从链接列表中删除节点意味着将其从某个索引中删除列表中，并更新周围节点的下一个指针以维护列表的完整性。

它与插入相反。

解释：

我们检查索引是否在链接列表的范围内。
如果索引为0，我们可以使用popFirst()方法来删除列表开头的节点。如果索引是列表中的最后一个位置（索引等于列表的长度），我们可以使用pop()方法删除列表末尾的节点。
否则，我们需要在要删除节点的位置之前立即在索引处找到节点。我们将此节点分配给临时变量。
我们更新上一个节点的下一个指针，以指向我们要删除的节点。这有效地从链接列表中删除了节点。
我们减少了链接列表的计数（长度）。

public function remove($index)
{
    if ($index < 0 || $index >= $this->length) {
        return null;
    }
    if ($index == 0) {
        $this->popFirst();
        return;
    } elseif ($index == $this->length - 1) {
        $this->pop();
        return;
    }
    $temp = $this->getNode($index - 1);
    $temp->next = $temp->next->next;
    $this->length--;
}
$l = new LinkedList(4);
$l->append(3);
$l->append(5);
$l->remove(1);

$l->printAll();
// 4->5->

您可以在这里看到整个脚本：
https://gist.github.com/matusstafura/6d7bf89bdde17e83fa39def977ffe7aa

时间复杂性

单个链接列表上基本操作的时间复杂性（或“大O”）取决于正在执行的操作和访问节点的位置。

某些常见操作的时间复杂性：

通过索引访问节点：o（n）
在列表的开头或结尾插入节点：o（1）
在特定索引上插入节点：o（n）
从列表的开头或结尾删除节点：o（1）
从特定索引中删除节点：o（n）

通常，单链接列表具有O（n）的时间复杂性，用于操作，这些操作需要遍历列表才能找到特定节点，因为这些操作需要访问列表中的每个节点，直到找到所需的节点为止。另一方面，不需要穿越列表的操作，例如在列表的开头或结尾插入或删除节点，具有O（1）的时间复杂性。

重要的是要注意，这些时间复杂性是最坏的情况，在某些情况下，操作所需的实际时间可能会更快。例如，如果我们有对要删除的节点的引用，则可以在O（1）时间中删除它，而无需穿越列表。同样，如果我们在特定索引上插入节点，并且已经对该索引的节点进行了引用，则插入操作也将花费O（1）时间。

目录