List Flatten

Raymond Hettinger vze4rx4y at
Mon Oct 18 10:42:04 CEST 2004

"bearophile" <bearophileHUGS at> wrote :
> This program works for very deep lists too, without giving Stack
> overflow like the recursive version (and it's faster than the
> recursive version).

Here is a non-recursive version using generators.  It runs in O(n) time and is
memory friendly (consuming space proportional to the depth of the input).  It
has one additional feature, strings are kept whole instead of iterating them
into characters.

>>> def f(n):
    iterstack = [iter(n)]
    while iterstack:
        for elem in iterstack[-1]:
                it = iter(elem)
            except TypeError:
                if not isinstance(elem, basestring):
            yield elem
            iterstack.pop()  # remove iterator only when it is exhausted

>>> n = [['ab', 2, [], [3, 5, (2,1), [4]]]]
>>> print list(f(n))
['ab', 2, 3, 5, 2, 1, 4]

Raymond Hettinger

More information about the Python-list mailing list