Javaでは、要素がリストに挿入される位置を保存できる場合、LinkedListコレクション から要素を取得できますか?私は一定時間にリストの途中からアイテムを削除したいので、ArrayListを使用することはできません。HashMapを使用して一定時間JavaのLinkedListから要素を取得する方法
LinkedListのgetは、引数としてintを受け入れ、複雑さはO(N)です。
C++では、マップを使用してリストのイテレータを格納できます。一定の時間に任意の要素にアクセスするために、私はハッシュテーブル内の要素を検索し、それに対するイテレータを取得することができます。イテレータを使用して、リスト内のその項目にアクセスできます。
- どのようにしてJavaで同様の機能を実現できますか?
- イテレータをHashMapの値に格納し、これを使って要素に直接アクセスできますか?
ここでは、C++でどのように行うことができるかを示すコードスニペットを示します。このプログラムは、LinkedListとHashMapの両方を必要としません。しかし、LRUキャッシュのようなものや、マップと同様にリストを維持したいという別のシナリオを想像してみてください。
list<string> namesList;
unordered_map<string, list<string>::iterator> namesMap;
namesList.push_front("hello");
namesMap["hello"] = namesList.begin();
namesList.push_front("hi");
namesMap["hi"] = namesList.begin();
namesList.push_front("abc");
namesMap["abc"] = namesList.begin();
// Now to access "hi" on the list, I can just look it up on the map
// Get iterator to "hi" from the map and access it
auto itr = namesMap.find("hi");
if (itr != namesMap.end())
{
// This is a simple case where my list is just storing the key
cout << *(itr->second) << endl;
}
しかし、一定時間内にリストの途中からアイテムを削除したいとします。 – Anit
'Map'だけを使ってリストをドロップするのはなぜですか?挿入順序を保持したい場合は、 'LinkedHashMap'を使ってそれを行います。 –
私が追加した例では、リストは必要ありません。しかし、LRUキャッシュのようなものや、マップと同様にリストを維持したいという別のシナリオを想像してみてください。二重リンクリストを実装する以外の選択肢がありますか? – Anit