Intrusive doubly-linked list gives O(1) cancel per price level
@tylerd▲ 0 net votes
For FIFO queues at each price level, an ArrayDeque can't remove from the middle in better than O(n), and cancels (the most common message type on a venue) remove from the middle. Put prev/next pointers inside the Order object itself and keep a HashMap<orderId, Order>. A cancel then looks up the order in O(1) and unlinks it in O(1). Null out the removed node's prev/next and keep the level's totalQuantity/orderCount in sync inside the same remove method. An order can only be in one list, which is fine because it rests at one price.