Gibt es andere Darstellungsformen verknüpfter Listen?

Im letzten Artikel haben wir bereits gesagt, dass es neben der einfachen einseitig verknüpften Liste noch mehrere andere Formen verknüpfter Listen gibt. Dies ist natürlich auch ein Hauptmerkmal der verknüpften Listenstruktur, die sehr flexibel und praktisch ist. Denken wir kurz darüber nach: Wenn der nächste Knoten des letzten Knotens auf den ersten Knoten zeigt, bildet dies einen Ring, bei dem es sich um eine kreisförmig verknüpfte Liste handelt.

Wenn wir jedem Knoten ein prev-Attribut hinzufügen, das auf den vorherigen Knoten zeigt, wird die verknüpfte Liste zu einer doppelt verknüpften Liste. Wenn wir auf Basis einer doppelt verknüpften Liste auch next vom letzten Knoten auf den ersten Knoten zeigen lassen und prev vom ersten Knoten auf den letzten Knoten zeigen lassen, wäre das dann nicht eine doppelt verknüpfte Liste? Schauen wir uns das unten genauer an.

Zirkular verknüpfte Liste

Wie oben erwähnt, lassen wir den letzten Knoten auf den ersten Knoten zeigen, und die auf diese Weise gebildete verknüpfte Liste ist eine kreisförmig verknüpfte Liste, wie in der folgenden Abbildung dargestellt:

Über die Operationen von zirkulär verknüpften Listen Wir geben keine detaillierte Erklärung. Tatsächlich ist der größte Teil des Codes derselbe wie der einer einseitig verknüpften Liste, Sie müssen jedoch auf zwei Dinge achten:

1 Achten Sie beim Einfügen von Operationen auf die Richtung des letzten Knotens und zeigen Sie auf den ersten Knoten. Die Bedingung für die Beurteilung, ob die Durchquerung der verknüpften Liste abgeschlossen ist, ist item->next == head Das heißt, wenn der nächste Knoten dieses Knotens der Kopfknoten ist, ist die Durchquerung der verknüpften Liste abgeschlossen.

Doppelt verknüpfte Liste

Doppelt verknüpfte Liste fügt der LinkedList-Klasse ein Attribut hinzu, um auf den vorherigen Knoten zu verweisen.

// 双向链表
class LinkedList
{
    public $data;

    public $prev;
    public $next;
}

Als nächstes initialisieren wir eine doppelt verknüpfte Liste.

/**
 * 生成链表
 */
function createLinkedList()
{
    $list = new LinkedList();
    $list->data = null;
    $list->next = null;
    $list->prev = null; // ** 全部都初始化为 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;
        $link->prev = $r; // ** 增加上级指向 **
        $r = $link;
    }
    return $list;
}

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

var_dump($link);
var_dump($link->next->next->next->next);
// object(LinkedList)#5 (3) {
//     ["data"]=>
//     int(4)
//     ["prev"]=>
//     object(LinkedList)#4 (3) {
//       ["data"]=>
//       int(3)
//       ["prev"]=>
//       object(LinkedList)#3 (3) {
//         ["data"]=>
//         int(2)
//         ["prev"]=>
//         object(LinkedList)#2 (3) {
//           ["data"]=>
//           int(1)
//           ["prev"]=>
//           object(LinkedList)#1 (3) {
//             ["data"]=>
//             NULL
//             ["prev"]=>
//             NULL
//             ["next"]=>
//             *RECURSION*
//           }
//           ["next"]=>
//           *RECURSION*
//         }
//         ["next"]=>
//         *RECURSION*
//       }
//       ["next"]=>
//       *RECURSION*
//     }
//     ["next"]=>
//     object(LinkedList)#6 (3) {
//       ["data"]=>
//       int(5)
//       ["prev"]=>
//       *RECURSION*
//       ["next"]=>
//       object(LinkedList)#7 (3) {
//         ["data"]=>
//         int(6)
//         ["prev"]=>
//         *RECURSION*
//         ["next"]=>
//         object(LinkedList)#8 (3) {
//           ["data"]=>
//           int(7)
//           ["prev"]=>
//           *RECURSION*
//           ["next"]=>
//           object(LinkedList)#9 (3) {
//             ["data"]=>
//             int(8)
//             ["prev"]=>
//             *RECURSION*
//             ["next"]=>
//             object(LinkedList)#10 (3) {
//               ["data"]=>
//               int(9)
//               ["prev"]=>
//               *RECURSION*
//               ["next"]=>
//               object(LinkedList)#11 (3) {
//                 ["data"]=>
//                 int(10)
//                 ["prev"]=>
//                 *RECURSION*
//                 ["next"]=>
//                 NULL
//               }
//             }
//           }
//         }
//       }
//     }
//   }

echo $link->next->next->next->next->data, PHP_EOL; // 4
echo $link->next->next->next->next->prev->data, PHP_EOL; // 3

