 <p>If your list is sorted, then you can calculate the median in constant time with a method similar to the following pseudo-code</p> <pre><code>if list.length % 2 == 0 median = (list[list.length/2 - 1] + list[list.length/2]) / 2 else median = list[list.length/2] </code></pre> <p>Therefore, just maintain a sorted list on every insert/remove. You can do these operations in <code>O(n)</code> time by stepping through the list until you are between an element that is &lt; the added element and one that is >= the added element. You can actually do these insert/removes in <code>O(log n)</code> time if you start in the middle of the list then decide if your element is less than or greater than the middle element. Take that half-list and start in the middle of that and repeat. </p> <p>Your problem doesn't state what the performance requirements are for this but the entire thing cannot always happen in constant time as far as I am aware. This implementation has the following performance</p> <pre><code>Insert O(log n) Remove O(log n) Median O(1) </code></pre>