#java

How to implement LinkedHashMap with LinkedList and HashMap in java?

@Acer That should be simple. Just internally use a hashmap and wrap the elements you add to it with a link to next and prev elements and store the first and last elements explicitly. Then use whichever collection's method is fastest when accessing it.

@freemo

Thanks
Yes, It should be simple.

I was thinking that whether there is a way to wrap the elements with java.util.LinkedList

I tried to use prev() and next() of ListIterator, but it seems they only work for immutable LinkedList

@Acer No, not efficiently.

But prev and next should work for writable linked lists.. what sort of error you get?

@freemo

If the LinkedList changed, the stored iterators will throw a Concurrent Modification exception when I try to use them.

@Acer yes that is correct, though not limited to LL... all collections forbid you to modify them while iterating over them.

In short, collection classes are **not** thread safe.

You can either synchronize yourself to insure you do not modify the list as your using the iterator or you can use the builtin utils that wrap a collection and allow it to be synchronized:

https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#synchronizedList(java.util.List)

Though again, the approach your using is fundamentally flawed and wont work even once you fix the synchronization problem. Looking up elements in a linked list is expensive and thus if there is no way to directly access its point in memory from the hashmap you have defeated the whole purpose of a linked hashmap.

@freemo

This problem is not a concurrent problem actually. Even you synchronize well, any modification using not the iterator itself will throw the exception.

Yea, a pointer is better than an iterator, but I failed to find a pointer to elements in LinkedList/HashMap

@Acer Thats valid, even if you synchronize it wont allow you to modify while using the iterator unless you modify it **through** the iterator (which only allows you to remove IIRC)... So you are required to avoid that.

Everything in java (except primitives) are a pointer by default. The wrapper you put around classes before inserting it into your hashmap would be the pointer basically.

@freemo

a pointer could be a value
I might need a pointer of the pointer

for example

int is premitives
Integer is not.
Integer in LinkedList<Integer> has no prev()/next()
Integer itself is a pointer of its value, but Integer is the value of the element(list node) not the pointer of the element(list node)

@Acer Thus why I said: "The wrapper you put around classes before inserting it".. the wrapper is effectively the pointer and the thing it wraps is the "value".. the wrapper would contain three properties "next, prev, value".. next points to the next wrapper, prev points to the previous wrapper, value points to the value.

You will effectively be implementing your own linked list but using the built in hash-type list. and of course using builtin interfaces.

Do you need me to write out a full solution for you to make it clearer?

@freemo

I already wrote hashmap and own linked list solution.

I was just curious about whether java.util.LinkedList could also do that

It seems to me that it could not

@Acer You could do something that is extremely ineffcieint using LinkedList.. but no, I cant think of any way to do an efficient version with built-in linked list implementation.

You might be able to hack something together, however, using the AbstractSequentialList