Detaillierte Erklärung der verknüpften Liste in PHP

Der Betrieb einer verknüpften Liste ist viel komplizierter als der einer sequentiellen Liste. Da PHP tatsächlich viele Array-Operationsprobleme für uns gelöst hat, können wir Arrays sehr bequem bedienen und müssen nicht viele logische Operationen für Arrays definieren. Beispielsweise haben Arrays in C eine Längenbeschränkung, aber in PHP werden wir dieses Problem nicht berücksichtigen.

Die Definition der verketteten Struktur

Zuerst haben wir im ersten Artikel über die Definition verknüpfter Listen gesprochen, um weitere Details zu erhalten das Konzept verknüpfter Listen verstehen.

Wir stellen den Knoten Knoten im Bild als Klasse dar:

/**
 * 链表结构
 */
class LinkedList
{
    public $data;
    public $next;
}

Eine verknüpfte Listenklasse kann als Knoten in der verknüpften Liste betrachtet werden. Sie enthält zwei Inhalte, Daten stellen Daten dar und next stellt den nächsten Knoten dar . Zeiger. Genau wie bei einer Kette, ein Glied in einem anderen, ist dies die legendäre Struktur verknüpfter Listen.

Erzeugen einer verknüpften Liste und Initialisieren von Vorgängen

/**
 * 生成链表
 */
function createLinkedList()
{
    $list = new LinkedList();
    $list->data = null;
    $list->next = null;
    return $list;
}

/**
 * 初始化链表
 * @param array $data 链表中要保存的数据，这里以数组为参考
 * @return LinkedList 链表数据
 */
function Init(array $data)
{
    // 初始化
    $list = createLinkedList();
    $r = $list;
    foreach ($data as $key => $value) {
        $link = new LinkedList();
        $link->data = $value;
        $link->next = null;
        $r->next = $link;
        $r = $link;
    }
    return $list;
}

$link = Init(range(1, 10));

print_r($link);
// LinkedList Object
// (
//     [data] =>
//     [next] => LinkedList Object
//         (
//             [data] => 1
//             [next] => LinkedList Object
//                 (
//                     [data] => 2
//                     [next] => LinkedList Object
//                         (
//                             [data] => 3
//                             [next] => LinkedList Object
//                                 (
//                                     [data] => 4
//                                     [next] => LinkedList Object
//                                         (
//                                             [data] => 5
//                                             [next] => LinkedList Object
//                                                 (
//                                                     [data] => 6
//                                                     [next] => LinkedList Object
//                                                         (
//                                                             [data] => 7
//                                                             [next] => LinkedList Object
//                                                                 (
//                                                                     [data] => 8
//                                                                     [next] => LinkedList Object
//                                                                         (
//                                                                             [data] => 9
//                                                                             [next] => LinkedList Object
//                                                                                 (
//                                                                                     [data] => 10
//                                                                                     [next] =>
//                                                                                 )

//                                                                         )

//                                                                 )

//                                                         )

//                                                 )

//                                         )

//                                 )

//                         )

//                 )

//         )

// )

Bei der Verwendung einer verknüpften Liste sorgen wir normalerweise dafür, dass der erste Knoten keine Daten enthält, sondern nur als leerer Knoten dient, um auf den ersten Knoten mit Daten zu verweisen. Wir können diese Art von Knoten als Kopfknoten bezeichnen. Wenn Sie beurteilen müssen, ob die verknüpfte Liste leer ist, müssen Sie nur beurteilen, ob der nächste Knoten des ersten Knotens leer ist. Im obigen Code generiert die Funktion createLinkedList() tatsächlich einen solchen Kopfknoten.

