通信用語の基礎知識 IPv4
戻る
参加者募集中

連結リスト

辞書:科学用語の基礎知識 算数・数学編 (NMATH)
読み:れんけつリスト
外語:linked list 英語
品詞:名詞
2002/07/31 作成
2014/07/18 更新

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

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

目的のデータを探す時には基本的には線型探索しか使えず、データがソートされていたとしても常に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);
  ...
}
関連する用語
線型探索
双方向リスト
データ構造

コメントなどを投稿するフォームは、日本語対応時のみ表示されます


KisoDic通信用語の基礎知識検索システム WDIC Explorer Version 7.03 (16-May-2019)
Search System : Copyright © Mirai corporation
Dictionary : Copyright © WDIC Creators club