連結リスト

説明

双方向連結リストを実装しましょう。

配列と同じように、連結リストはシンプルな線形のデータ構造です。 連結リストを使えば、キュー、スタック、連想配列など、よくあるデータ型をいくつも実装できます。

連結リストは、ノードと呼ばれるデータ要素の集まりです。 単方向連結リストでは、各ノードが値と次のノードへのリンクを持ちます。 双方向連結リストでは、各ノードが前のノードへのリンクも持ちます。

ここでは、双方向連結リストの実装を書いていきます。 値と、次のノードおよび前のノードへのポインターを保持するNodeを実装しましょう。 次に、最初と最後のノードへの参照を保持し、要素の追加と削除のための、配列に似たインターフェースを提供するListを実装します。

• push（末尾に値を挿入）;
• pop（末尾の値を削除）;
• shift（先頭の値を削除）.
• unshift（先頭に値を挿入）;

実装をシンプルに保つため、テストではエラーが起きる状況は扱いません。 具体的には、空のリストに対してpopやshiftが呼び出されることはありません。

連結リストについて詳しくは、Wikipediaのページを読んでみましょう。