連結リスト
読み：れんけつリスト
外語：linked list
データ構造の一つ。各要素にデータと次のリストを指し示すためのポインターが格納されており、ポインターの情報を元にデータの関連が表現されるもの。
概要
単にリストと呼ばれることが多い。
目的のデータを探す時には基本的には線型探索しか使えず、データがソートされていたとしても常にO(n)の時間を要するという欠点があるが、データの削除、追加はポインターの変更だけで済むため手間がかからず高速である。
このためリスト操作は頻繁に使われており、Linuxでは車輪の再発明を防ぐ目的で、ユーティリティ関数としてリスト操作機能を提供している。
実装
主な実装
struct list_head
実装方法はいくつかあるが、Linuxの実装では、list_headという構造体を用意している。Cで簡単に使うことができる。
struct list_headの中身は、struct list_head自身に対するprev/nextの2つのポインターで、線型探索に必要な最低限の要素である。リストごとにstruct list_head構造体を一つstaticで用意し、さらに、各構造体の要素にstruct list_headを一つ含めておけば、機能が利用できる。
関数群では、リストに加えたり、リストから削除したりといった基本的な処理が用意されている。用例は次の通り。
static LIST_HEAD (example_head);
static void example_in (example_t *t)
{
list_add_tail (&t->list, &example_head);
}
順次探索する処理に利便が良いように、list_for_eachなどのマクロが用意されている。
struct list_head *p;
example_t *t;
list_for_each (p, &example_head)
{
t = list_entry (p, example_t, list);
...
}
再検索