Adakah terdapat bentuk perwakilan senarai terpaut lain?

Dalam artikel sebelum ini, kami telah menyatakan bahawa sebagai tambahan kepada senarai terpaut sehala yang mudah, terdapat beberapa bentuk senarai terpaut yang lain. Sudah tentu, ini juga merupakan ciri utama struktur senarai terpaut, yang sangat fleksibel dan mudah. Mari kita fikirkan secara ringkas Jika nod terakhir seterusnya menghala kembali ke nod pertama, maka ini akan membentuk cincin, iaitu senarai pautan bulat.

Jika kita menambah atribut prev pada setiap nod yang menghala ke nod sebelumnya, maka senarai terpaut menjadi senarai terpaut dua kali. Jika kita juga membiarkan nod terakhir menghala ke nod pertama berdasarkan senarai terpaut berganda, dan membiarkan nod pertama menghala ke nod terakhir, bukankah ini senarai berpaut dua kali? Mari lihat lebih dekat di bawah.

Senarai pautan bulat

Seperti yang dinyatakan di atas, kami membiarkan nod terakhir menghala ke nod pertama, jadi senarai terpaut yang terbentuk ialah senarai pautan bulat, seperti yang ditunjukkan dalam rajah di bawah:

Kami tidak akan memberikan penjelasan terperinci tentang pengendalian senarai pautan bulat Sebenarnya, kebanyakan kod adalah sama dengan senarai pautan sehala, tetapi anda perlukan untuk memberi perhatian kepada dua tempat:

1. Apabila memulakan dan memasukkan operasi, perhatikan arah nod terakhir yang seterusnya harus menghala ke nod pertama

2 . Syarat untuk menilai sama ada traversal senarai terpaut selesai ialah item->next == head , iaitu, jika nod seterusnya nod ini ialah nod kepala, traversal senarai terpaut selesai.

Senarai terpaut berganda

Senarai terpaut berganda menambah atribut pada kelas LinkedList untuk menghala ke nod sebelumnya.

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

    public $prev;
    public $next;
}

Seterusnya, kami memulakan senarai terpaut dua kali.

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

Ia boleh dilihat bahawa perbezaan daripada senarai terpaut sehala ialah terdapat lebih banyak operasi pada atribut prev. Ia agak mudah difahami di sini. Mencetak senarai terpaut secara langsung akan memaparkan banyak kandungan *RECURSION*, yang merupakan mekanisme perlindungan keluaran PHP Tanda ini menunjukkan bahawa pembolehubah atribut semasa mempunyai jenis rekursif.

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

Sisipan senarai terpaut sebenarnya menambah dua baris kod Satu ialah penunjuk kepada atasan nod yang baru dibuat, iaitu, atasan nod baharu ini ditetapkan sebagai i-. 1 nod. Yang satu lagi ialah menukar penuding unggul nod kedudukan i asal kepada nod yang baru dibuat.

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

Sama seperti operasi nod sisipan, operasi nod pemadaman bukan sahaja menukar penunjuk nod seterusnya data nod kedudukan i-1 kepada penunjuk nod peringkat seterusnya bagi nod i , tetapi juga Tukar titik nod atasan nod peringkat bawah i kepada nod i-1.

Malah, takrifan dan pengendalian senarai terpaut berganda tidak jauh berbeza daripada senarai terpaut sehala Ia hanya mempunyai prev tambahan untuk menunjuk ke nod peringkat atas. ia hanya menambah atribut sebelumnya Ia hanya operasi. Jadi, apakah faedah yang dibawa oleh penunjuk lebih unggul ini? Apabila melintasi senarai terpaut, kami menggunakan prev untuk mempunyai kaedah traversal tambahan, iaitu melintasi senarai terpaut secara terbalik. Apabila mencari elemen tertentu, kita boleh mencari dari dua arah pada masa yang sama, dan kecekapan digandakan sekaligus. Kerumitan masa asal O(n) boleh menjadi kerumitan masa O(n/2) serta-merta.

Senarai pautan pekeliling dua hala

Akhir sekali, kami akan memperkenalkan senarai pautan pekeliling dua hala secara ringkas. Seperti namanya, ia menambahkan konsep senarai pautan bulat kepada senarai pautan berganda. Biarkan seterusnya nod terakhir menghala ke nod kepala, dan biarkan nod kepala sebelum menghala ke nod terakhir. Ia mudah untuk mengatakan tetapi ia sebenarnya lebih rumit untuk dilaksanakan, kerana anda bukan sahaja perlu memberi perhatian kepada masalah penunjuk nod bawahan nod terakhir, tetapi juga masalah penunjuk atas nod kepala. Oleh itu, kami tidak akan melakukan terlalu banyak demonstrasi kod di sini Perkara yang paling penting ialah apabila memasukkan dan memadam nod kepala dan ekor, anda perlu memberi lebih perhatian kepada penunjuk nod atas dan bawahnya.

Ringkasan

Adakah anda tiba-tiba menemui benua baharu? Terdapat begitu banyak bentuk senarai terpaut. Sudah tentu, ini belum selesai. Kami masih mempunyai senarai pautan silang yang sangat tinggi untuk dibincangkan Namun, sebenarnya, senarai pautan silang hanya menambah lebih banyak atribut yang menunjukkan data yang sama . Malah, senarai terpaut sehala yang paling biasa, yang diperkenalkan secara terperinci dalam artikel sebelumnya, adalah fokus sebenar pembelajaran tentang senarai terpaut.

Oleh itu, tidak perlu risau atau panik Jika anda menguasai senarai pautan sehala yang biasa, anda boleh membunuh kebanyakan orang dalam sekelip mata. Tetapi bagaimana dengan perkara yang anda pelajari hari ini? Jika anda boleh menguasainya, anda sekurang-kurangnya boleh membiasakan diri dengannya. Perkara yang paling penting dalam hidup adalah jangan terlalu memaksa diri sendiri. Kenali situasi dan kebolehan anda sekarang. Itu yang paling penting.

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

测试代码：

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

推荐学习：php视频教程

Atas ialah kandungan terperinci Adakah terdapat bentuk perwakilan senarai terpaut lain?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!