ConcurrentLinkedDeque Example – Non-blocking Thread-safe List

In java, most used data structure is probably a list. A list has an undetermined number of elements and you can add, read, or remove the element of any position. Additionally, concurrent lists allow the various threads to add or remove elements in the list at a time without producing any data inconsistency. And non-blocking lists provide operations that, if the operation can’t be done immediately, lists throw an exception or return a null value, depending on the operation. Java 7 has introduced the ConcurrentLinkedDeque class that implements a non-blocking concurrent list and in this tutorial, we will learn to use this class.

ConcurrentLinkedDeque Example

In this example, we are going to implement an example with the following two different tasks:

1. One that adds data to a list in large amount
2. One that removes data from the same list in large amount

Let’s create the threads for each task.

package com.howtodoinjava.demo.multithreading.concurrentLinkedDequeExample;

import java.util.concurrent.ConcurrentLinkedDeque;

public class AddTask implements Runnable {

	private ConcurrentLinkedDeque<String> list;

	public AddTask(ConcurrentLinkedDeque<String> list) {
		this.list = list;
	}

	@Override
	public void run() {
		String name = Thread.currentThread().getName();
		for (int i = 0; i < 10000; i++) {
			list.add(name + ": Element " + i);
		}
	}
}

and

package com.howtodoinjava.demo.multithreading.concurrentLinkedDequeExample;

import java.util.concurrent.ConcurrentLinkedDeque;

public class RemoveTask implements Runnable {

	private ConcurrentLinkedDeque<String> list;

	public RemoveTask(ConcurrentLinkedDeque<String> list) {
		this.list = list;
	}

	@Override
	public void run() {
		for (int i = 0; i < 5000; i++) {
			list.pollFirst();
			list.pollLast();
		}
	}
}

Now, let’s create 100 threads adding data into list and 100 threads for removing data from list. If the list is truly thread-safe and non-blocking, it will give you final result almost instantly. Moreover, list size in end will be zero.

package com.howtodoinjava.demo.multithreading.concurrentLinkedDequeExample;

import java.util.concurrent.ConcurrentLinkedDeque;

public class Main {
	public static void main(String[] args) 
	{
		ConcurrentLinkedDeque<String> list = new ConcurrentLinkedDeque<>();
		Thread threads[] = new Thread[100];

		for (int i = 0; i < threads.length; i++) {
			AddTask task = new AddTask(list);
			threads[i] = new Thread(task);
			threads[i].start();
		}
		System.out.printf("Main: %d AddTask threads have been launched\n", threads.length);

		for (int i = 0; i < threads.length; i++) {
			try {
				threads[i].join();
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
		System.out.printf("Main: Size of the List: %d\n", list.size());

		for (int i = 0; i < threads.length; i++) {
			RemoveTask task = new RemoveTask(list);
			threads[i] = new Thread(task);
			threads[i].start();
		}
		System.out.printf("Main: %d RemoveTask threads have been launched\n", threads.length);

		for (int i = 0; i < threads.length; i++) {
			try {
				threads[i].join();
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
		System.out.printf("Main: Size of the List: %d\n", list.size());
	}
}

Output:

Main: 100 AddTask threads have been launched
Main: Size of the List: 1000000
Main: 100 RemoveTask threads have been launched
Main: Size of the List: 0

Let’s see how it all worked:

1. First, you have executed 100 AddTask tasks to add elements to the list. Each one of those tasks inserts 10,000 elements to the list using the add() method. This method adds the new elements at the end of the list. When all those tasks have finished, you have written in the console the number of elements of the list. At this moment, the list has 1,000,000 elements.
2. Then, you have executed 100 RemoveTask tasks to remove elements from the list. Each one of those tasks removes 10,000 elements of the list using the pollFirst() and pollLast() methods. The pollFirst() method returns and removes the first element of the list and the pollLast() method returns and removes the last element of the list. If the list is empty, these methods return a null value. When all those tasks have finished, you have written in the console the number of elements of the list. At this moment, the list has zero elements.
3. To write the number of elements of the list, you have used the size() method. You have to take into account that this method can return a value that is not real, especially if you use it when there are threads adding or deleting data in the list. The method has to traverse the entire list to count the elements and the contents of the list can change for this operation. Only if you use them when there aren’t any threads modifying the list, you will have the guarantee that the returned result is correct.

Please note that ConcurrentLinkedDeque class provides more methods to get elements form the list:

• getFirst() and getLast(): These methods return the first and last element from the list respectively. They don’t remove the returned element from the list. If the list is empty, these methods throw a NoSuchElementExcpetion exception.
• peek(), peekFirst(), and peekLast(): These methods return the first and the last element of the list respectively. They don’t remove the returned element from the list. If the list is empty, these methods return a null value.
• remove(), removeFirst(), removeLast(): These methods return the first and the last element of the list respectively. They remove the returned element from the list. If the list is empty, these methods throw a NoSuchElementException exception.
• A ConcurrentLinkedDeque is an appropriate choice when many threads will share access to a common collection.
• Like most other concurrent collection implementations, this class does not permit the use of null elements.
• Iterators are weakly consistent, returning elements reflecting the state of the deque at some point at or since the creation of the iterator. They do not throw ConcurrentModificationException, and may proceed concurrently with other operations.

Happy Learning !!