Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed4a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <python-python-list@m.gmane.org>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.002
X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'cpython': 0.05; 'mrab': 0.05; 'skip:` 10': 0.07; 'subject:Question': 0.07; 'append': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'python': 0.11; 'jan': 0.12; 'curious.': 0.16; 'received:80.91.229.3': 0.16; 'received:plane.gmane.org': 0.16; 'reedy': 0.16; 'subject:`': 0.16; 'wrote:': 0.18; 'items.': 0.19; 'memory': 0.22; 'proposed': 0.22; 'header:User-Agent:1': 0.23; 'header:X-Complaints-To:1': 0.27; 'header:In-Reply-To:1': 0.27; 'needed.': 0.30; "i'm": 0.30; '(which': 0.31; 'usually': 0.31; 'apparently': 0.31; 'lists': 0.32; 'there,': 0.34; 'knows': 0.35; 'there': 0.35; 'really': 0.36; 'hi,': 0.36; 'list': 0.37; 'to:addr:python-list': 0.38; 'pm,': 0.38; 'to:addr:python.org': 0.39; 'received:org': 0.40; 'space': 0.40; 'entire': 0.61; 'received:173': 0.61; 'first': 0.61; 'more': 0.64; 'kept': 0.65; 'saving': 0.69; 'moves': 0.84; 'received:fios.verizon.net': 0.84
X-Injected-Via-Gmane: http://gmane.org/
To: python-list@python.org
From: Terry Reedy <tjreedy@udel.edu>
Subject: Re: Question about `list.insert`
Date: Thu, 06 Feb 2014 21:48:36 -0500
References: <4041bba7-91bc-4803-9150-2fcf14ecb5a9@googlegroups.com> <52F42BDC.7000907@mrabarnett.plus.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
X-Gmane-NNTP-Posting-Host: pool-173-75-254-207.phlapa.fios.verizon.net
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.3.0
In-Reply-To: <52F42BDC.7000907@mrabarnett.plus.com>
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.6470.1391741345.18130.python-list@python.org>
Lines: 22
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1391741345 news.xs4all.nl 2865 [2001:888:2000:d::a6]:50550
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:65574

On 2/6/2014 7:42 PM, MRAB wrote:
> On 2014-02-06 23:59, cool-RR wrote:
>> Hi,
>>
>> I'm curious. If I append an item to a list from the left using
>> `list.insert`, will Python always move the entire list one item to
>> the right (which can be super-slow) or will it check first to see
>> whether it can just allocate more memory to the left of the list and
>> put the item there, saving a lot of resources?
>>
> If it needs more space it resizes. It then moves the items.

The OP apparently knows that there is usually extra space at the right 
(end), so that reallocation is usually not needed. He wanted to know 
whether extra space is also kept at the left (beginning) to make left 
appends as efficient as right appends. This has been proposed and the 
answer was to use collections.deque if it really matters. CPython lists 
are asymmetric re-sizable stacks

-- 
Terry Jan Reedy