CODEWITHSUNDEEP
javalinked-listhashmapiterator
Anit
Anit

Reputation: 355

How to get element from Java's LinkedList in constant time using HashMap

In Java, is there way I can get an element from LinkedList collection at constant time if I can store the position where the element is inserted into the list? I can't use an ArrayList as I want to delete items from the middle of the list at Constant time.

LinkedList's get accepts int as an argument and the complexity is O(N).

In C++, I can use a map to store the iterator of the list. To access any element at constant time, I can lookup the element in the hash table and get the iterator to it. Using the iterator I can get to that entry in the list.

  1. How can I achieve a similar functionality in Java?
  2. Can we store iterator in HashMap's value and use that to directly access an element?

Here is a code snippet that shows how I can do it in C++. This program doesn't require both LinkedList and HashMap. But imagine something like an LRU Cache or a different scenario where I want to maintain a list as well as a map.

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;
}

Upvotes: 2

Views: 2080

Answers (2)

Daniel Pryden
Daniel Pryden

Reputation: 60997

java.util.LinkedHashMap sounds like exactly what you want (including the LRU case). For more elaborate caching situations, you probably want com.google.common.cache.Cache from the Guava library.

There is no way to store a pointer to a specific node in a Java LinkedList, and in fact LinkedList is a pretty useless implementation -- even Josh Bloch who wrote it doesn't recommend it anymore. If your needs are more specialized than what LinkedList and LinkedHashMap can handle, then you should probably just build your own linked list implementation -- it's literally the simplest data structure to implement.

Upvotes: 3

Programmer
Programmer

Reputation: 95

Hashmap has better performance to find elements than a List, always. It is a limitation of the data structure itself.

In Java you can implement a Hashmap to get any elements at constant time. But in a List the best algorithm to search elements in a List (sorted list) is a Binary Search that cost O(log n).

Upvotes: 0

Related Questions