リンクされたリストの他の表現形式はありますか?-PHPの問題-php.cn

前の記事では、単純な一方向リンクリストに加えて、他の形式のリンクリストがいくつかあることをすでに述べました。もちろん、これはリンクリスト構造の大きな特徴でもあり、非常に柔軟で便利です。簡単に考えてみましょう。最後のノードの次が最初のノードを指す場合、これはリング、つまり循環リンクリストを形成します。

前のノードを指す prev 属性を各ノードに追加すると、リンクリストは二重リンクリストになります。また、二重リンクリストに基づいて最後のノードの next が最初のノードを指し、最初のノードの prev が最後のノードを指すようにすると、これは二重リンクリストではないでしょうか。以下で詳しく見てみましょう。

循環リンクリスト

上で述べたように、最後のノードが最初のノードを指すようにするため、形成されるリンクリストは、次の図に示すような循環リンクリストになります。

リンクされたリストの他の表現形式はありますか?

循環リンクリストの動作の詳細な説明は省略しますが、実際にはコードの大部分は一方向リンクリストのコードと同じですが、

1. 初期化および操作を挿入するときは、最後のノードのポイントに注意してください。最後のノードの次は最初のノードをポイントする必要があります。

2. リンクリストのトラバーサルが完了したかどうかの判定条件は、 item->next == head 、つまりこのノードの次のノードがヘッドノードであれば、リンクリストのトラバーサルは完了します。

二重リンクリスト

二重リンクリストは、前のノードを指す属性を LinkedList クラスに追加します。

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

    public $prev;
    public $next;
}

ログイン後にコピー

リンクされたリストの他の表現形式はありますか?

次に、二重リンクリストを初期化します。

/**
 * 生成链表
 */
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

ログイン後にコピー

一方向リンクリストとの違いは、prev 属性に対してより多くの操作があることがわかります。ここは比較的分かりやすいです。リンクされたリストを直接印刷すると、PHP の出力保護機構である *RECURSION* コンテンツが大量に表示されます。このマークは、現在の属性変数が再帰型であることを示します。

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

ログイン後にコピー

リンクリストの挿入により、実際には 2 行のコードが追加されます。1 つは、現在新しく作成されているノードの上位ノードへのポインタです。つまり、この新しいノードの上位ノードは i-1 ノードとして指定されます。。もう 1 つは、元の i 位置ノードの上位ポインタを新しく作成したノードに変更することです。

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

ログイン後にコピー

ノード削除操作は、挿入ノード操作と同様に、i-1 位ノードのデータの次のノードの点を i ノードの次のレベルのノードの点に変更するだけでなく、 i も変更下位ノードの上位ノード点が i-1 ノードに変更されます。

実際には、二重リンクリストの定義と操作は、一方向リンクリストの定義と操作とあまり変わりません。上位レベルのノードを指す prev が 1 つ多いだけです。本質的には、 prev 属性が 1 つだけあり、単なる操作です。では、この優れたポインタはどのようなメリットをもたらすのでしょうか?リンクリストを走査するときは、 prev を使用して、リンクリストを逆に走査する追加の走査メソッドを使用します。ある要素を探索する際に、二方向から同時に探索することができ、効率が一気に2倍になります。元の時間計算量 O(n) は、即座に O(n/2) 時間計算量になる可能性があります。

双方向循環リンクリスト

最後に、双方向循環リンクリストについて簡単に紹介します。名前が示すように、二重リンクリストに循環リンクリストの概念が追加されます。最後のノードの next がヘッドノードを指し、ヘッドノードの prev が最後のノードを指すようにします。言うのは簡単ですが、実際に実装するのははるかに複雑です。最後のノードの下位ノードのポインティングだけでなく、ヘッドノードの上位ノードのポインティングにも注意を払う必要があるからです。したがって、ここではコードのデモはあまり行いませんが、最も重要なことは、先頭ノードと末尾ノードを挿入および削除するときに、それらの上位ノードと下位ノードの向きにさらに注意を払う必要があるということです。

リンクされたリストの他の表現形式はありますか?

概要

突然新しい大陸を発見したことがありますか?リンクリストには非常に多くの形式があります。もちろん、これはまだ完了していません。まだ話すべき非常にハイエンドなクロスリンクリストがあります。しかし、実際には、クロスリンクリストは指示属性を追加するだけです。基本データフィールドは常に同じデータです。。実際、最も一般的な一方向リンクリスト (前の記事で詳しく紹介したもの) が、リンクリストについて学習する際の本当の焦点です。

したがって、心配したりパニックになったりする必要はありません。通常の一方通行のリンクリストをマスターすれば、ほとんどの人を一瞬で殺すことができます。しかし、今日学んだこれらのことはどうでしょうか?それをマスターできれば、少なくともそれに慣れることができます。人生で最も重要なことは幸せになることです。無理をしないでください。頑張りすぎると、ドラゴンになるか大人になるかのどちらかです。自分の現状と能力を認識する、それが一番大切です。

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

测试代码：

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

ログイン後にコピー

推荐学习：php视频教程

以上がリンクされたリストの他の表現形式はありますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

リンクされたリストの他の表現形式はありますか?

循環リンク リスト

二重リンク リスト

双方向循環リンクリスト

概要

循環リンクリスト

二重リンクリスト