線形データ構造と非線形データ構造の違い

2019

データ構造は、データの孤立要素間に存在する論理関係の解釈として定義できます。線形および非線形データ構造は、Non-primitiveデータ構造の下に来るデータ構造の下位分類です。それらの間の重大な違いは、線形データ構造がデータをシーケンスに配列し、そしてある種の順序に従うということです。一方、非線形データ構造は、データを順次に編成しません。

線形データ構造はシングルレベルデータ構造であり、非線形データ構造はマルチレベルデータ構造である。データ構造は、データがどのように編成され、アクセスされ、関連付けられ、そして処理されるかを先に説明している。

比較表

比較基準	線形データ構造	非線形データ構造
基本	データ項目は、要素が隣接して結合されるように規則正しく並べられています。	それはソートされた順序でデータを配置し、データ要素間に関係があります。
データの移動	データ要素は一度にアクセスできます（シングルラン）。	一度にデータ要素を移動することはできません。
実装のしやすさ	もっと簡単	複雑な
含まれるレベル	シングルレベル	マルチレベル
例	配列、キュー、スタック、リンクリストなど	木とグラフ
メモリ使用率	無効	有効

線形データ構造の定義

データ要素が線形リストのシーケンスを構成する場合、データ構造は線形であると見なされます。要素は互いに隣接してそして特定の順序で結合されている。それは線形メモリ空間を消費し、データ要素はメモリに順次に格納することが要求される。線形データ構造を実装している間、必要な量のメモリが以前に宣言されています。それはメモリの有効利用をしないし、メモリの浪費をもたらします。データ要素は連続的に訪問され、単一要素にしか直接到達できない。

線形データ構造に含まれる例は、配列、スタック、キュー、リンクリストなどです。配列は、一定数の同種の要素またはデータ項目のグループです。 スタックとキューも配列のような要素の順序付けられたコレクションですが、スタックが要素の挿入と削除にFIFO（先入れ先出し）順に続き、キューがFIFO（先入れ先出し）を使用するという特別な条件があります。 リストは、一連の可変数データ項目として定義できます。

非線形データ構造の定義

非線形データ構造は、データを連続して配置するのではなく、ソートされた順序で配置されます。この場合、データ要素は、子、親、および祖父母の間の関係を含む階層関係を示す複数の要素に添付できます。非線形データ構造では、データ要素のトラバースと挿入または削除は順番には行われません。

非線形データ構造はメモリを効率的に利用し、事前にメモリ宣言を必要としない。非線形データ構造には、 ツリーとグラフの2つの一般的な例があります。ツリーデータ構造は、データ要素を階層関係で編成して格納します。

線形データ構造と非線形データ構造の主な違い

線形データ構造では、データは要素が次々にリンクされる線形順に編成されます。それとは対照的に、非線形データ構造では、データ要素は逐次的に格納されているのではなく、要素は階層的に関連している。
線形データ構造内のデータのトラバースは、すべてのデータ要素を一度にトラバースすることができるため、簡単ですが、一度に到達できるのは1つのエレメントのみです。それどころか、非線形データ構造では、ノードは順次訪問されず、一度に行き来することはできない。
データ要素は線形データ構造内で隣接して接続されます。つまり、1つのデータ要素を他の多数の要素に接続できる非線形データ構造では、2つの要素だけが2つの要素にリンクできます。
線形データ構造は、非線形データ構造に対して容易に実施される。
単一レベルの要素が線形データ構造に組み込まれています。逆に、非線形データ構造は複数のレベルを含みます。
線形データ構造の例は、配列、待ち行列、スタック、リンクリストなどである。対照的に、ツリーおよびグラフは、非線形データ構造の例である。
メモリは、線形データ構造がメモリを無駄にする傾向がある非線形データ構造において効率的に利用される。