How to dynamically add elements at index to Python list?-CodePudding

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?

CodePudding user response：

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.

CodePudding user response：

you can use a while loop and the enumerate function to achieve the same result.

index = 0
list1 = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
list2 = ['a', 'd', 'e'] 
while index < len(list1):
    # Get the current character and its index
    char, i = list1[index], index
    if char in list2:
        list1.insert(i, char   '1')
        index  = 2
    else:
        index  = 1

print(list1)

CodePudding user response：

An alternative approach with insert:

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


for e in list2:
    list1.insert(list1.index(e), f'{e}1')

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