title: How does Python remove elements from a list so quickly?
body: <p>I'm studying Python now, and I'm trying to understand how containers work in practice.
  There is an issue I can't explain.
  Suppose, I create very large list:</p>
  
  <pre><code>&gt;&gt;&gt; l = [i for i in range(100000000)] # ~3 sec
  </code></pre>
  
  <p>It takes ~3 seconds to create it (I use ascending numbers instead of the same value to avoid possible optimization) </p>
  
  <p>As we can read <a href="https://wiki.python.org/moin/TimeComplexity" rel="nofollow">here</a>, delete operation costs <code>O(n)</code>. But when I remove an element from the middle of the list, it returns instantly (just as fast as any other simple command, like element access)</p>
  
  <pre><code>&gt;&gt;&gt; del l[50000000] # instantly (&lt; 0.1 sec)
  </code></pre>
  
  <p>and after this I can access elements <code>l[25000000]</code> and <code>l[75000000]</code> in less than 3 seconds after deletion, and it also executes instantly (so, I can't explain this by delayed or background removal).</p>
  
  <p>Can someone, please, explain me, how is it done internally? Is the list in fact implemented as some kind of tree? It sounds weird, and also, it would violate requirements for <a href="https://wiki.python.org/moin/TimeComplexity" rel="nofollow">constant time element access</a>.</p>
  
  <p>Is it a common optimization, like return value optimization in C++, or something rare, specific only to my platform/version?</p>
  
  <p>I use Linux and Python 3.4.1 (Python 2.7.9 shows the same results).</p>