PHPでのリンクリストの詳しい説明

リンク リストの操作はシーケンス リストの操作よりもはるかに複雑です。実際、PHP は多くの配列操作の問題を解決してくれたので、非常に便利に配列を操作でき、配列に対して多くの論理操作を定義する必要がありません。たとえば、C では配列には長さの制限がありますが、PHP ではこの問題は考慮されません。

連結構造の定義

まず、線形リストの第一回目で連結リストの定義についてお話しましたが、ここで復習してみましょう。リンク リストの概念をより明確に理解するために、リンク リストに関する前の図を参照してください。

グラフ内のノード Node をクラスとして表します:

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

リンク リスト クラスは、リンク リスト内のノードとみなすことができます。 2 つの内容で、data はデータを表し、next は次のノードのポインタを表します。ちょうど鎖のように、1 つのリンクが別のリンクの中にある、これは伝説的なリンク リスト構造です。

リンク リストの生成と操作の初期化

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

//                                                                         )

//                                                                 )

//                                                         )

//                                                 )

//                                         )

//                                 )

//                         )

//                 )

//         )

// )

リンク リストを使用する場合、通常、最初のノードにはデータを含めず、3 番目のノードを指す空のノードとして機能します。データを含むノード。この種のノードをヘッド ノードと呼ぶことができ、リンク リストが空かどうかを判断する必要がある場合は、最初のノードの次のノードが空かどうかを判断するだけで済みます。上記のコードでは、createLinkedList() 関数が実際にそのようなヘッド ノードを生成します。

次に、Init() 初期化関数を通じてこのリンク リストを構築します。構築プロセスは比較的単純です。ここでは配列を渡し、配列構造に従ってリンク リストを構築します。もちろん、実際のアプリケーションでは、任意のデータを使用してリンク リストを構築できます。構築プロセスは複雑ではなく、現在のノードを r 変数に代入し、新しいノードを作成し、r->next を新しく作成したノードと等しくするだけです。構築されたリンクリストから直接出力される構造は、コメント内の形式です。

リンク リストのトラバース

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

リンク リストのトラバースは、一部のデータベースのカーソル操作、またはイテレータ モードの操作に非常に似ていますか?そうです、実際、カーソルとイテレータの構造は連結リストの形式です。次のノードがなくなるまで $next を探し続け、リンク リストの走査を完了します。このプロセスの時間計算量は O(n) であることがわかります。

挿入と削除

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

リンク リストの挿入と削除は実際には非常によく似ています。両方とも、挿入位置または削除位置で前の要素 (i 番目の要素) を検索する必要があります。 -1位。そして、リンクリスト要素の挿入と削除は、この要素のネクストポインタを操作することで実現されます。

トラバーサルと位置判定の 2 つの関数のコードは実際には同じです。違いは、作成時に新しいノードを作成する必要があり、このノードの次のノードが前の i-1 を指すことです。要素の次の位置を指定し、位置 i-1 にある要素の次の要素が新しく作成されたノードを指します。削除操作は、削除する位置 i のノードを一時変数に保存し、位置 i-1 の次の要素を削除した位置 i の次の要素にポイントします。

上記の説明は、コードを使って段階的に確認する必要がありますが、もちろん、次の図で学習することもできます。挿入と削除の操作はリンク リスト操作の中核であり、最も複雑な部分であり、多くの理解と習熟が必要です。

位置に基づく検索、データに基づく検索

/**
 * 根据位置查找元素位置
 * @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)

リンク リスト検索には 2 つの形式があり、1 つは位置を指定するものです。たとえば、次のようになります。 5 番目が必要です。 ある位置の要素の内容が見つかった場合、要素の値は、配列の添字と同様に、指定された位置に基づいて見つかります。ただし、0 の位置がヘッド ノードであるため、リンク リストのインデックスは 1 から始まることに注意してください。もちろん、U ターン ノードを無視して配列と一致させるようにコードを変更することもできますが、この場合、リンク リストの特性が明確ではないため、テスト コードでは引き続き 1 から開始します。ここ。

もう 1 つのタイプの検索は、データ コンテンツを指定して、それがリンクされたリスト内のどこにあるかを見つけることです。実際、どちらのアルゴリズムもリンク リスト全体を対象としており、本質的に違いはありません。リンク リストには配列のように添字を付ける機能がないため、検索操作の時間計算量は O(n) です。

まとめ

どうでしょう、難易度は上がっています。リンク リストの操作はさらに複雑になりますが、これは単なる前菜ですので、心配しないでください。後で学習する内容は、基本的に、逐次リスト (配列) とリンク リストの 2 つの形式を中心に展開します。リンク リストの研究はまだ終わっていません。次の記事では、リンク リストの他の形式 (二重リンク リスト、循環リンク リスト、二重循環リンク リスト) について詳しく見ていきます。

テスト コード:

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

推奨学習: php ビデオ チュートリアル

以上がPHPでのリンクリストの詳しい説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。