双方向リストの初期化とダミーヘッド・ダミーテイルについて

双方向リストの基本構造

双方向リストは、各ノードが前後のノードへの参照を持つデータ構造です。これにより、リスト内のノードを両方向にたどることができます。

ノードの構造

まず、ノードの構造は以下のようになります：

class Node<K, V> {
    K key;
    V value;
    Node<K, V> prev;
    Node<K, V> next;

    public Node(K key, V value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

• key：ノードのキー
• value：ノードの値
• prev：前のノードへの参照
• next：次のノードへの参照

ダミーヘッドとダミーテイル

双方向リストを簡単に管理するために、ダミーヘッド（head）とダミーテイル（tail）という特別なノードを使用します。これにより、リストの先頭や末尾の操作が容易になります。

リストの初期化

ダミーヘッドとダミーテイルを使ったリストの初期化は次のように行います：

class DoublyLinkedList<K, V> {
    private final Node<K, V> head;
    private final Node<K, V> tail;

    public DoublyLinkedList() {
        this.head = new Node<>(null, null); // ダミーヘッド
        this.tail = new Node<>(null, null); // ダミーテイル
        head.next = tail;
        tail.prev = head;
    }
}

ここで head.next = tail; と tail.prev = head; は以下のような意味を持ちます：

1. head.next = tail;:

   • ダミーヘッドの next フィールドがダミーテイルを指します。
   • これにより、リストの先頭に要素がない場合、ダミーヘッドの next は常にダミーテイルを指すことになります。
   • リストが空の状態では、ヘッドの次がテイルとなります。

2. tail.prev = head;:

   • ダミーテイルの prev フィールドがダミーヘッドを指します。
   • これにより、リストの末尾に要素がない場合、ダミーテイルの prev は常にダミーヘッドを指すことになります。
   • リストが空の状態では、テイルの前がヘッドとなります。

リストの初期状態

上記の設定により、リストの初期状態は次のようになります：

head <-> tail

• head.next は tail を指し、
• tail.prev は head を指します。

この構造により、双方向リストの操作（ノードの追加や削除）が簡単になります。

ノードの追加例

新しいノードをリストに追加する場合、例えば先頭にノードを追加する操作は次のように行います：

public void addFirst(Node<K, V> node) {
    node.prev = head;
    node.next = head.next;
    head.next.prev = node;
    head.next = node;
}

この操作により、リストは以下のように更新されます：

1. 新しいノード node の prev を head に設定します。
2. 新しいノード node の next を現在の最初のノード（head.next）に設定します。
3. 元の最初のノードの prev を node に設定します。
4. head.next を node に設定します。

結果として、リストの先頭に新しいノードが追加されます。

ノードの追加後の状態

head <-> node <-> tail

このように、ダミーヘッドとダミーテイルを使うことで、リストの先頭や末尾に要素を簡単に追加・削除することができるようになります。

実際の応用例

例えば、LRUキャッシュの実装では、双方向リストを使用してキャッシュ内の要素を管理します。この方法により、最も古い要素を効率的に削除し、最新の要素を簡単に追加できます。双方向リストの管理が簡単で、O(1)の時間複雑度で操作が行えるため、パフォーマンスが向上します。