Existe-t-il d'autres formes de représentation des listes chaînées ?

Dans le dernier article, nous avons déjà dit qu'en plus de la simple liste chaînée à sens unique, il existe plusieurs autres formes de listes chaînées. Bien entendu, il s’agit également d’une caractéristique majeure de la structure de liste chaînée, qui est très flexible et pratique. Pensons-y brièvement, si le prochain du dernier nœud pointe vers le premier nœud, cela formera un anneau, qui est une liste chaînée circulaire.

Si nous ajoutons un attribut prev à chaque nœud qui pointe vers le nœud précédent, alors la liste chaînée devient une liste doublement chaînée. Si nous faisons également en sorte que le nœud suivant du dernier nœud pointe vers le premier nœud et que le précédent du premier nœud pointe vers le dernier nœud en fonction de la liste chaînée bidirectionnelle, ne serait-ce pas une liste chaînée circulaire bidirectionnelle ? Regardons de plus près ci-dessous.

Liste chaînée circulaire

Comme mentionné ci-dessus, nous laissons le dernier nœud pointer vers le premier nœud, et la liste chaînée ainsi formée est une liste chaînée circulaire, comme le montre la figure ci-dessous :

À propos de opérations des listes chaînées circulaires Nous ne donnerons pas d'explication détaillée. En fait, la plupart du code est le même que celui d'une liste chaînée unidirectionnelle, mais vous devez faire attention à deux choses :

1. et les opérations d'insertion, faites attention à la direction du dernier nœud et au prochain du dernier nœud. Pointez vers le premier nœud

2 La condition pour juger si le parcours de la liste chaînée est terminé est item->next == head. C'est-à-dire que si le nœud suivant de ce nœud est le nœud principal, le parcours de la liste chaînée est terminé.

Liste chaînée double

La liste chaînée double ajoute un attribut à la classe LinkedList pour pointer vers le nœud précédent.

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

    public $prev;
    public $next;
}

Ensuite, nous initialisons une liste doublement chaînée.

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

On peut voir que la différence avec la liste chaînée unidirectionnelle est qu'il y a plus d'opérations sur l'attribut prev. C’est relativement facile à comprendre ici. L'impression directe de la liste chaînée affichera beaucoup de contenu *RECURSION*, qui est un mécanisme de protection de sortie de PHP. Cette marque indique que la variable d'attribut actuelle a un type récursif.

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

L'insertion de la liste chaînée ajoute en fait deux lignes de code. L'une est le pointeur vers le supérieur du nœud actuellement nouvellement créé, c'est-à-dire que le supérieur de ce nouveau nœud est désigné comme nœuds i-1. L'autre consiste à remplacer le pointeur supérieur du nœud de position i d'origine par le nœud nouvellement créé.

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

Semblable à l'opération de nœud d'insertion, l'opération de nœud de suppression change non seulement le pointage du nœud suivant des données du nœud de position i-1 vers le pointage du nœud de niveau suivant du nœud i, mais change également le nœud de niveau suivant de i Le nœud supérieur du nœud pointe vers le nœud i-1.

En fait, la définition et le fonctionnement d'une liste doublement chaînée ne sont pas très différents de ceux d'une liste chaînée unidirectionnelle, c'est juste qu'il y a un précédent supplémentaire pour pointer vers le nœud de niveau supérieur. c'est juste plus d'opérations sur l'attribut précédent. Alors, quels avantages apporte ce pointeur extra supérieur ? Lors du parcours de la liste chaînée, nous utilisons prev pour avoir une méthode de parcours supplémentaire, qui consiste à parcourir la liste chaînée en sens inverse. Lors de la recherche d'un certain élément, nous pouvons rechercher dans deux directions en même temps, et l'efficacité est immédiatement doublée. La complexité temporelle originale de O(n) peut instantanément devenir une complexité temporelle O(n/2).

Liste chaînée circulaire bidirectionnelle

Enfin, nous présenterons brièvement la liste chaînée circulaire bidirectionnelle. Comme son nom l'indique, il ajoute le concept de liste chaînée circulaire à une liste doublement chaînée. Laissez le prochain du dernier nœud pointer vers le nœud principal et laissez le précédent du nœud principal pointer vers le dernier nœud. C'est facile à dire mais c'est en réalité beaucoup plus compliqué à mettre en œuvre, car il faut non seulement faire attention au problème de pointage des nœuds subordonnés du dernier nœud, mais aussi au problème du pointage supérieur du nœud principal. Nous ne ferons donc pas trop de démonstration de code ici. La chose la plus importante est que lors de l'insertion et de la suppression de nœuds de tête et de queue, vous devez prêter plus d'attention au pointage de leurs nœuds supérieurs et inférieurs.

Résumé

Avez-vous soudainement découvert un nouveau monde ? Il existe de nombreuses formes de listes chaînées. Bien sûr, ce n'est pas encore fini. Nous avons encore une liste réticulée très haut de gamme à aborder. Cependant, en fait, la liste réticulée ne fait qu'ajouter des attributs de pointage supplémentaires. Le champ de données de base est toujours le même. . En fait, la liste chaînée unidirectionnelle la plus courante, qui est celle présentée en détail dans l'article précédent, est le véritable objectif de l'apprentissage des listes chaînées.

Donc, vous n'avez pas besoin d'être anxieux ou de paniquer. Si vous maîtrisez la liste chaînée à sens unique ordinaire, vous pouvez tuer la plupart des gens en un instant. Mais qu'en est-il de ces choses que vous avez apprises aujourd'hui ? Si vous pouvez le maîtriser, vous pouvez au moins le connaître. La chose la plus importante dans la vie est d'être heureux. Ne vous forcez pas, vous deviendrez soit un dragon, soit un ver. Reconnaissez votre situation actuelle et vos capacités. C'est la chose la plus importante.

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

测试代码：

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

推荐学习：php视频教程

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!