連結リスト

• list_head (LinuxほかPC UNIX、Cからも利用可能)
• listnode (Androidの実装で、list_headとほぼ同様)
• std::list (C++のSTL)

実装方法はいくつかあるが、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);
  ...
}