Java: is there another kind of linked list somewhere?

Is there a pre-implemented linked list out there that would have been implemented using id's instead of array indexes?

MOTIVATION: what I want to accomplish here is a linked list from witch cells can be removed by multiple threads in parellel. The problem with java's LinkedList is that the references are index ref's.

To clarify: let's say I have three threads and a LinkedList of three cells. Thread number one produces to cell number one (or 0 but anyway...), ...and thread number three produces to cell number 3. so basically threads produce stuff to their cells that work as buffers. Now if thread number 2 removes cell number two (for a business logical reason) the reference of thread #3 changes to #2. Naturally this can't be done if thread #3 is still working on cell #3, so synchronization is needed and even if thread #3 isn't currently using it's cell, the thread still needs to be told that it's going to use cell #2 from now on.

The solution: if the linked list would have been implemented using id's instead of array index references the other threads would never see the changes, i.e. the cell number two could be safely removed since thread #3 would use it's cell something like this linkedlist.add(id 3, C cell) instead of like this add(int index, C cell).

I开发者_开发百科 guess something like this is already implemented somewhere but after a while of googling, I couldn't find it. ALL HELP APPRECIATED!

---

LinkedHashMap seems relevant, but I'm not sure if it completely fits your scenario. Try it. It's a HashMap so you are accessing items with their keys.

---

Linked Lists refer to the 'Next', working with Indices in Linked Lists can lead to bad performance when attempting to access the item at index 'N' when 'N' is a large number.

Why do you need a list? is the order that much of an issue? Why can't you use a Map?

---

There are only two ways of talking about a conventional List element by position.

• You can refer to a list element by its index; i.e. by the number of steps it takes to reach the element starting from the first element. (That is what List.get(int) means.) The problem is that the index of an element can change due to other operations on the list.

• You can refer to a list element using an Iterator as a cursor. Some other operation could remove an element before or after the one you are looking at, but this shouldn't effect the current one, provided that you use an appropriate List implementation. (If you use a non-concurrent list, you are likely to get ConcurrentModification exceptions.)

The bottom line is that if you are worried about some other thread's updates causing indexes to change, don't use indexes. Use an Iterator, and a collection implementation that supports concurrent modifications; e.g. CopyOnWriteArrayList, ConcurrentLinkedQueue or one of the others ... depending on exactly what you are trying to do and what guarantees you require.

---

I'm not aware of any List implementation that allows you to lock out updates that would change an element's position. The List APIs don't support this kind of thing.

Besides:

• locking a list like that could be major concurrency bottleneck, and
• using get(int) or set(int, Object) on a LinkedList doesn't scale.