How to implement linked list using HashMap in java

Question

How can I create linked list using HashMap in java? I searched online, there are implementations using LinkedList data structure. Interviewer asked me to implement it without using LinkedList data structure, I tried to do with HashTable but at the end he said I should have done it using HashMap.

Thank you so much for answers.

I have done this after reading your comments:

public class hashMap {
 static Map<Integer, Integer> mMap = new HashMap<Integer, Integer>();
 public static void main(String[] args) {
 int a;
 mMap.put(1, 2);
 mMap.put(2, 3);
 mMap.put(3, 4);
 mMap.put(4, 7);
 mMap.put(7, 8);
 Scanner in = new Scanner(System.in);
 System.out.println("Enter: ");
 a = in.nextInt();
 itera();
 if(mMap.containsKey(a)) {
 add.insert(a);
 }
 else if (!mMap.containsKey(a)) {
 add.remove(a);
 }
 itera();
 }
 public static void itera() {
 for (Iterator<Integer> iter = (Iterator<Integer>) mMap.keySet().iterator(); iter.hasNext();) {
 int key = iter.next();
 int sa = mMap.get(key);
 System.out.println(key + " : " + sa);
 }
 }
 static class add {
 public static void insert(int a) {
 int s = a-1;
 int newKey = s; 
 int sa = mMap.get(a);
 mMap.put(newKey, sa);
 mMap.remove(a);
 }
 public static void remove(int a) {
 int newa = a;
 while(!mMap.containsKey(a)) {
 a--;
 System.out.println("while a: " + a);
 }
 mMap.put(newa, mMap.get(a));
 mMap.put(a, newa);
 }
}
}

It just inserts and deletes nodes into Linked List. But there is problem if some keys are missing, like 5 & 6 is not there in keys. So if I try to insert 6, it doesn't work. Could anyone explain what am I doing wrong?

• Sergey Kalinichenko: There's nothing to explain: HashMap is the new HashTable :)
• user207421: I don't know why you used a Hashtable either, or even how. He should have gone into that aspect of it rather than nitpicking over collection classes.
• qwr: @user2142511 .well make it as class and add insert and remove methods . post that class. and coming for objects you store it in another place .u can do it inside key,object pair or use another hashmap with key ,value . insert will be easy and fast, getting will be easy and fast too cause your linked list will use indexes . inserting in the middle will be high cost and removing too . u have to insert then renew indexes of other keys .see en.wikipedia.org/wiki/Linked_list Speeding up search section for pros and cons of this method
• Mayur: @QWR Thanks for your help! I have again edited the code, making a new class and adding insert and remove methods. I think it works. Is there anything we can do to make it more efficient?
• qwr: @user2142511 look your insert code again . I can't get what u trie to store as a value . you can store last key always . so next time when inserting (insert method just with value without index) you will just use mMap.put(newa, currentkey);currentkey=newkey ; this way you link last stored to previous . Make it fully class implement from List then write vital methods insert remove and etc .It is important how you are writing codes too

Answer 1

I tried to do with HashTable but at the end he said I should have done it using HashMap.

HashTable is an old Java 1.0 class that has a couple of undesirable properties:

• All operations are synchronized ... which is typically unnecessary
• The class doesn't allow null keys or values ... which HashMap does.

Apart from that (and the fact that HashTable supports the old Enumeration API) HashMap and HashTable behave pretty much the same. It is common knowledge that it is a bad idea to use HashTable ... unless you are working on a codebase / platform that actually requires it.

So the interviewer is pointing out (correctly) that you used an out-of-date class for (probably) no good reason. Ooops!

---

But unless he specifically told you to do this, implementing a linked list using a hash table of any kind is a pretty bad idea.

• It is obscure
• It is unnecessarily complicated
• It is inefficient
• It strongly suggests that your understanding of data structures and algorithms is weak.

A simple linked list is easy to implement from scratch in plain Java. That's what you should have done.

Much bigger Ooops!!!

Answer 2

Stupid interview questions.

Easiest way I can think of is to store the "index" for each value in the key and the value as the, well, value.

Have to externally maintain the head and tail index but that is not too surprising.

Add will then look like:

public void add(V value) {
 _map.put(_tail, value);
 _tail += 1;
}

Remove:

public boolean remove(V value) {
 Iterator<Map.Entry<Integer,V>> _map.entrySet().iterator();
 while( iter.hasNext() ) {
 Map.Entry<Integer,V> entry = iter.next();
 if( value.equals(entry.getValue()) ) {
 iter.remove();
 return true;
 }
 }
 return false;
}

Leave the rest as an exercise for the reader.

• Lone nebula: The remove method doesn't remove a value correctly. Let's say the underlying map contains the entries (a, b) and (b, c). By removing the value b, these entries should be reduced to (a, c), but in your code they are reduced to (b, c).
• Rob Moore: The key is a one up Integer not one of the values. For a "list" containing 'a', 'b', and 'c' the map would contain the key/values (1, 'a'), (2, 'b'), (3, 'c'). On a remove('b') the code removes the tuple (2, 'b'). The code does not "refill" the voids created by removes which may or may not be needed.
• Lone nebula: Oh sorry, I see how your code works now. But that would be a random access list rather than a linked list.
• Mayur: @RobMoore Thanks for your answer. I have edited the question, there is still some problem. Could you please take a look at it?