翻訳と辞書
Words near each other
・ 線収縮
・ 線名
・ 線吸収係数
・ 線図
・ 線固定
・ 線型
・ 線型システム論
・ 線型ディオファントス方程式
・ 線型ノルム空間
・ 線型ブロック符号
線型リスト
・ 線型代数
・ 線型代数学
・ 線型代数学の基本定理
・ 線型代数学用語一覧
・ 線型位相空間
・ 線型作用素
・ 線型写像
・ 線型分離可能
・ 線型分類器


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

線型リスト : ミニ英和和英辞書
線型リスト[かた]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

: [かた]
 【名詞】 1. mold 2. mould 3. model 4. style 5. shape 6. data type 

線型リスト ( リダイレクト:連結リスト ) : ウィキペディア日本語版
連結リスト[れんけつりすと]
連結リスト(れんけつリスト、)は、最も基本的なデータ構造の1つであり、他のデータ構造の実装に使われる。リンクリストリンクトリストとも表記される。
一連のノードが、任意のデータフィールド群を持ち、1つか2つの参照(リンク)により次(および前)のノードを指している。連結リストの主な利点は、リスト上のノードを様々な順番で検索可能な点である。連結リストは自己参照型のデータ型であり、同じデータ型の別のノードへのリンク(またはポインタ)を含んでいる。連結リストは場所が分かっていれば、ノードの挿入や削除を定数時間で行うことができる(場所を探すのにかかる時間はリスト上の順番の条件などにも依存するし、後述する片方向リストなのか双方向リストなのかにも依存する)。連結リストにはいくつかの種類があり、片方向リスト双方向リスト線形リスト循環リストなどがある。
連結リストは多くのプログラミング言語で実装可能である。LISPSchemePrologといった言語は組み込みでこのデータ構造を持っていて、連結リストにアクセスするための操作も組み込まれている。手続き型やオブジェクト指向型の言語(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/360System/370向けに開発したTSSでも、ファイルシステムに双方向リストを使っていた。そのディレクトリ構造は UNIX のものと似ており、ディレクトリはファイルや他のディレクトリを格納でき、任意の深さまで階層構造を作ることができた。システムがクラッシュしたとき、このファイルシステム構造の一部がディスクに書き戻されていない場合があり、これを修復するためのユーティリティ "flea" が開発された。これは双方リストの前方リンクと後方リンクの一貫性をチェックすることで問題を検出する。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「連結リスト」の詳細全文を読む

英語版ウィキペディアに対照対訳語「 Linked list 」があります。




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.