Python list insert

Python list is a dynamic data structure and it supports append, insert, pop, remove, extend out of all these operations insert is a bit complicated since it has to perform a lot of data movement.

This is a simple tip to use while inserting huge list into another huge list.

Generally list.insert() works in this way, if list l1 size is n (imagine that this n is huge) and if you try to add another huge list l2 of values from the beginning lets say from position 2 l1.insert(2, val) this should move all the other elements of list l1 from 2 to n - 1 to next positions for every insert.

Lets consider your lists l1 , l2 and we’ve to insert all the l2 values into l1 from the index 2.

>>> l1 = range(1, 10)
>>> l2 = range(10, 20)
>>> l1
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> l2
[10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

After inserting the l2 into l1 with the below way…….

>>> i = 2
>>> for j in l2:
...     l1.insert(i, j)
...     i += 1
>>> l1
[1, 2, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 3, 4, 5, 6, 7, 8, 9]

In the above way of inserting for every insert the values 3, 4, 5, 6, 7, 8, 9 in l1 has been moved to next positions after proper list.resize. Assume that what will heppen if your ‘l1’ size is of ten million this movement of values becomes a overhead.

We can avoid this by inserting from the ending by reversing both the l1 and l2.

To avoid this data movement within the list for every insert, you can insert values from the end, in your case you’ve to reverse the list l1 and l2 and do l1.insert(-2, l2.val)

>>> l1
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> l2
[10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
>>> l1.reverse()
>>> l2.reverse()
>>> l1
[9, 8, 7, 6, 5, 4, 3, 2, 1]
>>> l2
[19, 18, 17, 16, 15, 14, 13, 12, 11, 10]
>>> for i in l2:
...     l1.insert(-2, i)
... 

After inserting you’ll get this ..

>>> l1
[9, 8, 7, 6, 5, 4, 3, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 2, 1]

If you observe the data movement happened in this way of inserting, only values 2, 1 has been moved all the time while inserting the values of l2.

You can simply reverse the l1 to get the desired list of values.

>>> l1.reverse()
>>> l1
[1, 2, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 3, 4, 5, 6, 7, 8, 9]

in this way we can avoid the most happening data movement in list.insert().

Time Stats: https://ideone.com/owzWza

Note: This whole solution works well for inserting at the beginning, but in case if you’ve insert some value at the middle of the list you’ve slicing like below.

list[position_where_to_insert:position_where_to_insert]

Below is the example to insert all the values of list l1 into list l at position 2.

>>> l = [1, 2, 3]
>>> l1 = range(10)
>>> l[2:2] = l1
>>> l
[1, 2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 3]

Published: July 26 2015

  • category:
blog comments powered by Disqus