A*
OPEN/CLOSEリストに登録されているノードの数が多い場合、ノードの展開ごとに子ノード m をOPENから CLOSE へ移動(あるいは逆)するのは非常に高価な操作である。 たとえば、OPEN/CLOSEリストが2分探索木(赤黒木など)で実装されている場合、まずノードの探すのに O ( l o g N ) {\displaystyle O(logN)} かかり(ノードのIDで検索)、また削除にも O ( l o g N ) {\displaystyle O(logN)} かかる。配列の場合には削除により大きなコストがかかる。
しかし、データ構造を工夫することで、より効率よい実装を行うことが出来る。ノードを OPEN/CLOSEリスト間で行ったり来たりさせる代わりに、以下のように実装する:
それぞれのノードに、ノードの状態として OPEN, CLOSE の2種類のタグをもたせる。全てのノードは始めOPENである。
ノードに一意な整数 ID をもたせる。
また、ID からノードを O ( 1 ) {\displaystyle O(1)} で参照できるハッシュテーブルを用意する。