linked-listRozpoczęcie pracy z połączoną listą


Uwagi

W tej sekcji omówiono, czym jest lista połączona i dlaczego deweloper może chcieć z niej skorzystać.

Powinien również wymieniać wszelkie duże tematy w ramach listy połączonej i zawierać linki do powiązanych tematów. Ponieważ dokumentacja dla listy połączonej jest nowa, konieczne może być utworzenie początkowych wersji tych powiązanych tematów.

Projektowanie za pomocą węzła Sentry

Projektując listę połączoną, można uniknąć wszystkich przypadków specjalnych (pusta lista, pierwszy węzeł, ostatni węzeł itp.), Używając węzła wartownika. Zobaczmy, jak to się robi:

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

Wygląda na to, że nie powiedzie się to na przykład dla pustej listy, ale w przypadku węzła wartowniczego lista nigdy nie jest naprawdę pusta, zawsze zawiera węzeł wartowniczy, który łączy się ze sobą, jeśli nie ma węzłów danych. Węzeł wartowniczy podwaja się także jako ostatni za ostatnim znacznikiem.

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

Bardziej wszechstronny samouczek można znaleźć na stronie https://pastebin.com/DXunz58Q

Instalacja lub konfiguracja

Szczegółowe instrukcje dotyczące konfigurowania lub instalowania listy linków.