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

cool stuff 👍

nicely done. I believe this could be extended to arbitrary iterables.

If a list is very long, but not very deep this solution will no be optimal.
Consider this instead:

def flatten(arr):
  for i in arr:
    if isintance(i, list):
      yield from flatten(arr)
    else:
      yield i

---------------------------------------------------------------------------
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]]]]])))