linked-listリンクリストの使い方


備考

このセクションでは、リンクされたリストの概要と、開発者がリンクリストを使用する理由を概説します。

また、リンクされたリスト内の大きな件名についても言及し、関連するトピックにリンクする必要があります。リンクリストのドキュメントは新しいので、これらの関連トピックの初期バージョンを作成する必要があります。

セントリノードを使用した設計

リンクされたリストを設計する場合、監視ノードを使用して、すべての特殊ケース(空のリスト、最初のノード、最後のノードなど)を避けることができます。それがどのように行われるか見てみましょう:

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

これは、例えば空リストの場合には失敗するように見えるが、セントリリーノードではリストは真に空ではなく、常にデータノードがない場合にはそれ自体にリンクするセントリノードを含む。哨戒ノードはまた、過去の最後のマーカーの2倍です。

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

より包括的なチュートリアルはhttps://pastebin.com/DXunz58Qにあります。

インストールまたはセットアップ

リンクリストの取得またはインストールに関する詳細な手順。