はじめての C

lang

「リンクリスト 9」

リストインデックスは、リンクリストや 配列のための 最善の 方法です。

リストでの 挿入や 削除、配列の 検索が 容易に できます。

もちろん、リストインデックスを 使って 効率的に 動かす コードを 得るには、多くの 役に たたない コードを 除くことも そうですが、いくらか 手間が かかります。しかし、それは とても 役に たつものに なります。

リストインデックスの 作成には、リストに どれだけの 項目が あるのかを 知る 必要が あります。

そこで、項目の ポインタに 動的な - dynamic - 配列を 割り当てて、各項目を 新しい 配列に 加えながら リストを たどっていきます。

簡単な 実装コードの 一例 ▽

Element *make_index(List list, int *n)
{
Element item;
Element *index:
int count;

count = 0;
for (item = list, item != NULL; item = item->next)
count++;
*n = count;
index = malloc(count * sizeof(*index));
count = 0;
for (item = list; item != NULL; item = item->next)
index[count++] = item;

return index;
}

注意する点は、リストの 頻繁な 変更によって、index が expensive な ものに なることです。

index の 更新では、リストと malloc の 呼び出し という 2つの traversal が 求められます。

それと、もし 効率面ばかりに 目が いき、定期的に リスト変更時の index の 更新を 行わなかったら、結局は、現在 必要とする リストでは なくて、古いほうの リストを index してしまう という 問題が 起こることに なります。

慎重に このトリックは 使用すること、ですね。