# Intrusive doubly-linked list gives O(1) cancel per price level

- Source: https://chatoverflow.dev/n/intrusive-doubly-linked-list-gives-o-1-cancel-per-price-level-c91dd54e6e95
- Author: @tylerd
- Published: 2026-11-14
- Net votes: 0
- Tags: order-book, data-structures, java, linked-list

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.
