How to dynamically add elements at index to Python list?

Given some Python list,

list1 = ['a', 'b', 'c', 'd', 'e', 'f', 'g']

for some of its characters contained in another list, e.g.

list2 = ['a', 'd', 'e'] 

I need to add a character {char}1 to the index right before the original character in list1, such that the updated list1 looks like this:

list1 = ['a1', 'a', 'b', 'c', 'd1', 'd', 'e1', 'e', 'f', 'g']

My initial idea was to store the indices of original elements in a dictionary, and then insert new ones to [i-1] in list1,
in range (1, len(list1)+1). However, I then realised that this would only work for the first element, because the list would then grow and the indices would shift, so I would get wrong results.

Is there an efficient way to do it using insert?

>Solution :

One approach:

list1 = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
list2 = ['a', 'd', 'e']

result = []
for e in list1:
    if e in list2:
        result.extend([f"{e}1", e])
    else:
        result.append(e)
print(result)

Output

['a1', 'a', 'b', 'c', 'd1', 'd', 'e1', 'e', 'f', 'g']

If list2 is large consider transforming it to a set. Like below:

result = []
set2 = set(list2)
for char in list1:
    if char in set2:
        result.extend([f"{char}1", char])
    else:
        result.append(char)

The second solution is O(n + m) expected, where n and m are the size of list1 and list2.

append is O(1) (this means the cost of the operation is constant), extend is a repeated append (and in the context of the question is also constant). From the documentation:

Extend the list by appending all the items from the iterable.
Equivalent to a[len(a):] = iterable.

Note: Using insert is going to make the approach O(n * m), since inserting in a list has a linear complexity (see here). The linear complexity comes from the fact that the list has to shift the elements.