リンクされたリストを再帰的に削除すると、スタックのオーバーフローが発生しますか？

Question

私はNodeオブジェクトの外に構築されたリンクリストを持っている：

class Node { 
    public: 
     Node(string data); 
     Node* GetNext() const; 
     void SetNext(Node* nextNode); 
     ~Node(); 
    private: 
     string data; 
     Node* next; 
}; 

デストラクタは以下に定義される：デストラクタが頭Nodeに呼び出されなければなりません

Node::~Node() { 
    delete next; 
} 

。

私の質問は次のとおりです。このような単一リンクリストを削除すると、大きなリストでスタックオーバーフローが発生します（小数点以下は、<サイズリストで問題ありません）。もしそうであれば、

Nodeには定義されたコンストラクタはありません

while (head->GetNext() != 0) { 
    Node* temp = head->GetNext(); 
    head->SetNext(temp->GetNext()); 
    delete temp; 
} 
delete head; 

のような反復解法を使用する方がよいでしょうか？

Answer 1

解決策の問題は、~Node()メソッドへの呼び出しごとにスタックフレームがスタック上に連続的に増えていくことです。 3 Nodeオブジェクトの例を挙げると、たとえば0x01で始まります。百万Nodeのために、そう

(0) Node (0x01): ~Node 
(1) Node (0x02): ~Node 
(2) Node (0x03): ~Node 

：これらの削除は、次のスタックフレームのバックトレースを（私は各Nodeオブジェクトが真されていない、1ビットの情報が含まれていますが、それは少しすっきりリストを作ると仮定）がありますオブジェクトの場合、最初のものが完了する前に百万のスタックフレームがあります。。各スタックフレームはスタック上のスペースを占有するので、スタックスペースが足りなくなる可能性があります。

反復ごとに、Nodeを削除するための呼び出しが前に次のNode削除ルーチンの実行を完了し、ので、反復解法は、この問題に悩まされることはありません。これは、各反復中にスタック上で1回の関数呼び出し（その関数呼び出しを完了するのに必要な量をプラスまたはマイナスしますが、特にの再帰ではないことを意味します）を意味します。

この問題に加えて、別の問題が提起されています。つまり、ただ1つのNodeオブジェクトを削除する方法はありません。リスト全体またはリストの一部を削除することができます。前の例でクライアントがNode (0x02)への参照を持っていて、delete nodeを呼び出した場合に起こることを想像してください。この場合、Node (0x02)とNode (0x03)は削除されますが、Node (0x01)はNode (0x02)のメモリへのポインタを参照しています。これを逆参照するとクラッシュが発生します。

Answer 2

スタックサイズは、関数の再帰呼び出しの深さを常に制限します。デストラクタ（およびパラメータを持たない他の関数）であっても、その関数呼び出しの戻りアドレスを保持する必要があります（デストラクタは暗黙のパラメータとしてポインタを取得します）。

したがって、特定の上限のNodeから、スタックはオーバーフローします。はい。

反復的な方法はこれに関してはるかに堅牢です。