|
空でないリストには頭と尾があり、頭が単一の項目で、尾が別のリストであるため、「対称」ではありません。In 式[foo | bar]
foo
はリストの先頭を表し、bar
は末尾です。末尾が適切なリストでない場合、結果も適切なリストにはなりません。ヘッドがリストの場合、結果はそのリストを最初の要素とする単純なリストになります。
リンクされたリストの最後に O(n) 時間未満で追加する方法はありません。これが、++
for that の使用が一般的に敬遠される理由です。リストの最後に追加する特別な構文があったとしても、それでも O(n) 時間かかる必要があり、その構文を使用しても、使用++
するよりも「良いアーランガー」にはなりません。
挿入あたりの O(n) コストを回避したい場合は、前に追加してから逆にする必要があります。コストを支払う意思がある場合は、 を使用することもできます++
。
リストの仕組みについてもう少し詳しく説明します。
[ x | y ]
コンスセルと呼ばれるものです。C の用語では、基本的に 2 つのメンバーを持つ構造体です。適切なリストは、空のリスト ( []
) または 2 番目のメンバーが適切なリストであるコンス セルです (この場合、最初のメンバーはそのヘッドと呼ばれ、2 番目のメンバーはそのテールと呼ばれます)。
したがって、[1, 2, 3]
これを記述すると、次のコンス セルが作成されます[1 | [2 | [3 | []]]]
。つまり、リストは、最初のメンバー (先頭) が 1 で、2 番目のメンバー (末尾) が別のコンス セルであるコンス セルとして表されます。そのもう 1 つのコンス セルは、先頭に 2 を持ち、さらにもう 1 つのコンス セルを末尾に持っています。そのセルには、先頭に 3 があり、末尾に空のリストがあります。
このようなリストのトラバースは、最初にリストの先頭に作用し、次にリストの末尾でトラバーサル関数を呼び出すことによって再帰的に行われます。
そのリストの先頭に項目を追加したい場合、これは非常に簡単です。頭が新しい項目で、末尾が古いリストである別のコンス セルを作成するだけです。
ただし、単一のコンス セルを作成するだけでは十分でないため、アイテムの追加ははるかにコストがかかります。古いものと同じリストを作成する必要がありますが、最後のコンス セルの末尾は、先頭が新しい要素で末尾が空のリストである新しいコンス セルでなければなりません。したがって、O(n) であるリスト全体を調べずにリストに追加することはできません。