linked-listDémarrer avec la liste liée


Remarques

Cette section fournit un aperçu de la liste des liens et des raisons pour lesquelles un développeur peut vouloir l'utiliser.

Il devrait également mentionner tous les grands sujets dans la liste des liens, et établir un lien avec les sujets connexes. La documentation de la liste liée étant nouvelle, vous devrez peut-être créer des versions initiales de ces rubriques connexes.

Conception à l'aide du nœud Sentry

Lors de la conception d'une liste chaînée, vous pouvez éviter tous les cas spéciaux (liste vide, premier nœud, dernier nœud, etc.) en utilisant un nœud sentinelle. Voyons comment ça se passe:

struct Node
{
    Node* next;
    Node* prev;
    T data;
};

// helper function to link 2 nodes
void Link(Node* n1, Node* n2)
{
    n1->next = n2;
    n2->prev = n1;
}

// this inserts new data before 'here'
Node* Insert(Node* here, const T& data)
{
    Node* item = new Node{0,0,data};  // create new item. use T's copy-constructor
    Link(here->prev, item);           // link in new node. item comes before here,
    Link(item, here);                 // so in-between `here->prev´ and `here´
    size += 1;                        // update size
    return item;
}

// erase one item
Node* Erase(Node* here)
{
    Node* nxt = here->next;           // save next item for return value
    Link(here->prev, here->next);     // unlink item. no special cases needed when using sentry
    delete here;                      // delete item. this will call T's destructor
    size -= 1;                        // update size
    return nxt;
}
 

Cela semble échouer pour une liste vide par exemple, mais avec un nœud sentinelle, la liste n'est jamais vraiment vide, elle contient toujours le nœud sentinelle, qui est lié à lui-même s'il n'y a pas de nœuds de données. Le nœud sentinelle est également le dernier marqueur passé.

Node* sentry;
void Init()
{
    sentry = (Node*)your_preferred_allocator();
    Link(sentry, sentry);
    size = 0;
}
 

Un tutoriel plus complet peut être trouvé sur https://pastebin.com/DXunz58Q

Installation ou configuration

Instructions détaillées sur la configuration ou l'installation de la liste des liens.