Concurrent Queues and Skip Lists: Lock-Free Ends and Concurrent Order

Workers that must wait for the next order id belong on a BlockingQueue. Workers that should take work if any is there, and otherwise do something else, need a queue that does not block. Sorted keys under concurrent writers need a navigable map that is not a locked TreeMap.

This post is those two jobs: lock-free concurrent queues, and concurrent skip lists. They are not interchangeable with ConcurrentHashMap and they are not BlockingQueue.

The series hub owns weakly consistent iterators. Both families here use that contract: no ConcurrentModificationException, and a later offer / put may or may not show up in a walk that already started. The lab is still checkout: queue of Order.id, map of Order by id.

public record LineItem(String sku, int quantity, BigDecimal unitPrice) {}

public record Order(
        String id,
        String customerEmail,
        List<LineItem> items,
        BigDecimal total,
        boolean active) {}

ConcurrentLinkedQueue: unbounded, lock-free, no take

ConcurrentLinkedQueue is an unbounded FIFO Queue. Offers and polls at the ends are lock-free. There is no blocking take. Empty means poll() returns null.

Queue<String> ready = new ConcurrentLinkedQueue<>();
ready.offer("o-100");
ready.offer("o-101");

String id = ready.poll(); // "o-100"
String empty = ready.poll(); // null if another worker already took o-101 — does not wait

offer always returns true (the queue is unbounded). add is the same success path. Null elements are forbidden.

ready.offer(null); // NullPointerException

A worker that must park until an id arrives wanted BlockingQueue.take(), not this type. Busy-looping poll() until it is non-null is the bug the blocking family exists to prevent.

// wrong: this is a spin, not a hand-off
String id;
while ((id = ready.poll()) == null) {
    // burns a core
}

Use ConcurrentLinkedQueue when many threads offer and poll, a miss is a null you can handle, and you do not want a lock around an ArrayDeque. Typical picture: a thread checks the queue between other work, or you already have your own park/unpark story.

A warehouse thread that also answers HTTP can drain what is there and then return:

ConcurrentMap<String, Order> byId = new ConcurrentHashMap<>();
Queue<String> ready = new ConcurrentLinkedQueue<>();

void submit(Order order) {
    byId.put(order.id(), order);
    ready.offer(order.id());
}

int pickAvailable(int max) {
    int picked = 0;
    String id;
    while (picked < max && (id = ready.poll()) != null) {
        Order order = byId.get(id);
        if (order != null) {
            System.out.println("pick " + order.id());
        }
        picked++;
    }
    return picked; // 0 means “nothing waiting” — go do other work
}

peek() looks at the head without removing it. Under concurrent polls it can return an id another worker already took, or null a moment before an offer lands. Treat peek as a hint, not a reservation.

ConcurrentLinkedDeque: both ends, still non-blocking

ConcurrentLinkedDeque is the two-ended version. Lock-free. Unbounded. No nulls. pollFirst / pollLast return null when that end is empty — they do not wait.

Deque<String> ends = new ConcurrentLinkedDeque<>();
ends.offerLast("o-100");
ends.offerFirst("o-urgent");
String next = ends.pollFirst(); // o-urgent
String last = ends.pollLast();  // o-100

Urgent picks at the front, ordinary ids at the back — same shape as LinkedBlockingDeque, without blocking. If the worker should sleep until either end has work, you wanted the blocking deque.

offerFirst / offerLast always succeed (unbounded). pollFirst / pollLast / peekFirst / peekLast return null on an empty end. getFirst() / removeFirst() throw NoSuchElementException when empty — same Queue split as element / remove vs peek / poll. Prefer the poll* forms on a shared deque so a miss is a value, not an exception.

Iterators on both the queue and the deque are weakly consistent. A for-each may observe an id offered after the iterator was created. It will not throw CME. That is not a snapshot and not a freeze of the pick line.

for (String orderId : ready) {
    System.out.println(orderId); // a concurrent offer may appear; a concurrent poll may not
}

size() is O(n) and not a snapshot

ConcurrentLinkedQueue.size() and ConcurrentLinkedDeque.size() walk the nodes. They are not a field read.

int n = ready.size(); // traverses; another thread may offer or poll during the walk

The javadoc warning is literal: this is not a constant-time size, and a concurrent modification can make the count stale or briefly inconsistent. Do not call size() on the hot path to decide whether to poll. isEmpty() is the cheaper question, and even that is racy under concurrent polls — treat it as a hint.

toArray / iteration have the same weakly consistent story. If you need “exactly these ids, now,” drain into a local list from one thread, or use a blocking drainTo on a BlockingQueue.

When you needed blocking, you wanted BlockingQueue

Need	Type
Wait for the next id	`BlockingQueue.take` / `poll(timeout)`
Bounded buffer / backpressure	`ArrayBlockingQueue` or capped `LinkedBlockingQueue`
Rendezvous (no buffer)	`SynchronousQueue`
Work if present, else skip	`ConcurrentLinkedQueue.poll` → `null`
Shared unsorted map	`ConcurrentHashMap`
Shared sorted map	`ConcurrentSkipListMap`

