Why does Python take O(n) time to remove the first element from a list?
<p>The <a href="https://wiki.python.org/moin/TimeComplexity" rel="nofollow">Python wiki page on time complexity</a> says that deleting an item takes O(n) time. The <a href="https://docs.python.org/3/library/collections.html#collections.deque" rel="nofollow">description of the deque class in the documentation of the collections module</a> says that "<code>list</code> objects [...] incur O(n) memory movement costs for <code>pop(0)</code> and <code>insert(0, v)</code> operations which change both the size and position of the underlying data representation".</p>

<p>Why do lists need O(n) time? Isn't a list just a bunch of elements, or pointers to elements, physically next to each other in memory, along with a pointer to where the list starts? If so, why can't the <code>list</code> type have a <a href="https://docs.python.org/3/library/collections.html#collections.deque.popleft" rel="nofollow"><code>popleft</code></a> method, similar to the one in <code>collections.deque</code>, that removes the first element in O(1) time by appropriately incrementing the start pointer of the list?</p>

<p>I am not trying to solve any specific problem. I just want to satisfy my curiosity as to why it is designed that way.</p>

<p><strong>EDIT:</strong> Here is a diagram of how my <code>popleft</code> method would work:</p>

<p><strong>Before calling <code>popleft</code>:</strong></p>

<pre><code>-------------------------------------------------------------------
|    The   |  quick   |  brown   |   fox    |  jumps   |   over   |
-------------------------------------------------------------------
      ^
      pointer to list
</code></pre>

<p><strong>After calling <code>popleft</code>:</strong></p>

<pre><code>-------------------------------------------------------------------
|    The   |  quick   |  brown   |   fox    |  jumps   |   over   |
-------------------------------------------------------------------
                 ^
                 pointer to list
</code></pre>

<p>Before the call to <code>popleft</code>, the first element of the list is <code>The</code>, the 2nd is <code>quick</code>, etc. After the call, the place where the first element was is now unused memory (which may be left empty or claimed by the garbage collector), the new first element is <code>quick</code>, the new 2nd element is <code>brown</code>, etc. No large amount of data needs to be moved, and nothing needs to happen that takes O(n) time.</p>