リンクリスト：再帰を使用してノードを挿入

Question

次の2つのコードは、新しいノードをリンクリストに挿入するのと同じ働きをしますか？バージョン1において

verison1

version2

、新しいノードに前のノードを巻くことができるprevポインタがあります。

しかし、バージョン2ではそれが表示されません。バージョン2では、前のリンクが壊れています（つまり、新しいノードにリンクしていません）。何か不足していますか？

Answer 1

のは、あなたのバージョン2の挿入を掘り下げてみましょう：作業が呼び出しによって行われているので

void RecInsertSorted(Entry*& list, Entry* newOne) { 
    if (list == nullptr || newOne->name < list->name) { 
     newOne->next = list; 
     list = newOne; 
    else { 
     RecInsertSorted(list->next, newOne); 
    } 
} 

あなたはprevは必要ありません。何故ですか？ listパラメータはポインタへの参照であるためです。

newOneを最初の要素と2番目の要素の間に挿入するとします。終わりに、あなたはあなたのリストは次のようになりたい：

要素1 - > newOne - >要素2

条件 newOne->name < list->nameが満たされ

は、listの要素2を指します。しかしこれはポインタへの参照です、参照はelement1-> nextを参照しています！したがって、文list = newOne;が実行されると、それに応じてelement1->nextが更新され、リストが整形されます。

同様に、末尾にnewOneを挿入する場合、listはnullptrです。しかし、もう一度参考になるので、newOne->nextがnullptrになり、newOneがリストの最後になります。

また、newOneを最初の要素の前に挿入する必要がある場合は、headポインタを更新してリストの先頭を追跡します。したがって、リストの最初の要素になります。