Premiers pas avec la liste liée

Installation ou configuration #

Instructions détaillées sur la configuration ou l’installation de la liste liée.

Conception à l’aide de Sentry Node #

Lors de la conception d’une liste chaînée, vous pouvez éviter tous les cas particuliers (liste vide, premier nœud, dernier nœud, etc.) en utilisant un nœud sentinelle. Voyons comment cela se fait :

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, ce lien vers lui-même s’il n’y a pas de nœuds de données. Le nœud sentinelle double également comme l’un après le dernier marqueur.

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