通信用語の基礎知識 全国のICカードこれひとつ 戻る

通常PC用 / 人気 更新 今日 カテ
自然科学 > 数学 > アルゴリズム > データ構造
連結リスト
辞書:科学用語の基礎知識 算数・数学編 (NMATH)
読み:れんけつリスト
外語: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);
  ...
}
リンク
関連する用語
線型探索
双方向リスト
データ構造

[再検索] [戻る]


通信用語の基礎知識検索システム WDIC Explorer Ver 7.04 (07-Mar-2021)
Search System : Copyright © Mirai corporation
Dictionary : Copyright © WDIC Creators club
KisoDic