線形データ構造と非線形データ構造の主な違いは、線形データ構造ではデータ要素が順次整理されるのに対し、非線形データ構造ではデータ要素が順次整理されないことである。

データ構造とは、データの検索や利用を効率的に行うためのデータの整理・保存方法のことです。線形データ構造とは、データ要素を次々に整理していく構造である。線形データ構造の構成は、コンピュータのメモリの構成と似ている。非線形データ構造とは、あるデータ要素に他のデータ要素をくっつけることで、それらの間に特定の関係を反映させたものである。非線形データ構造の組織は、コンピュータのメモリとは異なる。

カタログ

1. 概要と主な相違点 2. 線形データ構造とは 3. 非線形データ構造とは 4. 並置比較 - 線形データ構造と非線形データ構造の表形式 5. まとめ

リニアデータ構造は何ですか？

線形データ構造は、データ要素を線形に整理し、各データ要素を次々に結合していくものである。線形データ構造では、データ要素は次々に走査され、走査時に直接到達できるのは1つの要素だけである。また、コンピュータのメモリの構成も線形であるため、線形データ構造の実装は非常に容易である。

図01：スタックデータ構造

一般的な線形データ構造には、配列、連鎖したテーブル、スタック、キューなどがあります。まず、配列とは同じ型のデータ要素の集まりのことです。インデックスは、配列内の各要素を識別するのに役立ちます。次に、リンクテーブルはノードの列であり、各ノードはデータ要素と次のノードへの参照で構成される。第三に、スタックも線形データ構造である。データエレメントはリストの先頭からしか追加・削除できません。第四に、キューはリストでもある。これにより、リストの一方の端からデータ要素を追加し、もう一方の端からデータ要素を削除することができます。

非線形データ構造は何ですか？

非線形データ構造では、データ要素は順次に整理されることはない。非線形データ構造のデータ項目は、他のいくつかのデータ要素に添付して、それらの間の特別な関係を反映させることが可能である。さらに、これらの項目を1回の走行で踏破することは不可能です。

図02：ツリーのデータ構造

木やグラフのようなデータ構造は、非線形データ構造の一例である。まず、ツリーとは、リンクしたノードの集合からなるデータ構造のことである。データ要素間の階層的な関係を表現することができる。第二に、グラフは有限個の辺と頂点からなるデータ構造である。頂点はデータ要素を格納し、エッジは頂点間の接続や関係を表す。

リニアと非線形データ構造(Non-linear)の違い

線形データ構造は、データ要素を順次に整理したもので、線形データ構造内を1回の実行で走査することができる。また、リニア構造は実装が非常に簡単です。線形データ構造の例として、配列、スタック、キュー、連鎖テーブルなどがあります。

非線形データ構造は、データを順次に整理しないため、非線形データ構造内のデータ要素を一度に走査することはできない。また、非線形データ構造の実装が困難である。木やグラフは、非線形データ構造の一例である。

概要 - リニア vs. 非線形データ構造(Non-linear)

線形データ構造と非線形データ構造の違いは、線形データ構造ではデータ要素が順次に整理されるのに対し、非線形データ構造ではデータ要素が順次に整理されないことである。つまり、線形データ構造は、非線形データ構造よりもコンピュータのメモリに実装しやすいのだ。保存する必要のあるデータ要素間の関係を考慮することで、あるデータ構造のタイプは他のタイプより慎重に選択されるべきです。

引用

1ナカム、ヒル"型付きデータ構造（線形・非線形） ......" LinkedIn SlideShare, 1 Aug. 2016.こちらから購入できます