Es ist ersichtlich, dass der Unterschied zur einseitig verknüpften Liste darin besteht, dass es mehr Operationen für das prev-Attribut gibt. Hier ist es relativ einfach zu verstehen. Beim direkten Drucken der verknüpften Liste wird viel *RECURSION*-Inhalt angezeigt. Dies ist ein Ausgabeschutzmechanismus von PHP. Diese Markierung zeigt an, dass die aktuelle Attributvariable einen rekursiven Typ hat.

/**
 * 链表指定位置插入元素
 * @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;

    // ** 增加当前新创建的节点的上级指向 **
    $s->prev = $item;

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

    // ** 将下级节点的 prev 指向新创建的这个节点 **
    $s->next->prev = $s;

    return true;
}

Durch das Einfügen der verknüpften Liste werden tatsächlich zwei Codezeilen hinzugefügt. Eine davon ist der Zeiger auf den übergeordneten Knoten des aktuell neu erstellten Knotens, dh der übergeordnete Knoten dieses neuen Knotens wird als i-1-Knoten bezeichnet. Die andere besteht darin, den übergeordneten Zeiger des ursprünglichen i-Positionsknotens auf den neu erstellten Knoten zu ändern.

/**
 * 删除链表指定位置元素
 * @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;

    // ** 让目标下一个节点的上级指针指向当前这个节点 **
    $temp->next->prev = $item;

    return true;
}

Ähnlich wie bei der Operation zum Einfügen eines Knotens ändert die Operation zum Löschen eines Knotens nicht nur die Ausrichtung des nächsten Knotens der Daten des i-1-Positionsknotens auf die Ausrichtung des Knotens der nächsten Ebene des i-Knotens, sondern auch Änderungen der Knoten der nächsten Ebene von i. Der übergeordnete Knoten des Knotens zeigt auf den i-1-Knoten.

Tatsächlich unterscheiden sich die Definition und Funktionsweise einer doppelt verknüpften Liste nicht wesentlich von der einer einseitig verknüpften Liste. Es gibt lediglich einen zusätzlichen Prev, der auf den Knoten der oberen Ebene verweist sind lediglich weitere Operationen für das prev-Attribut. Welche Vorteile bringt dieser besonders hochwertige Zeiger? Beim Durchlaufen der verknüpften Liste verwenden wir prev, um über eine zusätzliche Durchlaufmethode zu verfügen, die darin besteht, die verknüpfte Liste in umgekehrter Reihenfolge zu durchlaufen. Bei der Suche nach einem bestimmten Element können wir gleichzeitig aus zwei Richtungen suchen und die Effizienz wird auf einmal verdoppelt. Die ursprüngliche Zeitkomplexität von O(n) kann sofort zur O(n/2)-Zeitkomplexität werden.

Zwei-Wege-zirkulär verknüpfte Liste

Abschließend stellen wir die bidirektional-zirkulär verknüpfte Liste kurz vor. Wie der Name schon sagt, fügt es einer doppelt verknüpften Liste das Konzept einer zirkulär verknüpften Liste hinzu. Lassen Sie next vom letzten Knoten auf den Kopfknoten zeigen und prev vom Kopfknoten auf den letzten Knoten zeigen. Das lässt sich leicht sagen, ist aber tatsächlich viel komplizierter in der Umsetzung, da man nicht nur auf das Pointing-Problem der untergeordneten Knoten des letzten Knotens achten muss, sondern auch auf das Problem der übergeordneten Pointing-Funktion des Kopfknotens. Deshalb werden wir hier nicht zu viel Code demonstrieren. Das Wichtigste ist, dass Sie beim Einfügen und Löschen von Kopf- und Endknoten mehr auf die Ausrichtung ihrer oberen und unteren Knoten achten müssen.

Zusammenfassung

Hast du plötzlich eine neue Welt entdeckt? Es gibt so viele Formen verknüpfter Listen. Natürlich ist dies noch nicht abgeschlossen. Wir haben jedoch immer noch eine vernetzte Liste auf hoher Ebene, die nur die gleichen Daten enthält . Tatsächlich liegt der eigentliche Schwerpunkt beim Erlernen verknüpfter Listen auf der gebräuchlichsten einseitig verknüpften Liste, die im vorherigen Artikel ausführlich vorgestellt wurde.

Sie müssen sich also keine Sorgen machen oder in Panik geraten, wenn Sie die gewöhnliche einseitige verknüpfte Liste beherrschen. Aber was ist mit diesen Dingen, die Sie heute gelernt haben? Wenn Sie es beherrschen, können Sie sich zumindest damit vertraut machen. Das Wichtigste im Leben ist, sich nicht zu sehr anzustrengen, Sie werden entweder ein Drache oder ein Erwachsener. Erkennen Sie Ihre aktuelle Situation und Ihre Fähigkeiten. Das ist das Wichtigste.

关于线性表的内容到此为止。物理结构的存储问题就是这样了，接下来我们就要逻辑结构的世界了。也是从最简单的开始，那就是栈和队列，不要怕，它们和 树、图 比起来真的是洒洒水啦！！

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/2.线性表/source/2.4%20链表的其它形式.php

推荐学习：php视频教程

Das obige ist der detaillierte Inhalt vonGibt es andere Darstellungsformen verknüpfter Listen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!