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)) { newList.add(i); } else { // It’s a list, so add each item to the return list. newList.addAll(flattenList((List)i)); } }

return newList; }

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

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

ListIterator iterator = newList.listIterator();

int currentPosition = 0;

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

// Delete the list from the list iterator.remove();

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

// 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); i++; } }

public static void main(String[] args) {

BasicConfigurator.configure();

// 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++) { intList.add(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”); nestedList2.add(nestedList3); nestedList1.add(nestedList2);

LinkedList bigList = new LinkedList();

bigList.add(“First item”); bigList.add(stringList); bigList.add(“Third Item”); bigList.add(intList); bigList.add(“Fifth Item”); bigList.add(nestedList1); 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);

} }