On 29 Apr 2020, at 12:36, remi.lapeyre@henki.fr wrote:
Also, removing an element from a doubly-linked list is not a O(1) operation, it's O(n). It's O(1) once you have a pointer to the element but you have to iterate over the list to get it and that would take O(n) operations, so making deque a doubly-linked list would not be faster anyway.
In the cases where a DLL is the reasonable design choice remove is O(1) in my experience. The reason is that you have the element in your hand by other means then scanning the DLL. This was a heavily used pattern when I worked on DEC VMS device drivers. Async I/O requests could be cancelled and removed from the list of outstanding I/O for a device in O(1). Indeed the VAX had instructions to implement this pattern in hardware. Barry