LinkedTransferQueue in Java
(+ Code Examples)

In this article, you will learn about a very special queue: LinkedTransferQueue. This article describes its characteristics and shows you how to use this queue with an example.

We are now at the lowest point of the queue class hierarchy:

TransferQueue Interface

As you can see in the class diagram, java.util.concurrent.LinkedTransferQueue is the only class that implements the TransferQueue interface.

TransferQueue defines additional enqueue methods that can only be executed successfully if another thread takes over the transferred item using take() or poll():

• transfer(E e) – passes the element to a thread that is waiting for an element with take() or poll(). If such a thread does not exist, the method blocks until another thread calls take() or poll().
• tryTransfer(E e) – passes the element to a thread that is waiting for an element using take() or poll(). If such a thread does not exist, the method immediately returns false.
• tryTransfer(E e, long timeout, TimeUnit unit) – passes the element to a thread that is waiting for an element using take() or poll(). If such a thread does not exist and does not appear within the waiting time, the method returns false.

LinkedTransferQueue Characteristics

LinkedTransferQueue is an unbounded blocking queue, i.e., the regular enqueue operations put() and offer() cannot block (since the queue can grow to any size). Blocking, however, can:

• the dequeue operations (when the queue is empty),
• and the transfer() or tryTransfer() methods of the TransferQueue interface until the respective elements are retrieved.

LinkedTransferQueue is based on a singly linked list. As a result, the time complexity of the size() method is O(n) (and not O(1) as in the array-based queues)¹, since the entire list must be traversed to determine its length.

Thread safety is achieved through non-blocking compare-and-set (CAS) operations, ensuring high performance with low to moderate contention (access conflicts through multiple threads).

The characteristics in detail:

¹ You can learn about time complexity in the article "Big O Notation and Time Complexity – Easily Explained".

² Weakly consistent: All elements that exist when the iterator is created are traversed by the iterator exactly once. Changes that occur after this can, but do not need to, be reflected by the iterator.

Recommended Use Case

LinkedTransferQueue is not used in the JDK. Initially, it was implemented for the fork/join framework introduced in JDK 7 but was not used for it after all. Therefore, the probability of bugs is relatively high, so you should refrain from using this class.

LinkedTransferQueue Example

In the following example (→ code on GitHub), we start two threads that call LinkedTransferQueue.transfer(). After that, one element is written directly to the queue. Then, we create two more threads that call transfer(). Finally, we remove elements from the queue until it is empty again.

public class LinkedTransferQueueExample {
  public static void main(String[] args) throws InterruptedException {
    TransferQueue<Integer> queue = new LinkedTransferQueue<>();

    // Start 2 threads calling queue.transfer(),
    startTransferThread(queue, 1);
    startTransferThread(queue, 2);

    // ... then put one element directly,
    enqueueViaPut(queue, 3);

    // ... then start 2 more threads calling queue.transfer().
    startTransferThread(queue, 4);
    startTransferThread(queue, 5);

    // Now take all elements until the queue is empty
    while (!queue.isEmpty()) {
      dequeueViaTake(queue);
    }
  }

  private static void startTransferThread(TransferQueue<Integer> queue, int element)
      throws InterruptedException {
    new Thread(() -> enqueueViaTransfer(queue, element)).start();

    // Wait a bit to let the thread enqueue the element
    Thread.sleep(100);
    log("                            --> queue = " + queue);
  }

  private static void enqueueViaTransfer(TransferQueue<Integer> queue, int element) {
    log("Calling queue.transfer(%d)...", element);
    try {
      queue.transfer(element);
      log("queue.transfer(%d) returned  --> queue = %s", element, queue);
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
    }
  }

  private static void enqueueViaPut(TransferQueue<Integer> queue, int element)
      throws InterruptedException {
    log("Calling queue.put(%d)...", element);
    queue.put(element);
    log("queue.put(%d) returned       --> queue = %s", element, queue);
  }

  private static void dequeueViaTake(TransferQueue<Integer> queue)
      throws InterruptedException {
    log("    Calling queue.take() (queue = %s)...", queue);
    Integer e = queue.take();
    log("    queue.take() returned %d --> queue = %s", e, queue);

    // Wait a bit to get the log output in a readable order
    Thread.sleep(10);
  }

  private static void log(String format, Object... args) {
    System.out.printf(
        Locale.US, "[%-8s] %s%n",
        Thread.currentThread().getName(),
        String.format(format, args));
  }
}Code language: Java (java)

Below you can see the output of the program:

[Thread-0] Calling queue.transfer(1)...
[main    ]                             --> queue = [1]
[Thread-1] Calling queue.transfer(2)...
[main    ]                             --> queue = [1, 2]
[main    ] Calling queue.put(3)...
[main    ] queue.put(3) returned       --> queue = [1, 2, 3]
[Thread-2] Calling queue.transfer(4)...
[main    ]                             --> queue = [1, 2, 3, 4]
[Thread-3] Calling queue.transfer(5)...
[main    ]                             --> queue = [1, 2, 3, 4, 5]
[main    ]     Calling queue.take() (queue = [1, 2, 3, 4, 5])...
[main    ]     queue.take() returned 1 --> queue = [2, 3, 4, 5]
[Thread-0] queue.transfer(1) returned  --> queue = [2, 3, 4, 5]
[main    ]     Calling queue.take() (queue = [2, 3, 4, 5])...
[main    ]     queue.take() returned 2 --> queue = [3, 4, 5]
[Thread-1] queue.transfer(2) returned  --> queue = [3, 4, 5]
[main    ]     Calling queue.take() (queue = [3, 4, 5])...
[main    ]     queue.take() returned 3 --> queue = [4, 5]
[main    ]     Calling queue.take() (queue = [4, 5])...
[main    ]     queue.take() returned 4 --> queue = [5]
[Thread-2] queue.transfer(4) returned  --> queue = [5]
[main    ]     Calling queue.take() (queue = [5])...
[main    ]     queue.take() returned 5 --> queue = []
[Thread-3] queue.transfer(5) returned  --> queue = []Code language: plaintext (plaintext)

You can see nicely how, in the beginning, transfer() is called twice (but does not return), how then put() is called once (and returns), and how transfer() is called two more times (and does not return).

After that, we see how the first element is taken, and subsequently transfer(1) returns as well.

Then the second element is taken, and transfer(2) returns.

The removal of the 3 does not lead to any further action, since it was written to the queue with put().

After removing the 4 and the 5, you can again see nicely how the respective transfer() call returns.

Summary and Outlook

In this article, you learned about the TransferQueue interface and LinkedTransferQueue implementation and saw how to use them with an example.

In the next part of this tutorial series, you will find a summary of all queue implementations of the JDK and an overview of in which cases you should use which implementation.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.