今日、開発者の面接を受けましたが、答えがわからない興味深い技術的な質問をされました。ここで質問して、私の好奇心に対する解決策を誰かが提供してくれるかどうかを確認します。それは複数の部分からなる質問です:
1) 100 個の要素 (整数と次のノードへのポインター) を持つ単一リンク リストが与えられた場合、リンク リストの途中で破損または破損があるかどうかを検出する方法を見つけますか? リンクされたリストで何でもできます。リストは反復しているため、リストでこれを行う必要があることに注意してください。これは、リストに問題があることに気付く前の検証です。
リンクされたリストのブレークが 50 番目の要素にあると仮定すると、整数または次のノード (51 番目の要素) へのポインターでさえ、必ずしも無効なアドレスではないガベージ値を指している可能性があります。
2) リンクされたリストに破損がある場合、データの損失を最小限に抑えるにはどうすればよいでしょうか?
設計時に破損が重大な問題になる可能性があることがわかっている場合は、ノードデータ構造にフィールドとして「魔法の値」を追加して、一部のデータがノードである可能性が高いかどうかを識別できます。または、ノードの検索でメモリを実行することもできます。
または、リンク情報を2倍にします。つまり、各ノードの次のノードの後にノードのアドレスを格納して、1つのリンクが壊れた場合に回復できるようにします。
私が見る唯一の問題は、セグメンテーション違反を回避する必要があるということです。
最初の部分-新しい演算子をオーバーロードします。新しいノードが割り当てられるたびに、ノードの前後に追加のスペースを割り当て、そこにいくつかの既知の値を配置します。トラバーサルでは、各ノードが既知の値の間にあるかどうかを確認できます。
リンクされたリストに対して何でもできる場合、できることは、各要素のチェックサムを計算し、それを要素自体に格納することです。このようにして、要素のシングル ビット エラーであっても破損を検出できます。
データの損失を最小限に抑えるために、おそらく前の要素に nextPtr を格納することを検討できます。これにより、現在の要素が破損している場合でも、前の要素から次の要素の場所をいつでも見つけることができます。
これは簡単な質問で、いくつかの可能な答えがあります。いずれも堅牢性と効率のトレードオフです。堅牢性の向上は質問の前提条件であるため、時間 (リストのトラバーサル速度、ノードの挿入速度と削除速度) またはスペース (各ノードに保存される追加情報) の両方を犠牲にするソリューションがあります。問題は、これが長さ 100 の固定リストであるということです。この場合、連結リストのデータ構造は最も不適切です。パズルをもう少し難しくして、リストのサイズはアプリオリにわからないと言ってみませんか?
要素の数（100）がわかっているため、100番目のノードにはnullポインターが含まれている必要があります。その場合、ある程度の確率でリストが有効になります（たとえば、99番目のノードが破損していて、すべてゼロのメモリ位置を指している場合、これは保証されません）。そうでなければ、いくつかの問題があります（これは事実として返される可能性があります）。
upd：また、すべてのステップでdelete、ポインターが与えられた場合に使用するいくつかの構造を調べることも可能ですが、deleteそれ自体を使用することは決して安全ではないため、これは実装固有になります。