Lock-Free Concurrent Linked List in Java

Question

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?

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
– bestsss, Commented Jan 18, 2011 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? permalink.gmane.org/gmane.comp.java.jsr.166-concurrency/6321 — Jed Wesley-Smith
– Jed Wesley-Smith, Commented Jan 18, 2011 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
– ptikobj, Commented Jan 19, 2011 at 6: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 infoq.com/presentations/Thinking-Parallel-Programming — Jed Wesley-Smith
– Jed Wesley-Smith, Commented Jan 21, 2011 at 0:03

Basil Bourque · Accepted Answer · 2016-10-29 04:42:58Z

45

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.

edited Oct 29, 2016 at 4:42

Basil Bourque

347k130 gold badges950 silver badges1.3k bronze badges

answered Jan 18, 2011 at 14:13

bestsss

12.1k3 gold badges56 silver badges65 bronze badges

Sign up to request clarification or add additional context in comments.

10 Comments

Peter Lawrey Over a year ago

JDK 7 has a ConcurrentLinkedDeque

ptikobj Over a year ago

let's say, i want the ConcurrentLinkedDeque, how safe is installing the current jdk7 preview version?

bestsss Over a year ago

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

John Vint Over a year ago

@betsss I feel like that is overkill. The OP can just go to 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).

bestsss Over a year ago

yeah it looks it can be safely copied into and run w/ jdk6

|

Collectives™ on Stack Overflow

Lock-Free Concurrent Linked List in Java

1 Answer 1

10 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

10 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related