LinkedList Vs ConcurrentLinkedQueue

Question

Currently in a multithreaded environment, we are using a LinkedList to hold data. Sometimes in the logs we get NoSuchElementException while it is polling the linkedlist. Please help in understanding the performance impact if we move from the linkedlist to ConcurrentLinkedQueue implementation.

Thanks, Sachin

Answer 1

When you get a NoSuchElementException then this maybe because of not synchronizing properly. For example: You're checking with it.hasNext() if an element is in the list and afterwards trying to fetch it with it.next(). This may fail when the element has been removed in between and that can also happen when you use synchronized versions of Collection API.

So your problem cannot really be solved with moving to ConcurrentLinkedQueue. You may not getting an exception but you've to be prepared that null is returned even when you checked before that it is not empty. (This is still the same error but implementation differs.) This is true as long as there is no proper synchronization in YOUR code having checks for emptiness and element retrieving in the SAME synchronized scope.

There is a good chance that you trade NoSuchElementException for having new NullPointerException afterwards.

This may not be an answer directly addressing your question about performance, but having NoSuchElementException in LinkedList as a reason to move to ConcurrentLinkedQueue sounds a bit strange.

Edit

Some pseudo-code for broken implementations:

//list is a LinkedList
if(!list.isEmpty()) {
    ... list.getFirst()
}

Some pseudo-code for proper sync:

//list is a LinkedList
synchronized(list) {
    if(!list.isEmpty()) {
        ... list.getFirst()
    }
}

Some code for "broken" sync (does not work as intended). This maybe the result of directly switching from LinkedList to CLQ in the hope of getting rid of synchronization on your own.

//queue is instance of CLQ
if(!queue.isEmpty()) { // Does not really make sense, because ...
    ... queue.poll() //May return null! Good chance for NPE here!
}

Some proper code:

//queue is instance of CLQ
element = queue.poll();

if(element != null) {
   ...
}

or

//queue is instance of CLQ
synchronized(queue) {
    if(!queue.isEmpty()) {
        ... queue.poll() //is not null
    }
}