5 Best Ways to Flatten a List in Python Without Using Recursion

Rate this post

💡 Problem Formulation: In Python programming, a common challenge is to convert a nested list, with multiple levels of sublists, into a single flattened list with all the elements in order. For example, given the input [[1, 2, [3]], 4], the desired output is [1, 2, 3, 4]. This article demonstrates five methods to achieve this without relying on recursion.

Method 1: Using a Stack

The stack method iterates through each element in the input list. If the element is not a list, it’s appended to the result list. If the element is a list, it’s extended onto the top of the stack for further exploration. This non-recursive approach mimics the depth-first search algorithm.

Here’s an example:

def flatten_with_stack(lst):
    stack = list(reversed(lst))
    flat_list = []
    while stack:
        elem = stack.pop()
        if isinstance(elem, list):
            stack.extend(reversed(elem))
        else:
            flat_list.append(elem)
    return flat_list

nested_list = [[1, 2, [3]], 4]
flattened = flatten_with_stack(nested_list)
print(flattened)

Output:

[1, 2, 3, 4]

This code begins by reversing the input list to use it as a stack. It then repeatedly pops elements from the stack. If an element is a sublist, it is extended in reversed order onto the stack, otherwise, it is appended to flat_list. The process continues until the stack is empty.

Method 2: Using a While Loop with a Temporary List

This method involves iterating over the original list and appending non-list elements to a new list. If a list element is encountered, its items are added to a temporary list, which is then concatenated to the end of the original list for further processing.

Here’s an example:

def flatten_with_while_loop(lst):
    i = 0
    while i < len(lst):
        while isinstance(lst[i], list):
            lst[i:i+1] = lst[i]
        i += 1
    return lst

nested_list = [[1, 2, [3]], 4]
flattened = flatten_with_while_loop(nested_list)
print(flattened)

Output:

[1, 2, 3, 4]

As the function iterates, it checks whether the current element is a list. If so, it expands that list in place, replacing the single sublist element. The process is repeated until all sublists have been merged into the main list.

Method 3: Using List Comprehensions

List comprehension in Python is a concise way to apply an expression to each element in a sequence. By combining list comprehension with a checking condition, we can iteratively flatten one level of the nested list by detecting and extending list elements until no sublists are left.

Here’s an example:

def flatten_with_list_comprehension(lst):
    while any(isinstance(i, list) for i in lst):
        lst = [item for sublist in lst for item in (sublist if isinstance(sublist, list) else [sublist])]
    return lst

nested_list = [[1, 2, [3]], 4]
flattened = flatten_with_list_comprehension(nested_list)
print(flattened)

Output:

[1, 2, 3, 4]

This code snippet uses nested list comprehensions to flatten lists. If the current element is a list, it is extended; otherwise, it is added as-is. The outer while loop ensures the process continues until there are no more sublists.

Method 4: Using itertools.chain

itertools.chain from Python’s standard library itertools module provides a way to iterate over elements of multiple containers as if they were a single container. This method iterates over each level of nested sublists individually and combines them into a flat list.

Here’s an example:

from itertools import chain

def flatten_with_itertools(lst):
    while any(isinstance(i, list) for i in lst):
        lst = list(chain.from_iterable((sublist if isinstance(sublist, list) else [sublist] for sublist in lst)))
    return lst

nested_list = [[1, 2, [3]], 4]
flattened = flatten_with_itertools(nested_list)
print(flattened)

Output:

[1, 2, 3, 4]

The function applies chain.from_iterable to flatten the nested list, but first, it ensures that all elements are iterable—single elements are converted into a list with one element. The function loops until all elements are no longer lists.

Bonus One-Liner Method 5: Using a List Comprehension with a Helper Function

This method uses a single line of Python code, leveraging a helper function within a list comprehension to yield a flattened list. This method is concise but can be less intuitive for someone reading the code for the first time.

Here’s an example:

def is_list(element):
    return isinstance(element, list)

nested_list = [[1, 2, [3]], 4]
flattened = [element for sublist in nested_list for element in (sublist if is_list(sublist) else [sublist])]
print(flattened)

Output:

[1, 2, 3, 4]

The is_list helper function checks if an element is a list. The list comprehension then iterates over each element, flattening the list by one level. Note that this method only works for lists nested exactly one level deep.

Summary/Discussion

  • Method 1: Using a Stack. Strengths: Intuitive and efficient for deep nesting. Weaknesses: Might not be the most Pythonic way.
  • Method 2: Using a While Loop with a Temporary List. Strengths: In-place modification without additional data structures. Weaknesses: Modifying the list during iteration can be risky and lead to subtle bugs.
  • Method 3: Using List Comprehensions. Strengths: Pythonic and concise. Weaknesses: Can be difficult to read and understand due to the complexity of nested comprehensions.
  • Method 4: Using itertools.chain. Strengths: Clean and efficient, leveraging Python’s standard library. Weaknesses: Requires understanding of itertools module functions.
  • Bonus One-Liner Method 5: Using a List Comprehension with a Helper Function. Strengths: Very concise. Weaknesses: Only flattens one level and is less readable for beginners.