Dann erstellen wir diese verknüpfte Liste mithilfe der Initialisierungsfunktion Init(). Der Konstruktionsprozess ist relativ einfach. Hier übergeben wir ein Array und erstellen die verknüpfte Liste gemäß der Array-Struktur. In praktischen Anwendungen können wir natürlich beliebige Daten verwenden, um die verknüpfte Liste zu erstellen. Der Konstruktionsprozess ist nicht kompliziert. Weisen Sie einfach den aktuellen Knoten der Variablen r zu, erstellen Sie dann einen neuen Knoten und machen Sie r->next gleich dem neu erstellten Knoten. Die direkt aus der erstellten verknüpften Liste gedruckte Struktur ist das Formular im Kommentar.

Durchlaufen einer verknüpften Liste

function IteratorLinkedList(LinkedList $link)
{
    while (($link = $link->next) != null) {
        echo $link->data, ',';
    }
    echo PHP_EOL;
}

Ist das Durchlaufen einer verknüpften Liste der Cursoroperation einiger Datenbanken oder der Operation des Iteratormodus sehr ähnlich? Das ist richtig, tatsächlich ist die Struktur von Cursorn und Iteratoren eine Form einer verknüpften Liste. Wir suchen so lange nach $next, bis es keinen nächsten Knoten mehr gibt, und schließen so eine Durchquerung einer verknüpften Liste ab. Es ist ersichtlich, dass die zeitliche Komplexität dieses Prozesses O(n) beträgt.

Einfügen und Löschen

/**
 * 链表指定位置插入元素
 * @param LinkedList $list 链表数据
 * @param int $i 位置
 * @param mixed $data 数据
 */
function Insert(LinkedList &$list, int $i, $data)
{
    $j = 0;
    $item = $list;
    // 遍历链表，找指定位置的前一个位置
    while ($j < $i - 1) {
        $item = $item->next;
        $j++;
    }

    // 如果 item 不存在或者 $i > n+1 或者 $i < 0
    if ($item == null || $j > $i - 1) {
        return false;
    }

    // 创建一个新节点
    $s = new LinkedList();
    $s->data = $data;

    // 新创建节点的下一个节点指向原 i-1 节点的下一跳节点，也就是当前的 i 节点
    $s->next = $item->next;
    // 将 i-1 节点的下一跳节点指向 s ，完成将 s 插入指定的 i 位置，并让原来的 i 位置元素变成 i+1 位置
    $item->next = $s;

    return true;
}

/**
 * 删除链表指定位置元素
 * @param LinkedList $list 链表数据
 * @param int $i 位置
 */
function Delete(LinkedList &$list, int $i)
{
    $j = 0;
    $item = $list;
    // 遍历链表，找指定位置的前一个位置
    while ($j < $i - 1) {
        $item = $item->next;
        $j++;
    }
    // 如果 item 不存在或者 $i > n+1 或者 $i < 0
    if ($item == null || $j > $i - 1) {
        return false;
    }

    // 使用一个临时节点保存当前节点信息，$item 是第 i-1 个节点，所以 $item->next 就是我们要找到的当前这个 i 节点
    $temp = $item->next;
    // 让当前节点，也就是目标节点的上一个节点， i-1 的这个节点的下一跳（原来的 i 位置的节点）变成原来 i 位置节点的下一跳 next 节点，让i位置的节点脱离链条
    $item->next = $temp->next;

    return true;
}

// 插入
Insert($link, 5, 55);
// 遍历链表
IteratorLinkedList($link); // 1,2,3,4,55,5,6,7,8,9,10,

// 删除
Delete($link, 7);
// 遍历链表
IteratorLinkedList($link); // 1,2,3,4,55,5,7,8,9,10,

Das Einfügen und Löschen verknüpfter Listen ist eigentlich sehr ähnlich. Beide müssen das vorherige Element an der Einfüge- oder Löschposition finden, also das Element an der i-ten Position. Anschließend wird das Einfügen und Löschen verknüpfter Listenelemente durch Betätigen des nächsten Zeigers dieses Elements implementiert.

