linked-listEmpezando con la lista enlazada


Observaciones

Esta sección proporciona una descripción general de qué es la lista enlazada y por qué un desarrollador puede querer usarla.

También debe mencionar cualquier tema grande dentro de la lista enlazada, y vincular a los temas relacionados. Dado que la Documentación para la lista enlazada es nueva, es posible que deba crear versiones iniciales de esos temas relacionados.

Diseño utilizando el nodo centinela

Al diseñar una lista enlazada, puede evitar todos los casos especiales (lista vacía, primer nodo, último nodo, etc.) utilizando 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 de centinela, la lista nunca está realmente vacía, siempre contiene el nodo de centinela, que se vincula a sí misma si no hay nodos de datos. El nodo centinela también se dobla como el último marcador pasado.

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

Instalación o configuración

Instrucciones detalladas sobre cómo configurar o instalar una lista de enlaces.