ConcurrentLinkedQueue has no take. Calling it is a compile error. That confusion is the interview trap: people remember “concurrent queue” and invent a blocking method from LinkedBlockingQueue.

Keep the catalog in a ConcurrentHashMap. Keep waiting workers on a BlockingQueue. Keep opportunistic workers on ConcurrentLinkedQueue.

Call	`ConcurrentLinkedQueue`	`BlockingQueue`
`offer(e)`	always `true` (unbounded)	`false` if a bounded queue is full
`poll()`	`null` if empty, no wait	`null` if empty, no wait
`take()`	does not exist	waits for an element
`put(e)`	does not exist	waits for space
`drainTo`	not on `Queue`; iterate/`poll` yourself	yes

peek() on CLQ is the same non-blocking look as poll without removing. It is still racy under concurrent consumers.

Note: ConcurrentLinkedQueue is a Queue, not a BlockingQueue. Assigning it to a BlockingQueue variable does not compile. That is how you notice there is no take.

ConcurrentSkipListMap: concurrent sorted map

TreeMap is not safe to share. Collections.synchronizedSortedMap locks the whole tree. ConcurrentHashMap is shared and fast and unsorted.

ConcurrentSkipListMap is a concurrent NavigableMap. Keys stay ordered. Expected get / put / remove / containsKey are O(log n). No null keys, no null values. Iterators are weakly consistent.

The layout — layered forward pointers, coin-flip height — lives in Skip Lists. Comparator / NavigableMap methods (ceiling, floor, subMap) live in Navigable Collections. This post is the concurrent pick: use it when more than one thread mutates a sorted map.

ConcurrentNavigableMap<String, Order> byId = new ConcurrentSkipListMap<>();
byId.put("o-100", new Order(
        "o-100",
        "ada@ex.com",
        List.of(new LineItem("SKU-1", 1, new BigDecimal("9.99"))),
        new BigDecimal("9.99"),
        true));
byId.put("o-101", new Order("o-101", "grace@ex.com", List.of(), BigDecimal.ZERO, true));

Order atOrAfter = byId.ceilingEntry("o-100").getValue();
ConcurrentNavigableMap<String, Order> tail = byId.tailMap("o-101");

Natural String order is fine for opaque ids if you only need a concurrent sorted view. For “next order by total,” you need a comparator on a key that actually sorts that way — or a different structure. Do not pretend ConcurrentHashMap iteration order is sorted.

Range views are concurrent and weakly consistent, like the map:

Order floor = Optional.ofNullable(byId.floorEntry("o-100"))
        .map(Map.Entry::getValue)
        .orElse(null);
NavigableSet<String> ids = byId.keySet();
String nextId = ids.higher("o-100"); // o-101, or null

subMap / tailMap / headMap stay attached to the live map. A put of o-102 from another thread can appear in a tailMap you already hold. They are not a snapshot export. Copy to a local TreeMap if you need a frozen range.

putIfAbsent, computeIfAbsent, and replace exist here too. They are still per key. The cost is O(log n), not a CHM bin CAS. Use them when the map must stay sorted; do not switch to a skip list just to get compute.

ConcurrentSkipListSet is the set counterpart (a skip-list map with dummy values). Unique sorted elements, concurrent, no nulls.

ConcurrentNavigableSet<String> skus = new ConcurrentSkipListSet<>();
skus.add("SKU-1");
skus.add("SKU-2");
String first = skus.pollFirst(); // SKU-1; non-blocking, null if empty

pollFirst / pollLast on the set and map views remove an end. They do not wait. Empty is null (map entry) or null (set element) — same non-blocking story as ConcurrentLinkedQueue.poll.

A worker that wants “the next id in sort order, if any” can poll the skip-list key set without blocking:

ConcurrentNavigableMap<String, Order> open = new ConcurrentSkipListMap<>();
open.put("o-100", new Order("o-100", "ada@ex.com", List.of(), new BigDecimal("9.99"), true));
open.put("o-101", new Order("o-101", "grace@ex.com", List.of(), BigDecimal.ZERO, true));

Map.Entry<String, Order> head = open.pollFirstEntry(); // o-100, gone from the map
if (head != null) {
    System.out.println("pick " + head.getValue().id());
}

pollFirstEntry is not BlockingQueue.take. If the map is empty, you get null and do other work.

Skip list vs TreeMap vs ConcurrentHashMap

Type	Threads	Order	Expected cost	Nulls
`TreeMap`	one thread	sorted	`O(log n)`	no null key (natural order)
`synchronizedSortedMap(TreeMap)`	whole-map lock	sorted	`O(log n)` plus the mutex	same as backing
`ConcurrentSkipListMap`	concurrent	sorted	`O(log n)`	no
`ConcurrentHashMap`	concurrent, per-bin	none	expected `O(1)` get/put	no

Plain shared get/put: ConcurrentHashMap. Shared sorted keys, ceiling, range views: ConcurrentSkipListMap. One thread and sorted: TreeMap.

