はじめての C

「リンクリスト 10」

リンクリストで 用いる テクニックには、おもしろくって 役にたつものが、いくつか あります。

1. 一致する 項目を 捜して その数を かぞえる ▽

int count(List list, int find)
{
int cnt = 0;
while (list != NULL) {
if (list->data == find)
cnt++;
list = list->next;
}
return cnt;
}

2. リストの N番目の 項目を 見つけだす ▽

Element get_nth(List list, int index)
{
int i;
for (i = 0; i < index; i++) {
list = list->next;
if (list == NULL)
return NULL;
}
return list;
}

3. 全リストの 抹消

これは トリッキーな 仕組みで、次の項目に 移動してからでないと、その項目を free できません。

多くの人は 次の やり方で うまくいく、と まちがって 信じています。

void destroy(List list)
{
while (list != NULL) {
free(list);
list = list->next;
}
}

正しい 方法では、ポインタの 保存を 用いることで、開放された メモリに アクセスできなくするのです ▽

void destroy(List list)
{
Element save;
while (list != NULL) {
save = list->next;
free(list);
list = save;
}
}

4. ダブってる (項目を) 削除する ▽

void unique(List list)
{
Element curr = list;
Element save;
/* Empty list */
if (curr == NULL)
return;
while (curr->next != NULL) {
if (curr->data == curr->next->data) {
save = curr->next->next;
free(curr->next);
curr->next = save;
}
else
curr = curr->next;
}
}