What is the time complexity of inserting an element into the middle of a doubly linked list?

Inserting an element into the middle of a doubly linked list usually requires first finding the insertion position, which takes O(n) time, as you need to traverse the list to the desired node.

The actual insertion process (changing pointers of neighboring nodes) is performed in O(1).

In total:

• Finding the position — O(n)
• Insertion — O(1)

If the position is already known (for example, you have a pointer to the node), then the insertion will be O(1). If not — you need to traverse the list first, which gives O(n).