Primeros pasos con la lista enlazada

Instalación o configuración

Instrucciones detalladas sobre cómo configurar o instalar la lista enlazada.

Diseño usando Sentry Node

Al diseñar una lista enlazada, puede evitar todos los casos especiales (lista vacía, primer nodo, último nodo, etc.) mediante el uso de un nodo centinela. Veamos cómo se hace eso:

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;
}

Esto parece que fallaría para una lista vacía, por ejemplo, pero con un nodo centinela la lista nunca está realmente vacía, siempre contiene el nodo centinela, ese enlace a sí mismo si no hay nodos de datos. El nodo centinela también se duplica como el último pasado. marcador.

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

Puede encontrar un tutorial más completo en https://pastebin.com/DXunz58Q