In the JavaDoc of the LinkedBlockingDeque, it states that iterator.remove() is an example of a linear time method. Since the LBD needs Node with pointers for prev and next, this method would typically execute in constant time. The comment should be changed to reflect this.