flatten an arbitrarily nested list in Python

flatten.py

from copy import deepcopy

def flatten_list(nested_list):
    """Flatten an arbitrarily nested list, without recursion (to avoid
    stack overflows). Returns a new list, the original list is unchanged.

    >> list(flatten_list([1, 2, 3, [4], [], [[[[[[[[[5]]]]]]]]]]))
    [1, 2, 3, 4, 5]
    >> list(flatten_list([[1, 2], 3]))
    [1, 2, 3]

    """
    nested_list = deepcopy(nested_list)
    
    while nested_list:
        sublist = nested_list.pop(0)

        if isinstance(sublist, list):
            nested_list = sublist + nested_list
        else:
            yield sublist

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)

<ipython-input-40-389ddf2bcf2f> in <module>
----> 1 list(flatten(l))

<ipython-input-39-35f1c7ad54a6> in flatten(arr)
      2   for i in arr:
      3     if isinstance(i, list):
----> 4       yield from flatten(arr)
      5     else:
      6       yield i

... last 1 frames repeated, from the frame below ...

<ipython-input-39-35f1c7ad54a6> in flatten(arr)
      2   for i in arr:
      3     if isinstance(i, list):
----> 4       yield from flatten(arr)
      5     else:
      6       yield i

RecursionError: maximum recursion depth exceeded

after replacing isintance with isinstance

In frizzby's code above, change line 4 from yield from flatten(arr) to yield from flatten(i). Also correct isintance to isinstance.

your solution is pretty good but the complexity of pop(0) is o(n) because you need to reorganize all the indices and the complexity you sum other list at the begin of the list and the complexity of that is o(n+m) we can improve those operations using a queue instead, the code is below

from copy import deepcopy
from collections import deque
def flatten_list(nested_list):
    """Flatten an arbitrarily nested list, without recursion (to avoid
    stack overflows). Returns a new list, the original list is unchanged.
    >> list(flatten_list([1, 2, 3, [4], [], [[[[[[[[[5]]]]]]]]]]))
    [1, 2, 3, 4, 5]
    >> list(flatten_list([[1, 2], 3]))
    [1, 2, 3]
    """
    q = deque()
    for current in nested_list:
        if isinstance(current, list):
            q.extendleft(reversed(current))
        else:
            q.appendleft(current)
        while q:
            toFlat = q.popleft()
            if isinstance(toFlat, list):
                q.extendleft(reversed(toFlat))
            else:
                yield toFlat

print(list(flatten_list([[1,2,[3,5]], 6, 7, 8, [9, [10, [11, [12]]]]])))