LeetCode 146 問「LRU Cache」について解説します。
この問題では、LRU Cacheの要件を満たすために LRUCache クラスを実装することが求められます。
まずは問題文の説明を見ていきましょう。
LRUCache クラスのコンストラクタでは、integer 型の capacity を受け取り、その capacity を持つキャッシュを初期化します。
get メソッドは integer 型の key を受け取り、その key がキャッシュ内に存在すれば対応する value を返し、存在しなければ -1 を返します。
put メソッドは integer 型の key と value を受け取り、
その key がキャッシュ内に存在する場合：対応する value を更新する
存在しない場合：新しい key-value ペアをキャッシュに追加する
さらに、この操作によってキャッシュのサイズが capacity を超えた場合は、最も長い間使われていなかった key（Least Recently Used）を削除します。
ちなみに、get メソッドと put メソッドの両方が、その key の「使用」を意味します。
また、問題文では、get と put は平均時間計算量 O(1) を満たす必要がある、と記載されています。
では、どのように実装すればよいのでしょうか？
もし使用順序を追跡するために queue を使った場合、get も put も O(n)の時間計算量をかかってしまいます。
なぜでしょうか？
get メソッドの場合を先に見ていきましょう。
key が queue 内に存在する場合、その key を「最近使われた」状態を示すために queue の末尾へ移動させる必要があります。
しかし、この key を見つけるには queue を先頭から探索（traverse）しなければならず、最悪 O(n) の時間計算量となります（ここで n は capacity）。
さらに、put メソッドの場合を見ていきましょう。
key が存在する場合は、同じく key を queue の末尾へ移動させる必要があります。
そのため、検索に O(n) の時間計算量が必要となります。
では、どのように get と put を O(1) の時間計算量にするのか？
ここで使用するのが Doubly-Linked List（双方向リスト） です。
そして、これを Hash Table（ハッシュテーブル） と組み合わせます。
コードを見て詳しく説明していきましょう。
17 行目では、後で使用するために、constructor で受け取った capacity の値を size プロパティに保存します。
18 行目では、空の dictionary を作成し cache プロパティとして保持します。
cache の key にはキー、value には対応する Node オブジェクトを格納します（Node の定義は後述します）。
value に integer の値ではなく Node オブジェクトを保存する理由は、後でそのノードを Doubly-Linked List の末尾へ移動する際、先頭や末尾から探索する必要がなくなるためです。探索が必要になると 時間計算量が O(n) になってしまいます。
Doubly-Linked List を使用するため、1〜12 行で Node クラスを定義しています。
プロパティは以下の通りです：
- key
- value
- prev（前の Node オブジェクトへの参照、または None）
- next（次の Nodeオブジェクト への参照、または None）
最も古い要素と最新の要素を管理するために、19 行目と 20 行目で left プロパティと right プロパティを定義しています。
ここでのテクニックとして、両方とも 新しく作ったダミーノード（sentinel）を指すようにしています。
None を使うよりも、後続のロジックが簡潔になるメリットがあります。
21 行目では、left が指すノードの next を right に
22 行目では、right が指すノードの prev を left に設定しています。
get と put メソッドを見る前に：remove と insert メソッドを見ていきましょう。
remove メソッド
双方向リスト から特定のnodeを削除する helper function です。
25〜30 行の処理内容：
- 与えられたnodeの前のノードを prev に保存（25 行目）
- 与えられたnodeの次のノードを nxt に保存（26 行目）
- node.prev を None に（27 行目）
- node.next を None に（28 行目）
- prev.next を nxt に（29 行目）
- nxt.prev を prev に（30 行目）
insert メソッド
与えられた node を right sentinel の左側（= 最新位置）に挿入する helper function です。
33〜37 行の処理内容：
- right sentinel の前のノードを prev に保存（33 行目）
- prev.next を node に（34 行目）
- node.next を right sentinel に（35 行目）
- right sentinel の前のノード を node に（36 行目）
- node.prev を prev に（37 行目）
get メソッド
key が self.cache に存在する場合：
- 対応ノードを双方向リストから削除（41 行目）
- そのノードを最新位置に挿入（42 行目）
- ノードの value（integer）を返す（43 行目）
存在しない場合は -1 を返す（44 行目）。
put メソッド
まず key が self.cache に存在するか確認します。
key が存在する場合：
- ノードの val を更新（48 行目）
- ノードを双方向リストから削除（49 行目）
- ノードを最新位置に挿入（50 行目）
- return（51 行目）
key が存在しない場合：
新しい Node(key, value) を作成（52 行目）
それを self.cache[key] に代入（53 行目）
新ノードを最新位置に挿入（54 行目）
その後、self.cache のサイズが capacity を超えていないか確認（55 行目）。
もし超えていたら：
- 最も古いノード（left.next）の key を lru_key に保存（56 行目）
- left.next のノードを削除（57 行目）
- self.cache から lru_key を削除（58 行目）
最後に補足
単方向リストより双方向リストを使う理由は、特定ノードを削除する際、そのノードの前のノードを O(1) の時間計算量で参照できるためです。
単方向リストでは prev ポインタがないため、そのノードの前を探すには先頭からのトラバースが必要となり、O(1) ではなく O(n) となってしまいます。
以下は私がGitHubにアップロードするコードです。
参考したいなら、見てください。
Python code on GitHub
参考文献: