36

I would like to use a Linked List like the one described in this paper. However, I didn't find any Java implementation in the web.

If no java implementation of the above mentioned Linked List exists, I think, I would use the java.util.concurrent.ConcurrentLinkedQueue<E>. Is this a good choice (it is not really a linked list)?

If it's not a good choice, does anyone know of a reliable concurrent (thread-safe) wait-free(lock-free) Linked List implementation in Java?

ptikobj
  • 2,690
  • 7
  • 39
  • 64
  • It's not lock-free in any shape of form (it does use locks for adding/removing) - doh target comment gone... (it was regarding LinkedBlockingDeque) – bestsss Jan 18 '11 at 14:15
  • Well, the big question is, why do you think you want a concurrent list of any shape or form? Most List methods don't make sense on a shared concurrent structure. Why would you get the nth element? What does it mean anyway to get the nth element? Things like size are ephemeral and of no value apart from for monitoring. Can you explain a bit more about how you want to use this? http://permalink.gmane.org/gmane.comp.java.jsr.166-concurrency/6321 – Jed Wesley-Smith Jan 18 '11 at 22:55
  • I want to implement a singleton "physical" buffer, which is used by n "logical" buffers, where each logical buffer is defined only by its start and end elements, s.t. I don't have a redundant representation of my data in memory. – ptikobj Jan 19 '11 at 06:12
  • well, I still don't understand what problem you are trying to solve, you have only outlined a solution. Often in a concurrent algorithm you do need to trade memory for isolation though, the costs of coordinating access and modification to the same memory can be prohibitive. See Guy Steele for example http://www.infoq.com/presentations/Thinking-Parallel-Programming – Jed Wesley-Smith Jan 21 '11 at 00:03

1 Answers1

44

ConcurrentLinkedQueue is a superb lock free queue and does what a concurrent single linked list can do. A small warning: if you dont use poll or peek and only iterator() (+.remove()) it will leak memory.

It's an outstanding Queue.

Basil Bourque
  • 303,325
  • 100
  • 852
  • 1,154
bestsss
  • 11,796
  • 3
  • 53
  • 63
  • 7
    JDK 7 has a ConcurrentLinkedDeque – Peter Lawrey Jan 18 '11 at 14:24
  • let's say, i want the ConcurrentLinkedDeque, how safe is installing the current jdk7 preview version? – ptikobj Jan 18 '11 at 14:34
  • actually it's fairly simple to implement it in Java (both queue, deque). Thanks to the GC, there is no ABA. Overall concurrent/lock-free algos are times easier if you have GC... Or just to grab the source form the JDK7 and run it at w/ JDK6, you will (most likely) need Unsafe but that's not an issue, if you drop the code in bootstrap path. To make sure I am not going wrong I will check the latest JDK7 source code and tell if the code can be safely backported (copied) into jdk6 – bestsss Jan 18 '11 at 14:52
  • @betsss I feel like that is overkill. The OP can just go to http://g.oswego.edu/dl/concurrency-interest/ and download the jar. It should be very stable considering it will be introduced with Java 7 (which should be going live soon). – John Vint Jan 18 '11 at 14:55
  • yeah it looks it can be safely copied into and run w/ jdk6 – bestsss Jan 18 '11 at 14:59
  • actually forgot that (about CLD): "Empirically, microbenchmarks suggest that this class adds about 40% overhead relative to ConcurrentLinkedQueue, which feels as good as we can hope for." So unless really needed to do pollLast()... – bestsss Jan 18 '11 at 15:05
  • If you're trying to achieve a ConcurrentLinkedList you can imagine the added overhead will be a good amount more. But I agree a ConcurrentLinkedQueue would be best to use. – John Vint Jan 18 '11 at 15:15
  • If I rethink my application, I think it should be relatively easy to solve my problem with a queue instead of a Linked List. I will just have to reimplement some of the already written stuff. – ptikobj Jan 18 '11 at 15:33
  • Can we sort concurrent linked queue using collections.sort() ?? I don't think so, but we can use collections.sort() on a linked list. Correct me if I am wrong. – 2rd_7 Jun 13 '16 at 07:29
  • Queues do not support the `get(int)` method for random access, so any type of `Queue` is not a substitute for a `List`. – Luke Hutchison Jul 26 '20 at 11:02