インデックス付き単リンクリスト

Question

単一リンクリストを作成したいと思います。私は既にインデックス作成を許可していない実装を持っています。 この機能を追加したいと思いますが、その方法はわかりません。

だから、基本的にヘッドは、インデックス "1" を持っている必要があります。しかし、私はそれが自分自身を理解することはできませんどのような場合は、1各ステップでインデックスを増やすために私は何をすると思います。

void AddNode (int addData) 
{ 
    nodePtr NewNode = new node; 
    NewNode->next = NULL; 
    NewNode->data = addData; 

    if (head != NULL) 
    { 
     curr = head; 
     while(curr->next != NULL) 
     { 
      curr = curr->next; 
     } 
     curr->next = NewNode; 
     NewNode->index; 
    } 
    else 
    { 
     head = NewNode; 
     NewNode->index = 1; 
    } 
} 

Answer 1

get（index）を使用してリンクリストノードを取得するようなことは、

また、頭にはインデックス1を付けるべきではありません。0にする必要があります。これは、ゼロベースのインデックス作成の標準的な方法には準拠していません。

リンクされたリストは、技術的にインデックスを持っておらず、またそれらを保存する必要もありません。それは（私のC++構文が錆びている場合言い訳）しかし、あなたは、このようなループでそのよう

int get(int index) { 
    Node current = head; 
    for (int x = 0; x < index; x++) { 
    if (current->next == null) { 
     //some sort of error handling for index out of bounds 
    } else { 
     current = current->next; 
    } 
    } 
    return current->data 
} 

取得し、それを扱うことができ、あなたがやっていることのための適切なデータ構造ではないかもしれないリンクリストのように思える（2 ）は、リストの3番目の要素を返します。

Answer 2

Graph for the structure なぜそれをリストの最後に追加しますか？新しいノードを正面に追加するだけです。

1,2,3の順番に従う必要はないと思われます。代わりに逆にすることができます 新しいノードを追加する前に、頭にアクセスしてインデックスを検索します私はそれの）。新しいものを追加すると、このインデックスはi + 1になります。

2つの利点： - このリストをループすると何も変わりません。 - このリストに追加した人の数が分かります。

Answer 3

実際にしたいことは、能力をリンクリストの要素のインデックスに追加することです。あなたが本当にタイプと配列の最初の要素のアドレスとしてarray/vector要素のインデックスを格納しないよう、実際に（どこでもインデックスを格納する必要はありません

• は、あなたが取得するために必要なものがすべてですi-th要素）。

• リストの長さは、必要なたびにheadからtailにリストをトラバースする必要があるため、計算がコストがかかるので、リストの長さだけです。この情報を取得したら、addNodeはリストのsizeのみを更新する必要があります。

すでにリンクされたリストのi-th要素にアクセス知っているようにも（ベクトルと比較して）コストがかかるが、それはコードに簡単です。

次のようなものが動作するはずです：それはどちらかの端に到達した（headがnullptrである）、またはposが<=0なるまで

void get(Node* head, size_t pos) { 
    while (head && pos--) 
     head = head->next; 
    return pos<=0 ? head : nullptr ; 
} 

それはheadからリストをトラバースします。 pos>0リストがそうでなければ、あなたが規則を一致させたい場合は、ヘッドがインデックス0を持つべきである（pos-th要素を指します）head