構造体について
自己参照構造体
構造体にもアドレスがありますが、このアドレス自体を自身の構造体のメンバに持っているものを自己参照構造体と呼びます。これは、構造体のデータ同士に関係性がある場合に使用されることが多いです。
複数のデータがあり、ある条件を満たすものと関係性を示すアドレスを構造体のメンバに格納することにより、関係性を一覧化するなど情報の分析を行なうことができます。このようにデータ同士を連携させることをデータチェインと呼び、データがつながった状態になります。Aのデータを参照し、メンバのアドレスを参照するとBのデータにたどり着く、Bのデータを参照し、メンバのアドレスを参照するとCのデータを参照する・・・というように、データを規則性にそって並べることが出来、最終的にそれを一つ一つ辿っていくことにより、規則性に従って整理されたデータ群になるのです。
インプットとなるデータ自体の並び替えは行われず、次に繋がるべきデータのアドレスを示しているため、インプットデータを変更することなく実行結果ではソートされた形で処理を行うことが可能なのです。
これを使わずに実現しようとすると、構造体分の作業領域を確保する必要があり、実際にデータの入れ替えを行なう必要があるため処理に時間がかかる上、メモリを多く使用します。自己参照構造体を使用した場合には、使用する作業領域はアドレスを退避する領域があれば良いため、効率的にソート処理を実現することが可能なのです。