Time complexity of storing priority queue as a doubly linked list

Question

If I want to store a priority queue as a sorted doubly-linked list then aren't the following time complexities correct?

• Insert a new entry: O(n)

  Because I'd have to iterate over each element of the linked-list to find out where it should be inserted so that my list is always sorted.

• Get element with max priority: O(1)

  I can keep my list sorted in ascending/descending order of priority and save the head & tail of the list. If this is true, then getting the element with max priority should be O(1) because we know its location.

• Remove element with max priority: O(1)

  Same logic as above

Answer 1

Besides the fact, that a priority queue using linked lists is a somewhat inefficient idea (you can make the worst runtime complexity log(n()), your numbers are right.

You could make a destiction here though: "Insert a new entry: O(n)"

Technically, the insertion is O(1), finding the correct position is what takes you O(n). So basically, when you add 7 identical items, it will not take you 7 times the amount of time, because you need the lookup just once.