連結リスト
(線形リスト から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/01/19 01:20 UTC 版)
一連のノードが、任意のデータフィールド群を持ち、1つか2つの参照（リンク）により次（および前）のノードを指している。連結リストの主な利点は、リスト上のノードを様々な順番で検索可能な点である。連結リストは自己参照型のデータ型であり、同じデータ型の別のノードへのリンク（またはポインタ）を含んでいる。連結リストは場所が分かっていれば、ノードの挿入や削除を定数時間で行うことができる（場所を探すのにかかる時間はリスト上の順番の条件などにも依存するし、後述する片方向リストなのか双方向リストなのかにも依存する）。連結リストにはいくつかの種類があり、片方向リスト、双方向リスト、線形リスト、循環リストなどがある。
連結リストは多くのプログラミング言語で実装可能である。LISP や Scheme 、Prologといった言語は組み込みでこのデータ構造を持っていて、連結リストにアクセスするための操作も組み込まれている。
歴史
線形リストは、1955年から1956年ごろ、ランド研究所にてアレン・ニューウェル、Cliff Shaw、ハーバート・サイモンが Information Processing Language (IPL) の主要データ構造として開発したのが最初である。IPL はいくつかの初期の人工知能プログラム（General Problem Solver など）で使われた。線形リストを箱と矢印で表すという今ではお馴染みの記法は、1957年2月の "Proceedings of the Western Joint Computer Conference" に掲載されたニューウェルと Shaw の "Programming the Logic Theory Machine" という論文で使われている。ニューウェルとサイモンは1975年、「人工知能、認知心理学、リスト処理の基盤を築いた」ことに対してチューリング賞を受賞した。
マサチューセッツ工科大学 (MIT) の Victor Yngve は、自然言語処理、特に機械翻訳向けに開発した COMIT という言語学向けのプログラミング言語で線形リストをデータ構造として使っている。これに関する論文は1958年、"Mechanical Translation" に "A programming language for mechanical translation" と題して掲載された。
1960年、ジョン・マッカーシー等が MIT で開発したLISPは "list processor" の略であり、"Communications of the ACM" にその設計に関する論文 "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I" が掲載された[1]。LISP の主要なデータ構造の一つとして片方向リストによる木構造が採用されている[2]。
1960年代初期までに、線形リストやそれを基本的なデータ構造とする言語が一般化した。MIT リンカーン研究所の Bert Green は1961年3月、"IRE Transactions on Human Factors in Electronics" に "Computer languages for symbol manipulation" という論文を書き、線形リストを使った手法の利点をまとめている。同様の論文は1964年4月、Communications of the ACM に Bobrow と Raphael の "A Comparison of list-processing computer languages" が掲載されている。
Technical Systems Consultants (TSC) 社は、片方向リストをファイル構造に利用したオペレーティングシステム FLEXを開発した。ディレクトリがファイルの第一セクターを指し、その後のファイルの中身も線形リストのポインタを辿ることで得られるようになっていた。FLEX から派生したオペレーティングシステムとして Smoke Signal Broadcasting社が開発したものがあるが、こちらは双方向リストを同じ用途に使っていた。
IBM社が System/360やSystem/370向けに開発したTSSでも、ファイルシステムに双方向リストを使っていた。そのディレクトリ構造は UNIX のものと似ており、ディレクトリはファイルや他のディレクトリを格納でき、任意の深さまで階層構造を作ることができた。システムがクラッシュしたとき、このファイルシステム構造の一部がディスクに書き戻されていない場合があり、これを修復するためのユーティリティ "flea" が開発された。これは双方リストの前方リンクと後方リンクの一貫性をチェックすることで問題を検出する。
種類
線形リスト
線形リストには、片方向リストと双方向リストがあり、どちらも任意の位置でデータの追加・削除が"O(1)"時間でできるのが特長である。しかし、ソートされた配列や木構造と違い、データの検索はO(n)時間かかってしまうという欠点がある（ソートされていない配列は線形リストと同じ"O(n)"の検索時間である）。
片方向リスト
片方向リスト（singly-linked list）は、最も単純な連結リストであり、ノード毎に1つのリンクを持つ。このリンクはリスト上の次のノードを指し、リストの最後尾ならNull値を格納するか、空のリストを指す。
3つの整数値を格納した片方向リスト
双方向リスト
双方向リスト（doubly-linked list）は、より洗練された連結リスト。各ノードには2つのリンクがあり、1つが次のノード（前方リンク）、もう1つが後ろのノード（後方リンク）を指す。リストの先頭のノードには後ろのノードがないので、後方リンクにはヌル値を格納するか、空のリストを指す。リストの最後尾のノードには次のノードがないので、前方リンクにはヌル値を格納するか、空のリストを指す。
3つの整数値を格納した双方向リスト
低レベルの言語の中には、XOR連結リストを使って双方向リストの2つのリンクを1つのワードで表せるようにしたものもあるが、この技法は一般には使われない。
循環リスト
循環リスト（circularly-linked list）では、先頭と最後尾のノードを相互に連結する。循環リストには片方向のものも双方向のものもある。循環リストを辿る場合、任意のノードから出発して、好きな方向にたどっていき、最初のノードに戻ってくるまで続ける。つまり、循環リストは先頭や最後尾といったものが存在しないリストと考えることもできる。循環リストはデータ格納用バッファの管理によく使われ、1つのノードを使っているスレッド（やプロセス）が他のノードを全て参照したい場合などに便利である。
リスト全体を指すポインタは、アクセスポインタと呼ばれることがある。
3つの整数値を格納した循環リスト
片方向循環リスト
片方向循環リスト（singly-circularly-linked list）では、各ノードは線形の片方向リストと同じように1つのリンクを持つが、最後尾のノードは先頭のノードをリンクしている。片方向リストと同様、新たなノードを挿入する場合、既に参照を持っているノードの次の位置にのみ挿入できる。このため、片方向循環リストでは、最後尾のノードを指している参照を保持しておくことが多く、それによって、先頭位置に高速に挿入可能とするだけでなく、先頭ノードから最後尾のノードまでを順に辿ることも可能にしている。 [3]
双方向循環リスト
双方向循環リスト（doubly-circularly-linked list）では、各ノードは線形の双方向リストと同じように2つのリンクを持つが、先頭ノードの後方リンクは最後尾ノードを指し、最後尾ノードの前方リンクは先頭ノードを指す。双方向リストと同様、挿入も削除もその位置に隣接するノードへの参照が1つあれば、高速に行える。構造的には双方向循環リストには先頭も最後尾もないが、一般に外部のアクセスポインタを用意して、先頭または最後尾のノードを指しておくことが多い。そして、双方向リストでの番兵ノードのように順序を把握するのに使われる[3]。
番兵ノード
線形リストには「ダミーノード」または「番兵ノード; sentinel node」と呼ばれるものが、リストの先頭や最後尾に置かれることがある。番兵ノードにはデータは格納されない。その目的は、全てのノードのリンクが常にノードのデータ構造を指していることを保証して、いくつかの操作を高速化することである。LISPではそのような設計がされており、nil と呼ばれる特別な値は片方向リストの最後尾を示すと決められている。nil は CAR 操作でも CDR 操作でも nil を返すため、一部の操作を高速化できる。最後尾が nil でないリストは不適切（improper）である（不適切とは言っても使えないということではない）。
応用
連結リストは他のデータ構造の構成要素として使われる。例えば、スタック、キューなどである。
ノードのデータ部が別の連結リスト（へのポインタ）という構成も可能である。これを応用すると様々なデータ構造をリストで構成できる。これはLISPを起源とする方法であり、LISP では連結リストは主要なデータ構造とされ、今では関数型言語で一般に使われている。
連結リストを使って連想配列を実装することもあり、これを連想リスト（association list）と呼ぶ。このような連結リストの応用にはあまり利点がない。平衡2分探索木などのデータ構造の方が、ごく小さいデータ量であっても性能的に優れている。しかし、木構造のサブセットという範囲を超えて連結リストを動的に生成することもあり、より効率的にそのような構成のデータを扱うのに使われる。
トレードオフ
コンピュータプログラミングと設計におけるほとんどの選択と同様、あらゆる状況に適した方法は存在しない。連結リストというデータ構造も状況によってはうまく機能するが、別の状況には適さない。以下では、連結リスト構造に関するトレードオフについて説明する。一般に動的に変化するデータの集まりがあって、要素の追加・削除が頻繁に行われ、新たな要素を追加する位置が重要となる場合、連結リストが適しているといえる。
連結リストと配列
| 配列 | 連結リスト | |
|---|---|---|
| 検索 | O(1) | O(n) |
| 最後尾での挿入/削除 | O(1) | O(1) or O(n)[4] |
| 途中での挿入/削除（位置指定あり） | O(n) | O(1) |
| 永続性 | なし | 片方向で有り |
| 局所性 | 大 | 小 |
連結リストは配列と比較したとき、いくつかの利点を持つ。リストでは要素の挿入は無制限に可能であるが、配列はサイズが決まっているために限界があり、配列を大きくしようとしても、メモリのフラグメンテーションによって不可能なこともある。同様に、配列から要素の多くを削除すると領域の無駄となったり、サイズを小さくする必要が生じる。
複数のリストが尾部を共有することで、さらにメモリを節約できる場合もある。つまり、先頭が複数あって、末尾が1つになっている構造が可能である。これを使って、何らかのデータの古いバージョンと新しいバージョンを同時に保持することが可能であり、簡単な永続データ構造の例となっている。
一方、配列はランダムアクセス性に優れており、連結リストがシーケンシャルアクセスを得意とするのと対照的である。片方向リストは一方向にしか辿れない。従って、ヒープソートのようにインデックスによって高速に要素を参照する必要がある場合、連結リストは不向きである。シーケンシャルアクセスも多くのマシン上では、連結リストよりも配列の方が高速である。これは、キャッシュメモリの効果と参照の局所性によるものである。連結リストはキャッシュメモリからはほとんど何も恩恵を受けない。
連結リストの別の欠点は、参照のための余分な領域を必要とする点である。このため、キャラクタやブーリアン型のような小さなデータ要素を連結リストで操作するのは（1文字ごとにノードを割り当てて文字列操作を実現するなど）、速度の面でもメモリ消費の面でも無駄が多く、現実的でない。
これらの問題の一部を改善する連結リストの派生データ構造がいくつか存在する。Unrolled linked list は各ノードに複数の要素を格納するもので、キャッシュ性能を向上させ、参照時のメモリのオーバヘッドを低減させる。CDRコーディングも参照を参照すべき実データと置換することで同様の効果が得られる。
配列との比較で利点と欠点を明確にする好例として、ジョセファスの問題を解くプログラムの実装がある。ジョセファスの問題とは、人間が輪になって並んでいる状況で、そこから1人を選ぶというものである。ある人を開始点として、特定の方向に n 人を数えていく。n 番目の人に到達したら、その人を輪から外して、残りの人間で一回り小さい輪を作る。そして再び n 番目まで数えていく。これを1人だけが残るまで繰り返し、最後に残った人が選ばれた人ということになる。これを循環リストを使って表すのは直接的で分かり易いし、ノードの削除も簡単である。しかし、循環リストでは、現在のノードから n 番目のノードを見つけるには、リストを順に辿っていくしかない。配列であればインデックスの計算で即座に見つけられる。一方、配列では要素（ノード）の削除は容易ではなく、n 番目のノードを即座に見つけるという利点を生かすには、ノードを削除したときに残った要素を詰めてやる必要がある。
双方向と片方向
双方向リストはノード毎に要するメモリ量が多くなるし、基本的な操作にかかる手間が多くなる。しかし、どちらの方向にもシーケンシャルアクセス可能であるため、扱いやすくなることが多い。特に、あるノードの削除をする場合、そのノードのアドレスさえ分かっていれば、定数時間でそれが可能である。挿入の場合も、挿入する位置（そのノードの前に新たなノードを挿入する）が判っていれば、双方向リストでは定数時間で挿入が可能である。片方向リストでは、挿入・削除の際に1つ前のノードのアドレスも知る必要がある。アルゴリズムによっては双方向のアクセスが必須な場合もある。一方、双方向リストでは尾部の共有はできないので、永続データ構造としては使えない。
循環と線形
循環リストは、本質的に環状の構造を表すのに適している。また、どのノードからでもリスト全体をたどることが可能である。また、（最後尾のノードを指す）ポインタを1つ保持しておけば、先頭と最後尾を同時に効率的にアクセス可能である。主な欠点は、繰り返し処理をする際に、微妙に複雑な配慮を要する点である。
番兵ノード
番兵ノードを使えば、全てのノードに次のノードや前のノードが存在することを保証でき、特定のリスト操作を単純化できる。しかし、（特に小さなリストを多数使用する場合）余分な領域を必要とするという欠点があり、他のリスト操作は逆に複雑化する。余分な領域を消費するのを防ぐため、番兵ノードはリストの先頭あるいは最後尾のノードへの参照として再利用されることがある。
連結リストの操作
連結リストを操作する場合、無効化され使われなくなった値の扱いに注意する必要がある。そのため、連結リストでの挿入・削除のアルゴリズムはある意味で巧妙である。ここでは、片方向リスト、双方向リスト、循環リストでのノードの追加と削除に関する擬似コードを示す。リストの終端を表すマーカー（あるいは番兵）としては "null" を使うが、その実装は様々なものが考えられる。
線形リスト
片方向リスト
ここでのノードのデータ構造には2つのフィールドがある。また、List の "firstNode" というフィールドがリストの先頭ノード（空のリストの場合は "null"）を指すとする。
record Node {
data // ノードに格納されるデータ
next // 次のノードへの参照（最後尾の場合は null）
}
record List {
Node firstNode // リストの先頭ノードを指す（空のリストの場合は null）
}
片方向リストを辿るのは単純で、先頭ノードから各ノードの "next" リンクを最後まで辿っていく。
node := list.firstNode
while node ≠ null {
(node.data に何かをする)
node := node.next
}
次のコードは片方向リスト上のあるノードの次に新たにノードを挿入する。あるノードの前にノードを挿入することはできない。その場合は挿入位置の前のノードを見つける必要がある。
function insertAfter(Node node, Node newNode) { // newNode を node の次に挿入
newNode.next := node.next
node.next := newNode
}
リストの先頭にノードを追加する場合、別の関数が必要である。この場合、firstNode を更新しなければならない。
function insertBeginning(List list, Node newNode) { // 現在の先頭ノードの前にノードを挿入
newNode.next := list.firstNode
list.firstNode := newNode
}
同様に、指定されたノードの次のノードを削除する関数と、リストの先頭のノードを削除する関数を示す。特定のノードを探して削除する場合、その前のノードを覚えておく必要がある。
function removeAfter(Node node) { // このノードの次のノードを削除
obsoleteNode := node.next
node.next := node.next.next
destroy obsoleteNode
}
function removeBeginning(List list) { // 先頭ノードを削除
obsoleteNode := list.firstNode
list.firstNode := list.firstNode.next // 削除されるノードの次を指す
destroy obsoleteNode
}
removeBeginning() は、削除するノードが最後のノードだった場合、"list.firstNode" を "null" にする。
逆方向に繰り返すことができないので、"insertBefore" や "removeBefore" といった操作を効率的に実装することはできない。
2つの片方向リストを連結したい場合、リストの最後尾を常に保持していないと効率的に処理できない。2つのリストがそれぞれ長さ 
連結リストを構築する際、データをノードそのものに格納するか、別のデータ構造への参照のみを格納するかという選択を迫られる。前者を「内部収納; internal storage[要出典]」、後者を「 外部収納; external storage[要出典]」と呼ぶ。内部収納の方がデータアクセスが効率化され、全体としてメモリ使用量が低減され、参照の局所性が向上し、リストに関するメモリ管理も簡素化される（データはノードと共に確保・解放される）。
一方、外部収納はより汎用的だという利点がある。データの内容に依存しないデータ構造とリスト操作コードを形成可能である。また、複数のノードで同じデータを共有することも容易に実現できる。内部収納の場合も、通常のリンクとは別に、同じ内容のデータを保持するノードを連結するフィールドを持てば、同様のことが可能になるが、リスト操作にあたってそれも考慮する必要が出てくる。
一般に、データ構造を複数の連結リストに属させる必要がある場合、外部収納が最善の手法である。データ構造が1つの連結リストにしか属さない場合、内部収納の方が若干良いが、外部収納の汎用リスト操作パッケージが利用可能なら、それを利用するほうがよい場合もある。
いくつかの言語で採用されている別の手法として、いくつかの種類のデータ構造があって、それらの先頭部分の同じ位置にリストのための "next" および "prev" のフィールドが存在する場合がある。この場合、リスト操作は汎用的なルーチンを使い、個々のノード内のデータは個別のルーチンで処理する。様々な種類のメッセージを受信する際の構文解析などでよく使われる。メッセージのキューへの追加と削除は汎用的なルーチンで行われる。メッセージの種類がメッセージの先頭にあり、それを見て適切なメッセージ処理ルーチンを呼び出す。
内部収納と外部収納の例
ここでは、家族とその構成員の連結リストを処理するコードを例として示す。内部収納の場合、構造体は次のようになる。
record member { // 家族のメンバー
member next
string firstName
integer age
}
record family { // 家族
family next
string lastName
string address
member members // この家族のメンバーのリストの先頭
}
家族のリストと各家族のメンバーを表示するルーチンは、内部収納の場合、次のようになる。
aFamily := Families // 家族リストの先頭から開始
while aFamily ≠ null { // 家族リスト上でループ
家族に関する情報を印字
aMember := aFamily.members // その家族のメンバーのリストの先頭を得る
while aMember ≠ null { // メンバーのリスト上でループ
メンバーに関する情報を印字
aMember := aMember.next
}
aFamily := aFamily.next
}
外部収納を使うと、構造体は次のようになる。
record node { // 汎用リンク構造体
node next
pointer data // ノードに付属するデータを指す汎用ポインタ
}
record member { // 家族構成員に関する構造体
string firstName
integer age
}
record family { // 家族に関する構造体
string lastName
string address
node members // この家族のメンバーのリストの先頭
}
家族のリストと各家族のメンバーを表示するルーチンは、外部収納の場合、次のようになる。
famNode := Families // 家族リストの先頭から開始
while famNode ≠ null { // 家族リスト上でループ
aFamily = (family)famNode.data // ノードから家族データ構造体を取り出す
家族に関する情報を印字
memNode := aFamily.members // その家族のメンバーのリストの先頭を得る
while memNode ≠ null { // メンバーのリスト上でループ
aMember := (member)memNode.data // ノードからメンバーデータ構造体を取り出す
メンバーに関する情報を印字
memNode := memNode.next
}
famNode := famNode.next
}
外部収納を使った場合、データ構造体を取り出して型変換するという余分なステップが必要になる。これは、2種類の連結リストが同じデータ構造（node）を使っているためである。
あるメンバーがいくつの家族に属することができるかがコンパイル時に分かっている場合、内部収納の方が適している。しかし、1人のメンバーが任意の個数の家族に属する可能性がある場合、かつその数が実行時にならないと分からない場合、外部収納にする必要がある。
検索の高速化
連結リストで特定の要素を探す場合、たとえそれがソート済みであっても一般に O(n) の時間を要する（線型探索）。これは連結リストの重大な欠点である。これを改善するいくつかの方法が存在する。
ソートされていないリストでは、平均検索時間を短縮する単純なヒューリスティックとして "Move To Front" と呼ばれる手法がある。これは、1度検索して見つかったノードをリストの先頭に移動させるという方式である。これは一種の簡単なキャッシュ構成法であり、最も後に検索したノードを再度検索する場合に高速化される。
もう1つの一般的な手法は、より効率的な外部のデータ構造を使ってノードにインデックスを付けるというものである。例えば、赤黒木やハッシュテーブルを構築し、その要素が連結リストの各ノードへの参照を持つようにする。1つのリストに対して、そのようなインデックスを複数構築できる。この手法の欠点は、ノードの追加や削除の度にインデックス側の更新が必要となる点である。少なくともインデックスを再利用する前に更新が必要である。
関連するデータ構造
- スタックとキューは連結リストを使って実装されることが多く、単にリストで許されている操作を制限するだけでよい。
- スキップリストは、ポインタが階層化された連結リストであり、多数のノードを高速に飛ばして検索可能である。
- 二分木は、データ部も同じような連結リストへのリンクになっている連結リストと見なすこともできる。各ノードは2つのノードへのリンクになっており、それぞれが部分木の頂点を指している。
- unrolled linked list は、各ノードに配列が置かれている形式の連結リストである。主に参照の局所性を高め、性能を向上させる目的で使われる。
- ハッシュテーブルは、ハッシュ値が衝突しているデータを保持する際に連結リストの構造を使うことがある。
特許問題
- Linked List Patented in 2006 (Slashdot)
- リンクトリストが2006年に特許承認 (スラッシュドット ジャパン)
 |
