データ構造の一つ。各要素にデータと次のリストを指し示すためのポインターが格納されており、ポインターの情報を元にデータの関連が表現されるもの。

目次 概要 実装 主な実装 struct list_head

概要

単にリストと呼ばれることが多い。

目的のデータを探す時には基本的には線型探索しか使えず、データがソートされていたとしても常にO(n)の時間を要するという欠点があるが、データの削除、追加はポインターの変更だけで済むため手間がかからず高速である。

このためリスト操作は頻繁に使われており、Linuxでは車輪の再発明を防ぐ目的で、ユーティリティ関数としてリスト操作機能を提供している。

実装

主な実装

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

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);
  ...
}

リンク

関連する用語
線型探索
双方向リスト
データ構造

[再検索] [戻る]