Disclosure: This article may contain affiliate links. When you purchase, we may earn a small commission.

ConcurrentLinkedDeque Example in Java - A High Performance, Thread-Safe, Non-blocking Data Structure

Hello friends, we are here again today on the journey of Java, well boarded, well excited! Hope you guys are ready for being startled as today's topic is definitely going to startle you guys. Before going to discuss this topic, let me inform you that this article is in continuation of our deque article series. It's totally not mandatory to go through those articles, but it is highly recommended as they all play a part in the understanding of today's topic. So please go ahead and brush up on those articles. Now, hope you guys now have a basic understanding of what a deque is, its limitations in a multi-threaded environment, what a blocking deque is, and its limitation too. 

Today we will discuss a data structure that will overcome all of these limitations and will show the true power of Concurrency that Java provides us. But, before that, let us brush up on the past topics to understand more about why this data structure was required in the first place.

Recalling Deque and BlockingDeque in Java

Let's revisit what is Deque and what is its limitation:

1. 1 Deque 

A deque is a double-ended queue where we can add, update or delete elements from both ends. A queue can be implemented using a linked list where the element first inserted is removed first (FIFO). A singly linked list can be used to implement an unbounded queue and a doubly-linked list can be used to implement a deque.

Its limitation:
There are some limitations of Deque when considering a multi-threaded environment. Consider a scenario. Consider 3 threads simultaneously working on a Deque and both threads want to add an element at the 4th index. 

Consider a Deque where thread A and thread B both try to put an element at 4th position. Thread A wants to insert value 7 and thread B wants to insert value 9. Whichever thread accesses the deque first will put a value. 

Let’s say thread B first puts a value of 9 and then thread A comes and alters that value to 7. Now, thread A knows that the value is 7 but thread B still thinks that the value is 9. This is a classic case when one of the values gets lost due to a lack of safety during multi-threading. 

When you actually try to code this scenario using Deque, Java will throw a ConcurrentModificationException when you try to modify the Deque simultaneously from multiple threads.


1.2 Blocking Deque

BlockingDeque is a deque that is thread-safe. Multiple threads can work on the same data structure without any error or exception. But, a BlockingDeque has a lock on the data structure level. This means, whenever any operation is performed on BlockingDeque, a lock is obtained and only the thread that has a lock can modify/work on deque. 

This is very inefficient as if there are 500 threads waiting to work on deque, each has to work one-by-one after obtaining the lock.

Its limitations:
Blocking Deque puts a Structure level lock which means, all threads need to work sequentially on the Deque which is not at all efficient. Consider 3 writers and 300 readers, all would work in a sequential way when it could be more efficient considering concurrency.

This is where ConcurrentLinkedDeque comes into play. It has all the features and overcomes most of the limitations of Deque and BlockingDeque. Let us understand what it is.

2. What is ConcurrentLinkedDeque in Java?

A ConcurrentLinkedDeque is a class that provides a deque that is concurrent in nature. So, when multiple threads try to access the same deque, no exception occurs and all operations are thread-safe. Thus, this data structure is most preferred when production scenarios are considered.

ConcurrentLinkedDeque<Integer> deque = new ConcurrentLinkedDeque<>();

Some of the important points of ConcurrentLinkedDeque:
  • Concurrent insertion, removal, and access operations execute safely across multiple threads.
  • It does not permit null elements.
  • size() method is not implemented in constant time. Because of the asynchronous nature of these deques, determining the current number of elements requires a traversal of the elements.

This concurrent access is provided by Java because under the hood, this concurrency is achieved by using non-blocking techniques. This means that whenever multiple threads are performing operations on ConcurrentLinkedDeque, any of the threads will not be blocked by any other thread. 

Each thread will be working independently regardless of the other thread’s operation. This is possible because some of ConcurrentLinkedDeque’s methods are atomic.

But, some of the operations of ConcurrentLinkedDequeue are not atomic. This means that data may not be consistent while working on them. To give an example, suppose there is a thread that is traversing using forEach the deque and another thread that is performing the addAll() bulk operation.

So, in the traversal, only some of the elements may appear from the addAll operation.

3. ConcurrentLinkedDeque Example in Java

Let's see its working code. Here is a working example of ConcurrentLinkedDeque in Java. You can try this code by running gin your favorite Java IDE like Eclipse or IntelliJIDEA

import java.util.concurrent.ConcurrentLinkedDeque;

public class DequeDemo extends Thread{
public static ConcurrentLinkedDeque<Integer> deque;
public static void main(String[] args) throws InterruptedException {
deque = new ConcurrentLinkedDeque<>();

//add at last
//deque : 1

//add at first
//deque : 3 -> 1

//add at last
//deque: 3 -> 1 -> 2

//add at last
//deque : 3 -> 1 -> 2 -> 4

//remove at first
//deque : 1 -> 2 -> 4

deque.forEach(a -> System.out.print(a+"->"));
DequeDemo myClass = new DequeDemo();
Thread first = new Thread(myClass, "First thread") {
public void run() {
System.out.println("this is first thread. starting");
for(int i:deque) {
System.out.println("First thread ending");
Thread second = new Thread(myClass, "Second thread") {
public void run() {
System.out.println("this is second thread. starting");
System.out.println("This is thread 2. value added at front :"+9);


deque.forEach(a -> System.out.print(a+"->"));

ConcurrentLinkedDeque Example in Java
ConcurrentLinkedDeque output

Hope you guys have learned what to use in production, concurrent scenarios. If you have still a doubt about the use case, let's discuss it again.

When to use ConcurrentLinkedDeque in Java

Now, let’s understand the real need of this class. Is there any situation where ConcurrentLinkedDeque is used in real life? Suppose you are in a queue for buying a plane ticket. Your turn comes and you buy your ticket. 

After buying the ticket, when you are just walking away from the counter, you notice a discrepancy in your name. So you immediately go back to the counter and ask for it. You are privileged to go directly to the counter because you have purchased the ticket. 

You now have corrected the discrepancy in your name. But, meanwhile, a young person from the end of the queue feels the queue is too long and gets out of the queue. Do you know what just happened? This is exactly a Deque!
  • Insertion at front - you're going to correct the discrepancy in your name.
  • Insertion at back - normal queue operation as people want to buy tickets.
  • Removal from front - normal queue operation when people buy tickets.
  • Removal from the back - the young person getting out of the queue.

When to use ConcurrentLinkedDeque in Java

This is where, if you are designing a virtual ticket system. Virtual ticket managing platform, we would use a ConcurrentLinkedDeque.

That's all about the ConcurrntLinkedDeque in Java. It's an extremely useful, high-performance, thread-safe, and non-blocking data structure which can be used to design high-performance applications in Java. Good knowledge of Concurrent Collections goes a long way in creating better Java applications and Java developers should make every effort to learn new classes and utilities added into the newer Java versions.

Thanks for reading this article if you find these Java Dequen examples useful then please share them with your friends and colleagues. If you have any questions or feedback then please drop me a note. 

P. S. - If you are new to Java and looking for a free course to learn Java in a structured way then you can also check this Java Tutorial for Complete Beginners(FREE) course on Udemy. It's fully online, free and more than 1.4 million developers have joined this course. You just need a free Udemy account to join the course. 

No comments :

Post a Comment