Code to flatten a list in Java, with and without recursion

Recently had someone ask me to solve this problem: assume you have a list of objects, some of which may be lists of arbitrary depths. Write a function to return the list “flattened,” so sublists are all in the “main” list. I solved it recursively pretty easily, but it took some thought to do it without recursion. My solutions are below.

package com.evanhoffman.listflattener;

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

import org.apache.log4j.BasicConfigurator;
import org.apache.log4j.Logger;

public class ListFlattener {

        private static Logger logger = Logger.getLogger(ListFlattener.class);

        public static List flattenList(List inList) {
                List newList = new LinkedList();

                for (Object i : inList) {
                        // If it's not a list, just add it to the return list.
                        if (!(i instanceof List)) {
                        } else {
                                // It's a list, so add each item to the return list.

                return newList;

        public static List flattenListNoRecursion(List inList) {
                List tempList = null;

                // Clone the input list to newList
                List newList = new LinkedList();

                ListIterator iterator = newList.listIterator();

                int currentPosition = 0;

                while (iterator.hasNext()) {
                        Object i =;
                        if (!(i instanceof List)) {
                                // If it's not a list, advance the position.  Don't advance position if this IS a list.
                        } else {
                                // If the current item is a list, save it to a temp var.
                                tempList = (List) i;

                                // Delete the list from the list

                                // Add each item from the temp list to the master list at the same position the sublist was removed.
                                for (Object obj : tempList) {

                                // reset the iterator to re-walk the list that was just inserted (within the master) to check for more lists.
                                iterator = newList.listIterator(currentPosition);
                return newList;

        public static void printList(List list) {
                int i = 0;
                for (Object item : list) {
                        logger.debug("List item #"+i +": "+item);

        public static void main(String[] args) {


                // List of strings
                LinkedList stringList = new LinkedList();
                for (Integer i = 0; i < 10; i++) {
                        stringList.add("String #" +i.toString());

                // List of integers
                LinkedList intList = new LinkedList();
                for (Integer i = 10; i < 20; i++) {

                // Nested Lists
                LinkedList nestedList1 = new LinkedList();
                LinkedList nestedList2 = new LinkedList();
                LinkedList nestedList3 = new LinkedList();

                nestedList3.add("Nested String 1");
                nestedList3.add("Nested String 2");

                LinkedList bigList = new LinkedList();

                bigList.add("First item");
                bigList.add("Third Item");
                bigList.add("Fifth Item");
                bigList.add("Seventh Item");

//              List flattenedList = flattenList(bigList);
                List flattenedListRecursion = flattenList(bigList);
                List flattenedList = flattenListNoRecursion(bigList);

                logger.debug("Original list:                 "+bigList.toString());
//              printList(bigList);
                logger.debug("Flattened list (w/ recursion): "+flattenedListRecursion.toString());
                logger.debug("Flattened list (no recursion): "+flattenedList.toString());
//              printList(flattenedList);


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: