Explication détaillée de la liste chaînée en php

Le fonctionnement de la liste chaînée est bien plus compliqué que celui de la liste séquentielle. Parce que PHP a en effet résolu de nombreux problèmes de fonctionnement des tableaux pour nous, nous pouvons utiliser les tableaux très facilement et nous n'avons pas besoin de définir de nombreuses opérations logiques pour les tableaux. Par exemple, en C, les tableaux ont une limite de longueur, mais en PHP nous ne considérerons pas ce problème.

La définition de la structure chaînée

Tout d'abord, dans le premier article précédent sur les listes linéaires, nous avons parlé de la définition des listes chaînées. Ici, nous allons revoir le diagramme précédent sur les listes chaînées pour obtenir plus de détails. Comprendre clairement le concept de listes chaînées.

Nous représentons le nœud Node dans l'image comme une classe :

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

Une classe de liste chaînée peut être considérée comme un nœud dans la liste chaînée. Elle contient deux contenus, data représente les données et next représente le nœud suivant. .pointeur. Tout comme une chaîne, un maillon dans un autre, c'est la légendaire structure de liste chaînée.

Génération d'une liste chaînée et opérations d'initialisation

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

//                                                                         )

//                                                                 )

//                                                         )

//                                                 )

//                                         )

//                                 )

//                         )

//                 )

//         )

// )

Lors de l'utilisation d'une liste chaînée, nous faisons généralement en sorte que le premier nœud ne contienne aucune donnée, mais sert simplement de nœud vide pour pointer vers le premier nœud contenant des données. Nous pouvons appeler ce type de nœud le nœud principal. Si vous devez déterminer si la liste chaînée est vide, il vous suffit de déterminer si le prochain du premier nœud est vide. Dans le code ci-dessus, la fonction createLinkedList() génère en fait un tel nœud principal.

Ensuite, nous construisons cette liste chaînée via la fonction d'initialisation Init(). Le processus de construction est relativement simple. Ici, nous passons un tableau et construisons la liste chaînée en fonction de la structure du tableau. Bien sûr, dans les applications pratiques, nous pouvons utiliser n'importe quelle donnée pour construire la liste chaînée. Le processus de construction n'est pas compliqué. Il suffit d'attribuer le nœud actuel à la variable r, puis de créer un nouveau nœud et de rendre r->next égal au nœud nouvellement créé. La structure imprimée directement à partir de la liste chaînée construite est la forme dans le commentaire.

Parcours d'une liste chaînée

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

Le parcours d'une liste chaînée est-il très similaire au fonctionnement du curseur de certaines bases de données, ou au fonctionnement du mode itérateur ? C'est vrai, en fait, la structure des curseurs et des itérateurs est une forme de liste chaînée. Nous continuons à chercher $next jusqu'à ce qu'il n'y ait plus de nœud suivant, complétant ainsi un parcours de liste chaînée. On peut voir que la complexité temporelle de ce processus est O(n).

Insertion et suppression

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

L'insertion et la suppression de listes chaînées sont en fait très similaires. Elles doivent toutes deux trouver l'élément précédent à la position d'insertion ou de suppression, qui est l'élément à la i-1ème position. Ensuite, l'insertion et la suppression des éléments de la liste chaînée sont implémentées en actionnant le pointeur suivant de cet élément.

Les codes dans les deux fonctions de parcours et de jugement de position sont en fait les mêmes. La différence est que lors de la création, vous devez créer un nouveau nœud, puis laisser le suivant de ce nœud pointer vers le suivant du i- précédent. 1 élément de position. Pointez ensuite le prochain élément à la position i-1 vers le nœud nouvellement créé. L'opération de suppression consiste à enregistrer le nœud à la position i à supprimer dans une variable temporaire, puis à faire pointer le prochain élément à la position i-1 vers le suivant à la position supprimée i.

L'explication ci-dessus doit être consultée étape par étape en conjonction avec le code. Bien sûr, nous pouvons également l'apprendre en conjonction avec l'image ci-dessous. Les opérations d'insertion et de suppression sont au cœur des opérations de liste chaînée et la partie la plus complexe, qui nécessite beaucoup de compréhension et de maîtrise.

Recherche basée sur la position, recherche basée sur les données

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

Il existe deux formes de recherche dans les listes chaînées. La première consiste à donner une position. Par exemple, si je veux que le contenu de l'élément soit en cinquième position. L'élément est recherché en fonction de la valeur de position spécifiée, tout comme un index de tableau. Cependant, il convient de noter que l'index de la liste chaînée commence à 1, car la position 0 est notre nœud principal. Bien sûr, on peut aussi changer le code pour ignorer le nœud demi-tour et le rendre cohérent avec le tableau, mais dans ce cas, les caractéristiques de la liste chaînée ne seront pas évidentes, on commence donc toujours par 1 dans le code de test ici.

Un autre type de recherche consiste à donner le contenu d'une donnée et à trouver sa position dans la liste chaînée. En fait, les deux algorithmes parcourent l’intégralité de la liste chaînée et il n’y a pratiquement aucune différence. Puisqu'une liste chaînée n'a pas la capacité d'indicer comme un tableau, la complexité temporelle de ses opérations de recherche est O(n).

Résumé

Que diriez-vous, la difficulté augmente. Le fonctionnement de la liste chaînée sera beaucoup plus compliqué. Ne vous inquiétez pas, ce n'est qu'un apéritif. Le contenu que vous apprendrez plus tard tournera essentiellement autour des deux formes de listes séquentielles (tableaux) et de listes chaînées. Et notre étude des listes chaînées n'est pas encore terminée. Dans le prochain article, nous examinerons plus en détail d'autres formes de listes chaînées : les listes chaînées doublement, les listes chaînées circulaires et les listes chaînées doublement circulaires.

Code de test :

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

Apprentissage recommandé : Tutoriel vidéo 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!