What is a Doubly Linked List?

双方向連結リストは、各ノードが値と2つのポインタ（前のノードへのprevと次のノードへのnext）を持つノードのシーケンスです。リスト自体は、head（最初のノード）とtail（最後のノード）の両端を追跡します。

ノードごとの2つのポインタと追加のtail参照により、多くの利点が得られます。末尾への追加はO(1)になり（チェーンをたどる代わりにtailに直接ジャンプします）、最後のノードの削除もO(1)になります（tail.prevから最後から2番目のノードに到達できるため）。トレードオフは、ノードあたりのメモリ消費が増えることと、挿入や削除のたびに同期を保つべきポインタが増えることです。

双方向連結リストにおける主な5つの操作は以下の通りです：

1. AddFirst: リストの先頭に値を追加します。
2. AddLast: リストの末尾に値を追加します（O(1)!）。
3. Get: 指定されたインデックスの値を返します。
4. RemoveLast: 最後のノードを削除します（O(1)!）。
5. Size: 現在格納されているノードの数を返します。

まずNodeクラスを作成し、その上にDoublyLinkedListを構築しましょう！