synchronized LinkedList - peek

Question

A LinkedList has convenient peek, pop, ... methods.

Unfortunately, I need a thread-safe LinkedList. So, my first idea was to wrap it as follows:

List<Object> list = Collections.synchronizedList(new LinkedList<>());

However, since the List interface does not contain the peek or pop methods. This doesn't work of course.

Alternatively, I could use synchronized(list) blocks all over the code. Is that the way to go ?

Any solutions that I'm overlooking ?

---

EDIT:

There are many reasons why one would use a LinkedList. I see some people are proposing other collections. So, here follow the brief requirements, which lead to my decision of using a LinkedList.

More background information:

• I'm using a LinkedList because the items need to be ordered.
• Items should be added in a non-blocking way.
• Items are added in the back ; removed from the front.
• Before the first item is removed, it first needs to be peeked and validated. If validation fails, then the item needs to stay in the list.
• Only if the validation completed successfully, then the first item is removed.
• The queue needs to have a maximum size (to avoid memory issues).

Trovillion

An implementation of BlockingQueue would be a better choice. It's designed for concurrent access, and supports peek and take (which is basically pop). – Isoelectronic

You may want to look at ConcurrentLinkedDeque. – Bloodfin

Maybe add a wrapper class around your list that has these peek/pop methods - and passes it on to the sync list? – Pippy

Or LinkedBlockingDeque – Steak

As others have noted, BlockingQueue is more appropriate, but if you must use a LinkedList (can't see why), then you have the List methods get(0) and remove(0) as equivalent to peek and pop. – Selfgovernment

Answer 1

If you need peek to work, making a synchronized wrapper may not be sufficient, so you would have to write synchronized explicitly.

It is not so much a problem with writing a wrapper as it is a problem with the semantic of the peek method. Unlike the pop method, which represents a single action, peek method is often used in a multi-component action composed of peek-ing and then doing something else based on what peek returns.

If you synchronize in a wrapper, the result would be the same as if you wrote this code manually:

String s;
synchronized(list) {
    s = list.peek();
}
// <<== Problem ==>>
if (s != null) {
    synchronized(list) {
        s = list.pop();
    }
}

This presents a problem, because there is a moment in time when your list can change in between of peek and pop (this place in code above is marked as "Problem").

A proper way to do check-and-modify is doing it in a single synchronized block, i.e.

synchronized(list) {
    String s = list.peek();
    if (s != null) {
        s = list.pop();
    }
}

However, this cannot be done in a simple wrapper, because two list operations are performed in a single synchronized block.

You can avoid writing synchronized in multiple places by building your own data structure that encapsulates a LinkedList<T>, and provides operations that perform all test-and-modify operations in a synchronized block. This is not a simple problem, however, so you may be better off changing your algorithm in a way that it could work with one of pre-defined concurrent containers.

Perutz

Yes, the key is that no builtin concurrent stack-like collection supports atomicity between "peek" and "pop" operations. You need a new method that takes a Predicate as an argument. – Steak

Answer 2

What you want is a concurrent Queue. LinkedList implements List, Deque, and Queue. The Queue is what gives it the FIFO (adding in back, remove from front) semantics with peek and pop.

A LinkedBlockingQueue can be bounded, which is one of your criteria. There are several other concurrent Queues and Deques to choose from as well.

Libelous

Isn't it the case that a LinkedBlockingQueue blocks the moment you add an item, until an item is removed on the other end ? --> that's something I try to avoid. The add should be asynchronous (i.e. non-blocking). – Trovillion

You've got it backwards. Take will block, but add is non blocking. – Libelous