この節の加筆が望まれています。
|
脚注
- ^ “RECURSIVE FUNCTIONS OF SYMBOLIC EXPRESSIONS AND THEIR COMPUTATION BY MACHINE (Part I) (12-May-1998)”. www-formal.stanford.edu. 7 April 2024閲覧。
- ^ “McCarthy et al. LISP I Programmer's Manual. — Software Preservation Group”. softwarepreservation.org. 7 April 2024閲覧。
- ^ a b Preiss, Bruno R. (1999年), Data Structures and Algorithms with Object-Oriented Design Patterns in Java, Wiley, p. page 97, 165, ISBN 0471-34613-6
- ^ 最後尾へのリンクを保持していれば O(1) だが、最後尾を探すために先頭から辿る必要がある場合は O(n)
参考文献
- Antonakos, James L. and Mansfield, Kenneth C., Jr. Practical Data Structures Using C/C++ (1999). Prentice-Hall. ISBN 0-13-280843-9, pp. 165–190
- Collins, William J. Data Structures and the Java Collections Framework (2002,2005) New York, NY: McGraw Hill. ISBN 0-07-282379-8, pp. 239–303
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford Introductions to Algorithms (2003). MIT Press. ISBN 0-262-03293-7, pp. 205–213, 501–505
- Green, Bert F. Jr. (1961). Computer Languages for Symbol Manipulation. IRE Transactions on Human Factors in Electronics. 2 pp. 3-8.
- McCarthy, John (1960). Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. Communications of the ACM. [1] HTML DVI PDF PostScript
- Donald Knuth. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Sections 2.2.3–2.2.5, pp.254–298.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 10.2: Linked lists, pp.204–209.
- Newell, Allen and Shaw, F. C. (1957). Programming the Logic Theory Machine. Proceedings of the Western Joint Computer Conference. pp. 230-240.
- Parlante, Nick (2001). Linked list basics. Stanford University. PDF
- Sedgewick, Robert Algorithms in C (1998). Addison Wesley. ISBN 0-201-31452-5, pp. 90–109
- Shaffer, Clifford A. A Practical Introduction to Data Structures and Algorithm Analysis (1998). NJ: Prentice Hall. ISBN 0-13-660911-2, pp. 77–102
- Wilkes, Maurice Vincent (1964). An Experiment with a Self-compiling Compiler for a Simple List-Processing Language. Annual Review in Automatic Programming 4, 1. Published by Pergamon Press.
- Wilkes, Maurice Vincent (1964). Lists and Why They are Useful. Proceeds of the ACM National Conference, Philadelphia 1964 (ACM Publication P-64 page F1-1); Also Computer Journal 7, 278 (1965).
- Kulesh Shanmugasundaram （2005年4月4日）. Linux Kernel Linked List Explained.
関連項目
外部リンク
- Description Dictionary of Algorithms and Data Structures より
- スタンフォード大学 計算機科学科:
- SimCList, an open source C library for linked lists
- SGLib, an collection of algorithms for operating on linked lists (and other containers)
- Generic List Container Type for ANSI C by Jeff Hay
- shared singly linked list implementations
- Linked Lists Tutorial with diagrams and Java code example
- 各ノードが複数の線形リストに同時に属するという技法に関する特許 （この技法はこの特許が成立する何十年も前から広く使われていた）
|
|
|||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| その他 | |||||||||||||||||
| 配列構造(英) | |||||||||||||||||
| リンク構造(英) | |||||||||||||||||
| 検索構造(英) |
|
||||||||||||||||
| 木構造 |
|
||||||||||||||||
| グラフ構造 | |||||||||||||||||
| 抽象データ型 | |||||||||||||||||
| 典拠管理データベース: 国立図書館 |
|---|
線形リスト
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/29 20:30 UTC 版)
線形リストには、片方向リストと双方向リストがあり、どちらも任意の位置でデータの追加・削除が"O(1)"時間でできるのが特長である。しかし、ソートされた配列や木構造と違い、データの検索はO(n)時間かかってしまうという欠点がある（ソートされていない配列は線形リストと同じ"O(n)"の検索時間である）。
※この「線形リスト」の解説は、「連結リスト」の解説の一部です。
「線形リスト」を含む「連結リスト」の記事については、「連結リスト」の概要を参照ください。
- 線形リストのページへのリンク
