循環リンクリストにノードを挿入するアルゴリズムを実装する

Question

この問題の解決策を考えていました。

私の入力：
1.最後のノードを指すテールポインタを持っています。
2.最後のポインタが分かれば、簡単に隣に新しいノードを追加できます。

Void Insert(Node N) 
{ 
    if (head == null) // linked list is empty 
    { 
     head = N; tail = N; tail.Next = head; 
    } 
    else 
    {   
     Node temp = tail.Next; // since this is circular tail will point to head 
     Tail.Next = N; 
     N.Next = temp; // correct 
     tail = N;  
    } 
} 

テールポインタを使用しなくても、より良い解決策を考えることができますか？また、トラバースしない問題でも述べられているように？ これはインタビューの質問ですが、最適なソリューションを見つけるためにはいくつかの入力が必要です。

Answer 1

あなたは単独でリンクされた循環リストと、1つの要素へのポインタ（これをヘッドノードと呼ぶ）があると思います。従って、リストの各ノードは、値と次の要素へのポインタとからなる。テールノードはヘッドノードを指す。ヘッドノードの直後にノードを挿入するのは簡単です。あなたが直接ノードを挿入したいと思うのは、の前に、のヘッドノードです。そのためには、新しいノードが最後のノードになる必要があります。このノードは、前の最後のノードからポイントされ、ヘッドノードを指します。今度は、最後のノードを見つけるためにリストをトラバースすることを避けたい。つまり、その最後のノードにアクセスすることはできず、ポインタを変更することはできません。

1. が後
2. は、その新しいノードに現在のヘッドノードの値をコピーして、ヘッドノードを新しいノードを挿入します。この作業を行うための唯一の他の方法は、最後のノードポイントは、つまり場所を変更することです
は
4. は、新しいノードの新しいヘッドノード私はあなたのコードビット簡略化されてきた

Answer 2

いいえ、テールポインタが必要です。それ以外の場合は、リストをトラバースする必要があります。リストの終わりがどこにあるか分からない。

あなたは賢明なインデックス作成算術を思いつくことができますが、それでも頭や尾へのポインタになります。

Answer 3

あなたはヘッドノードも持っています。あなたもそれを使用して挿入することができます。私は新しいノードを挿入する場所に制限がないと仮定しています（質問は明示的にそれを指定しません）。

頭に挿入するのは簡単です。

編集「より良い」のあなたの尺度は頭と尾のポインタの両方を維持できないのであればヘッド

Answer 4

後にそれを挿入して、あなたの代わりに、単にテールポインタを維持することができます。ヘッドポインタは暗黙的に（tail.Nextによって与えられます）。

実際には、リストへのアクセスは非常に一般的です（循環リストをキューとして使用している場合など）。また、ヘッドにアクセスするための余分なステップがあるとオーバーヘッドが増えます。私が行ったプロジェクトのテストでは、このようにヘッドポインタを削除すると、メモリの一部が減少しました（リストは一般的に短かったが、それらの多くはあった）が、リストの先頭にアクセスしてから時間が増えた。 YMMV。

Answer 5

を行い、現在のヘッドノードに新しい価値を置きます。 temp変数の必要はありません。設定した後は何も使用しませんでした。

Void Insert(Node N) { 
    if (head == null) { // linked list is empty 
     head = tail = N; 
    } 
    else { // insert after tail 
     tail.Next = N; 
     tail = N;  
    } 
    tail.Next = head; 
} 

Answer 6

頭と尾を格納する代わりに、テールを格納してください。

Void Insert(Node N) 
{ 
    if (tail == null) // linked list is empty 
    { 
     tail = N.Next = N; 
    } 
    else 
    { 
     N.Next = tail.Next; 
     tail = tail.Next = N; 
    } 
} 
Node Head() { return tail == null ? null : tail.next; }