size() on the skip-list map is not a cheap field. Like the concurrent linked queue, counting may traverse. Do not use it as a heartbeat on the hot path.

A skip list is not a HashMap. Hashing is the HashMap post. Here the key property is order under concurrent writers, paid for with logarithmic hops instead of a bin.

Constructor with a Comparator is how you sort by something other than Comparable keys. The comparison must stay consistent with equals, same rule as TreeMap — the navigable post owns that contract. A comparator that only looks at Order.total while the key is Order.id is the wrong map: the skip list orders keys, not values. If you need “highest total under writers,” wrap a total into the key or keep a PriorityBlockingQueue of work, not a skip list of ids.

Interview lens

Interviewers want “does poll wait?”, size() cost, and which sorted map is safe to share.

Question	Honest answer
`ConcurrentLinkedQueue` vs `BlockingQueue`?	CLQ never blocks; `poll` returns `null`. Blocking queues have `take` / `put` that wait.
`ConcurrentLinkedQueue.take()`?	There is no `take`. That method is on `BlockingQueue`.
`size()`?	`O(n)` walk on CLQ / CLD; not snapshot-accurate under concurrent offers and polls.
Skip list vs `TreeMap` vs CHM?	Skip list: concurrent + sorted. `TreeMap`: sorted, one thread. CHM: concurrent, unsorted, usually faster get/put.
Nulls?	No nulls on CLQ, CLD, skip-list map/set.
Iterator?	Weakly consistent on these types — no CME, may see later updates.

Wrong answer: “ConcurrentLinkedQueue.take() waits for an element.” There is no take. Waiting is BlockingQueue. poll returns null immediately.

Cheat sheet

ConcurrentLinkedQueue    unbounded FIFO; lock-free; poll() -> null; no take
ConcurrentLinkedDeque    both ends; same non-blocking / no-nulls story
size()                   O(n); racy under concurrent mutation
Iterators                weakly consistent; no CME

ConcurrentSkipListMap    concurrent NavigableMap; expected O(log n); no nulls
ConcurrentSkipListSet    concurrent NavigableSet; same layout
vs TreeMap               TreeMap is not shared
vs CHM                   CHM unsorted and usually faster for get/put

Do     CLQ when miss is null; skip list when shared keys must sort
Don't  spin on poll(); invent take() on CLQ; skip list as a HashMap

Do:

Use ConcurrentLinkedQueue / Deque for non-blocking ends.
Use ConcurrentSkipListMap when a shared map must stay sorted.
Leave waiting workers on BlockingQueue and unsorted shared maps on ConcurrentHashMap.

Don’t:

Call take on a concurrent linked queue — it is not there; do not fake it with a spin.
Trust size() as a snapshot or as an O(1) counter.
Share a TreeMap because “it is sorted.”

Wrap-up

ConcurrentLinkedQueue and ConcurrentLinkedDeque are lock-free, unbounded, and non-blocking: poll returns null, iterators are weakly consistent, size() walks the chain. When the worker must wait, that was a BlockingQueue. ConcurrentSkipListMap and ConcurrentSkipListSet are the concurrent sorted types — logarithmic, no nulls, an alternative to TreeMap when another thread writes. Unsorted shared maps stay on ConcurrentHashMap. The next step in the series is how a collection splits for a stream and how collectors put it back together.

Next optional step in the series Split a collection for a stream, then collect it back into a list, map, or concurrent structure. Spliterator and Collectors: Split a Collection and Put It Back Together

Concurrent Queues and Skip Lists:Lock-Free Ends and Concurrent Order

ConcurrentLinkedQueue: unbounded, lock-free, no take

ConcurrentLinkedDeque: both ends, still non-blocking

size() is O(n) and not a snapshot

When you needed blocking, you wanted BlockingQueue

ConcurrentSkipListMap: concurrent sorted map

Skip list vs TreeMap vs ConcurrentHashMap

Interview lens

Cheat sheet

Wrap-up

Pick the Collection:Nulls, Order, Threads, and the Hot Operation

Sequenced Collections:First, Last, and Reversed Without the Ceremony

Stream Gatherers:Custom Intermediate Ops Without Breaking the Pipeline

Java Streams:Filter, Map, and Collect Without the Nested Loop Soup

ConcurrentLinkedQueue: unbounded, lock-free, no take

ConcurrentLinkedDeque: both ends, still non-blocking

size() is O(n) and not a snapshot

When you needed blocking, you wanted BlockingQueue

ConcurrentSkipListMap: concurrent sorted map

Skip list vs TreeMap vs ConcurrentHashMap

Interview lens

Cheat sheet

Wrap-up

Related posts

Pick the Collection:Nulls, Order, Threads, and the Hot Operation

Sequenced Collections:First, Last, and Reversed Without the Ceremony

Stream Gatherers:Custom Intermediate Ops Without Breaking the Pipeline

Java Streams:Filter, Map, and Collect Without the Nested Loop Soup