- 475 名前：デフォルトの名無しさん [2021/11/28(日) 18:32:54.89 ID:Izo/gJUY.net]
- >>463
>＞リンクリストで、一度作成したノードのアドレスはずっと保存する
>って、どこにどういう形で保存するのです？
・リンクリスト全体のノードを辿ればいい場合には保存する必要が無い。
なお、その場合、1ノード右側のノードのアドレスを取得するのは1〜2クロック
しかかからない。
・例えば、1000個のノードが入っている場合の、特定の 2 個のポインタを
保存したい場合には、グローバル変数の2つのポインタにそれぞれの
アドレスを代入しておけばよい。
それは丁度、ArrayList(vector)の場合であれば、添え字番号を2つの整数
変数に代入しておくのと全く同じこと。
・要は、ノードを識別するための数値が、配列では整数型の添え字番号であったところが、
リンクリストでは、ポインタ型のアドレスになるというだけのこと。
決して後者に置いては、通し番号を使ってはいけない。
数学的には、次のような双対関係の様なものが存在していると考えられる:
（配列, 添え字) <---> (リンクリスト, アドレス)
QZを含めて、この双対関係を理解できておらず、
（配列, 添え字) <---> (リンクリスト, 添え字)
と間違って理解してしまっている人が多いことから、リンクリストでのランダムアクセス
が O(N)などと謝った認識に至ってしまう人が多いと考えられる。
しかし、正しく双対関係を理解すれば、O(1)であることが理解できよう。
|
 |
