単方向リストと双方向リスト

単方向リスト

単方向リスト【Singly Linked List】は、複数の要素を順序付けて格納するデータ構造の一つです。単方向リストでは、各要素がリスト内で一方向にのみつながる（線形）構造を持ちます。

単方向リストの要素は、通常は「ノード」と呼ばれます。各ノードは、データを保持するためのフィールドと、次のノードへの参照を格納するためのフィールドを持ちます。リストの先頭ノードは「ヘッド」、末尾ノードは「テール」と呼ばれます。

単方向リストは、データの追加や削除が高速に行えるという利点があります。一方で、要素の検索にはO(n)の時間が必要となるという欠点もあります。また、各要素が次の要素の参照しか持っていないため、リスト内の要素を逆方向にたどることはできません。

なお、JavaのArrayListクラスは、今回紹介した単方向リストではなく、配列の応用です。つまり、可変長配列を実装したリスト（動的配列）です。初期化時には、内部の配列は指定された初期容量（デフォルトは10）で作成されます。要素の追加や削除が行われるときに、内部配列のサイズが不足する場合は自動的にリサイズされます。ArrayListはランダムアクセス（インデックスを指定しての要素へのアクセス）において高速ですが、検索に関しては要素を順番に調べる線形検索となるため、効率はあまり高くありません。

以下の練習問題でリストの理解度を確かめてください。

練習問題

基本情報技術者試験 平成29年春期 午前問4

練習問題

基本情報技術者試験 平成30年春期 午前問6

練習問題

基本情報技術者試験 平成27年秋期 午前問5

＜サンプルプログラム＞

＜出力結果＞

5 8 3 2

双方向リスト

双方向リスト【Doubly Linked List】は、リスト内の各ノードが前後のノードへの参照を持つデータ構造です。各ノードがデータと前後のポインタ（参照）を持ち、リストの前方から後方、後方から前方の両方向に操作が可能です。

通常の単方向リスト【Singly Linked List】では、各ノードが次のノードへの参照を持ちますが、前のノードへの参照は持ちません。一方、双方向リストでは、各ノードが次のノードへの参照だけでなく、前のノードへの参照も持つため、リストの前後の移動や操作が容易になります。

双方向リストの主な利点は、以下の点です：

順方向と逆方向のトラバース（走査）が容易：各ノードが前後のポインタを持っているため、リストを順方向または逆方向に移動しながら要素にアクセスすることができます。

要素の挿入と削除が効率的：双方向リストでは、挿入や削除時に前後のポインタを調整するだけで済みます。一方、単方向リストでは、挿入や削除を行う場合には前方のノードを探索する必要があります。

リストの逆順アクセスが可能：双方向リストでは、最後のノードから最初のノードに向かって逆順にアクセスすることも容易です。

双方向リストの欠点は、単方向リストと比べて各ノードが前方への参照を保持するためにメモリ使用量が多くなることです。また、リストの操作に伴う実装の複雑さも挙げられます。

双方向リストは、特に要素の追加や削除が頻繁に行われる場合や、順方向および逆方向のアクセスが必要な場合に有用です。

＜サンプルプログラム＞

＜出力結果＞

Forward: 5 8 3 2 Backward: 2 3 8 5