シングルリンクリストとダブルリンクリストの違いとは?分かりやすく解説!

スポンサーリンク
スポンサーリンク


シングルリンクリストとダブルリンクリストの主な違いは、シングルリンクリストのノードには次のノードのアドレスが格納され、ダブルリンクリストのノードには次のノードと前のノードのアドレスが格納されることである

配列は、同じデータ型の要素群を格納するデータ構造です。

配列の大きな欠点は、あらかじめ定義されていたり、長さが固定されていることです。

リンクリストは、データを動的に格納することができるため、この問題を解決することができる。

そのため、実行時に要素を追加することが可能です

つまり、リンクリストでは、必要なときに必要な要素のためのメモリを確保することができる

リンクリストにはさまざまな種類があり、単一リンクリストと二重リンクリストがその2つです。

  簡単に説明すると、単一リンクリストは一方向へのトラバースが可能であり、二重リンクリストは要素を通して両方向へのトラバースが可能である

スポンサーリンク

シングルリンクリストとは

リンクリストとは、一連のノードの集まりからなる線形データ構造のことです。

ノード(要素)はデータと他のノードのアドレスから構成される。

単一リンクリストは、リンクリストの一種である

単一リンクリストには、データと次のノードのアドレスが格納される。

次のノードのアドレスが格納されるため、ノードは互いに参照し合っている。

したがって、鎖のような構造を形成する。

単一のリンクリストの要素に対して、挿入、削除、走査などの操作を行うことができる。

ダブルリンクリストとは

シングルリンクリストと同様に、ダブルリンクリストもリンクリストの一種です

2重リンクリストとも呼ばれる。

データと2つのアドレスが格納される。

このアドレスは、次のノードのアドレスと前のノードのアドレスです。

2つの参照があるため、二重リンクリストの要素を前に進めたり後ろに戻したりすることができる。

さらに、プログラマは二重リンクリスト内の要素を挿入したり、削除したりする操作を行うことができる。

Main Difference - Single Linked List vs Double Linked List

この2種類のリンクリストの他に、循環リンクリストというリンクリストがあります。

この種のリストでは、最後のノードに最初のノードのアドレスが格納されます。

したがって、循環鎖のような構造を形成する。

シングルリンクトリストとダブルリンクトリストの違い

定義

単一リンクリストとは、データフィールドと、ノードの列の次のノードを指すネクストフィールドを持つノードを含むリンクリストのことです。

これに対し、ダブルリンクリストは、データフィールドと、次のノードを指すネクストフィールドと、一連のノードの前のノードを指すプレストフィールドを含むリンクリストです。

したがって、これがシングルリンクリストとダブルリンクリストの主な違いです。

方向性

また、単一リンクリストは要素を一方向にトラバースすることができ、二重リンクリストは両方向(後方および前方)にトラバースすることができる。

必要メモリ

シングルリンクリストとダブルリンクリストのもう一つの違いは、必要なメモリ容量です

シングルリンクリストは1つのアドレスしか保存しないので、必要なメモリは少なくて済みますが、ダブルリンクリストは2つのアドレスを保存するので、より多くのメモリが必要です

挿入と削除

単一リンクリストの既知の位置での挿入と削除の複雑さはO(n)です。

ダブルリンクリストの既知の位置での挿入と削除の複雑さは、O(1)です。

したがって、この点もシングルリンクリストとダブルリンクリストの違いと言える。

結論

リンクリストは、一連のノードのグループからなる線形データ構造です。

実行時に非連続のメモリ位置に要素を格納します。

リンクリストには、シングルリンクリストとダブルリンクリストの2種類があります。

シングルリンクリストとダブルリンクリストの主な違いは、シングルリンクリストのノードが次のノードのアドレスを格納するのに対して、ダブルリンクリストのノードは次のノードと前のノードのアドレスを格納することです。

タイトルとURLをコピーしました