Question about `list.insert`

[Dan Stromberg]

On Thu, Feb 6, 2014 at 3:59 PM, cool-RR <ram.rachum at gmail.com> 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?

I'm pretty sure it'll slide all the existing elements right one
position, and add at the leftmost position just opened up - assuming
you're inserting at position 0.

As was already mentioned, collections.deque is good for this sort of
thing.  It's implemented as a fancy doubly-linked list. Or rather, a
doubly-linked list of smallish arrays/lists.

For a singly-linked list:
http://stackoverflow.com/questions/280243/python-linked-list
http://stromberg.dnsalias.org/~strombrg/linked-list/

HTH