|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 連 ： [むらじ, れん] 【名詞】 1. party 2. company 3. group ・ 連結 ： [れんけつ] 1. (n,vs) concatenation 2. coupling 3. connection
連結リスト（れんけつリスト、）は、最も基本的なデータ構造の1つであり、他のデータ構造の実装に使われる。リンクリスト、リンクトリストとも表記される。 一連のノードが、任意のデータフィールド群を持ち、1つか2つの参照（リンク）により次（および前）のノードを指している。連結リストの主な利点は、リスト上のノードを様々な順番で検索可能な点である。連結リストは自己参照型のデータ型であり、同じデータ型の別のノードへのリンク（またはポインタ）を含んでいる。連結リストは場所が分かっていれば、ノードの挿入や削除を定数時間で行うことができる（場所を探すのにかかる時間はリスト上の順番の条件などにも依存するし、後述する片方向リストなのか双方向リストなのかにも依存する）。連結リストにはいくつかの種類があり、片方向リスト、双方向リスト、線形リスト、循環リストなどがある。 連結リストは多くのプログラミング言語で実装可能である。LISP や Scheme 、Prologといった言語は組み込みでこのデータ構造を持っていて、連結リストにアクセスするための操作も組み込まれている。手続き型やオブジェクト指向型の言語（C言語、C++、Java）では、連結リストを作るには mutable（更新可能）な参照を必要とする。 == 歴史 == 線形リストは、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" と題して掲載された。 1958年、ジョン・マッカーシーが MIT で開発したLISPは "list processor" の略であり、1960年に "Communications of the ACM" にその設計に関する論文 "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I" が掲載された。LISP の主要なデータ構造の一つとして線形リストが採用されている。 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" が開発された。これは双方リストの前方リンクと後方リンクの一貫性をチェックすることで問題を検出する。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「連結リスト」の詳細全文を読む スポンサード リンク
|