Python Program to Flatten a Nested List

In computer science, a list is a data structure that allows us to store multiple elements in a single container. Lists can contain other lists as their elements, creating nested lists. In Python, lists can be nested to any depth. However, working with deeply nested lists can become cumbersome and error-prone. Therefore, there may be situations where you want to “flatten” a nested list, converting it into a single, one-dimensional list.

Flattening a nested list means converting it into a one-dimensional list without altering the original elements. For example, a nested list [[1, 2, [3, 4]], [5, 6], 7] should be flattened to [1, 2, 3, 4, 5, 6, 7].

In this article, we will explore various methods to flatten a nested list in Python. We will discuss basic iterative methods, recursion, and Python-specific idioms that make the process efficient and easy to implement.

1. Iterative Method using Stack

An intuitive way to flatten a nested list is to use a stack data structure. The stack can be implemented using a Python list. The algorithm works as follows:

1. Initialize an empty stack and push the entire nested list onto it.
2. Initialize an empty list to hold the flattened result.
3. Pop an element from the stack.
   • If the element is a list, push its items onto the stack.
   • Otherwise, append the element to the flattened list.
4. Repeat step 3 until the stack is empty.

Here’s a Python implementation for the same:

def flatten_using_stack(lst):
    stack = [lst]
    flattened = []
    
    while stack:
        curr_element = stack.pop()
        
        if isinstance(curr_element, list):
            for elem in reversed(curr_element):
                stack.append(elem)
        else:
            flattened.append(curr_element)
            
    return flattened

nested_list = [[1, 2, [3, 4]], [5, 6], 7]
print(flatten_using_stack(nested_list))  # Output: [1, 2, 3, 4, 5, 6, 7]

2. Recursive Method

Flattening a nested list can be naturally thought of as a recursive problem. The base case for the recursion is when we encounter a non-list element. In that case, we return the element itself as a single-item list. The recursive case involves iterating through the list, flattening each element, and concatenating the results.

Here’s the Python code for the recursive approach:

def flatten_using_recursion(lst):
    flattened = []
    
    for elem in lst:
        if isinstance(elem, list):
            flattened.extend(flatten_using_recursion(elem))
        else:
            flattened.append(elem)
            
    return flattened

nested_list = [[1, 2, [3, 4]], [5, 6], 7]
print(flatten_using_recursion(nested_list))  # Output: [1, 2, 3, 4, 5, 6, 7]

3. Conclusion

Flattening a nested list is a common problem that can be solved using various techniques in Python. Whether you opt for an iterative approach or use recursion, it depends on your specific needs and the nature of the lists you’re working with.

Understanding the pros and cons of each method can help you make an informed decision, making your code more efficient, readable, and Pythonic.