linked-listAan de slag met gekoppelde lijst


Opmerkingen

Deze sectie biedt een overzicht van wat de gelinkte lijst is en waarom een ontwikkelaar deze mogelijk wil gebruiken.

Het moet ook alle grote onderwerpen in de gelinkte lijst vermelden en naar de gerelateerde onderwerpen linken. Omdat de documentatie voor de gekoppelde lijst nieuw is, moet u mogelijk eerste versies van die gerelateerde onderwerpen maken.

Ontwerp met behulp van Sentry Node

Bij het ontwerpen van een gekoppelde lijst kunt u alle speciale gevallen (lege lijst, eerste knooppunt, laatste knooppunt, enz.) Vermijden door een schildwachtknooppunt te gebruiken. Laten we eens kijken hoe dat wordt gedaan:

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

Dit lijkt erop dat het zou mislukken voor bijvoorbeeld een lege lijst, maar met een schildwachtknooppunt is de lijst nooit echt leeg, het bevat altijd het schildwachtknooppunt, die naar zichzelf linkt als er geen gegevensknooppunten zijn. De schildwachtknoop verdubbelt ook als die voorbij laatste marker.

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

Een uitgebreidere tutorial is te vinden op https://pastebin.com/DXunz58Q

Installatie of instellingen

Gedetailleerde instructies voor het instellen of installeren van de gekoppelde lijst.