Die Codes in den beiden Funktionen Traversierung und Positionsbeurteilung sind tatsächlich gleich. Der Unterschied besteht darin, dass Sie beim Erstellen einen neuen Knoten erstellen und dann den nächsten Knoten auf den nächsten Knoten des vorherigen verweisen lassen müssen. 1 Positionselement. Richten Sie dann das nächste Element an Position i-1 auf den neu erstellten Knoten aus. Der Löschvorgang besteht darin, den zu löschenden Knoten an Position i in einer temporären Variablen zu speichern und dann das nächste Element an Position i-1 auf das nächste Element an der gelöschten Position i zu verweisen.

Die obige Erklärung muss Schritt für Schritt in Verbindung mit dem Code betrachtet werden. Natürlich können wir sie auch in Verbindung mit dem Bild unten lernen. Einfüge- und Löschvorgänge sind der Kern von verknüpften Listenoperationen und der komplexeste Teil, der viel Verständnis und Beherrschung erfordert.

Suche basierend auf Position, Suche basierend auf Daten

/**
 * 根据位置查找元素位置
 * @param LinkedList $list 链表数据
 * @param int $i 位置
 */
function GetElem(LinkedList &$list, int $i)
{
    $item = $list;
    $j = 1; // 从第一个开始查找，0是头结点 
    while ($item && $j <= $i) {
        $item = $item->next;
        $j++;
    }

    if (!$item || $j > $i + 1) {
        return false;
    }
    return $item->data;

}

/**
 * 根据数据查找数据元素所在位置
 * @param LinkedList $list 链表数据
 * @param mixed $data 数据
 */
function LocateElem(LinkedList &$list, $data)
{
    $item = $list;
    $j = 1; // 从第一个开始查找，0是头结点 
    while (($item = $item->next)!=null) {
        if($item->data == $data){
            return $j;
        }
        $j++;
    }

    return false;
}

// 获取指定位置的元素内容
var_dump(GetElem($link, 5)); // int(55)

// 获取指定元素所在的位置
var_dump(LocateElem($link, 55)); // int(5)

Es gibt zwei Formen der Suche in verknüpften Listen. Wenn ich beispielsweise den Inhalt eines Elements an der fünften Position angeben möchte, dann Das Element wird basierend auf dem angegebenen Positionswert durchsucht, genau wie ein Array-Index. Es ist jedoch zu beachten, dass der Index der verknüpften Liste bei 1 beginnt, da die Position 0 unser Hauptknoten ist. Natürlich können wir den Code auch so ändern, dass der U-Turn-Knoten ignoriert und mit dem Array konsistent gemacht wird. In diesem Fall sind die Merkmale der verknüpften Liste jedoch nicht offensichtlich, sodass wir im Testcode immer noch mit 1 beginnen Hier.

Eine andere Art der Suche besteht darin, einen Dateninhalt anzugeben und seine Position in der verknüpften Liste zu finden. Tatsächlich durchlaufen beide Algorithmen die gesamte verknüpfte Liste, und es gibt im Wesentlichen keinen Unterschied. Da eine verknüpfte Liste nicht wie ein Array tiefgestellt werden kann, beträgt die zeitliche Komplexität ihrer Suchvorgänge O(n).

Zusammenfassung

Wie wäre es damit, der Schwierigkeitsgrad wird immer höher. Die Bedienung der verknüpften Liste wird viel komplizierter sein. Keine Sorge, das ist nur ein kleiner Vorgeschmack. Der Inhalt, den Sie später lernen werden, dreht sich im Wesentlichen um die beiden Formen sequentieller Listen (Arrays) und verknüpfter Listen. Und unser Studium der verknüpften Listen ist noch nicht abgeschlossen. Im nächsten Artikel werden wir einen tieferen Blick auf andere Formen verknüpfter Listen werfen: doppelt verknüpfte Listen, zirkulär verknüpfte Listen und doppelt zirkulär verknüpfte Listen.

Testcode:

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/2.线性表/source/2.3%20链表的相关逻辑操作.php

Empfohlenes Lernen: php-Video-Tutorial

Das obige ist der detaillierte Inhalt vonDetaillierte Erklärung der verknüpften Liste in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!