Yesterday I made a linked list, in Java. Yeah, that's right.

Today I'm taking on a programming problem: given a doubly-linked list (with head and tail), where any element may have a child doubly-linked list (without head and tail), flatten the structure into a doubly-linked list.

That sounds vaguely tree-like, but trees don't usually have linked siblings. It's all just parents and children. I'm calling this a bush.

Let's look at the structure.

head->A<=>D<=>E<=>FC       G
                  |
                  H

Without being told where to put stuff, I could just tack it all on the tail. But I think tacking it on after its parent is more elegant, if it can be implemented in similar complexity and space. In the bush I drew, I'd like the nodes to end up in alphabetical order.

I might even be able to do this without recursion.

I'll travel along the list, examining each node. If it's got a child, I'll append the child to the parent. Then I move to the next element.

That screws up the double linking, though. I could, on append, travel to the end of the child list, and adjust the links from there. But then I have to visit all the children twice. Well, that's not too bad; it increases the time complexity to O(2n), which is still linear, and storage stays O(1): all I need is a couple of pointers.

On the other hand, if storage is not the biggest issue, I can use a little bit of recursion to get a faster implementation, which visits each node only once.

The recursive function flattenAndFindTail(Bush head) flattens the provided bush and returns the tail. Basically, it just iterates down the bush, and calls flattenAndFindTail(node.child) on any bush that has a child. It then inserts the whole flattened list between the parent and the parent's next sibling, using the returned tail to adjust the sibling's prev pointer. Finally, it advances to the sibling, skipping the inserted list, because the inserted list has already been flattened.

This works in O(n) time, rather than O(2n)... not a big improvement, but more efficient regardless. Unfortunately, it takes up O(m) storage, where m is the maximum depth of the bush, in remembering a parent pointer for each recursive call.

In cases where the depth of the bush is not expected to be large, I'd like to use the recursive function. And I really like the elegance of flattening the child behind the parent; it's looks like the diagramming I did in English class. I'll use an iterative method to create the array in main(), just to show off that I can do it both ways.

[code] public class BushNode { public String value = null; public BushNode next = null; public BushNode prev = null; public BushNode child = null; public BushNode(String value) { this.value = value; } } [/code][code] public class Bush { public BushNode head = null; public BushNode tail = null; /** * Print out the bush with braces around sublists. * @param top The top of the bush */ public void printBush(BushNode top) { System.out.print(top.value + " "); if (top.child != null) { System.out.print("{ "); printBush(top.child); System.out.print("} "); } if (top.next != null) { printBush(top.next); } } /** * Driver to create a bush and flatten it * @param args A single string of the form { A B { C { D E F } G } H { I J } K }, * where each brace indicates the start of a child list. In this case, A * has no children, while B has a child list of two elements, including * an element C with a three-element child list of its own. */ public static void main(String args[]) { Bush bush = new Bush(); String list = "{ A B { C { D E F } G } H { I J } K }"; if (args.length > 0) { list = args[0]; } if (!list.startsWith("{")) { System.out.println("First character of list must be an opening brace!"); System.exit(-1); } if (!list.endsWith("}")) { System.out.println("Last character of list must be a closing brace!"); System.exit(-2); } list = list.substring(1, list.length() - 1); BushNode curr = null; boolean firstChild = true; LinkedList levelStack = new LinkedList(); StringTokenizer t = new StringTokenizer(list, " "); while (t.hasMoreElements()) { String tok = t.nextToken(); if (tok.equals("{")) { // We need to start a new sublist if (firstChild) { System.out.println("Invalid argument: list without parent!"); System.exit(-5); } firstChild = true; levelStack.push(curr); } else if (tok.equals("}")) { // This sublist is finished! try { curr = levelStack.pop(); } catch (NoSuchElementException e) { System.out.println("Invalid argument: no start for list end!"); System.exit(-4); } } else { if (firstChild) { // First element in a new list if (curr == null) { // The first element in the whole list bush.head = curr = new BushNode(tok); } else { // First element in a sublist of the current element curr.child = new BushNode(tok); curr = curr.child; } firstChild = false; } else { // Just another element in the current list curr.next = new BushNode(tok); curr.next.prev = curr; curr = curr.next; } } } // All done with elements. Pop up to the top level and set the tail. System.out.print("{ "); bush.printBush(bush.head); System.out.println("} "); System.out.println("Flattenning..."); Flatten f = new Flatten(); f.flatten(bush); f.printFlattenedBush(bush); } } [/code][code] /** * Flatten a doubly-linked list with child lists (which I call a Bush). */ public class Flatten { /** * Traverse the bush; whenever a node has a child, attach the child and * its siblings after the parent in the top list. * * This algorithm has the advantage of visiting each node only once, * although it requires additional space to accommodate the recursion. * @param bush The bush to flatten */ public void flatten(Bush bush) { bush.tail = flattenAndFindTail(bush.head); } public BushNode flattenAndFindTail(BushNode node) { BushNode curr = null; BushNode next = node; do { curr = next; if (curr.child != null) { BushNode subTail = flattenAndFindTail(curr.child); subTail.next = curr.next; if (curr.next != null) { curr.next.prev = subTail; } curr.next = curr.child; curr.child.prev = curr; curr = subTail; } // Nothing to flatten here next = curr.next; } while (next != null); return curr; } /** * Print the Bush, ignoring any children. * @param bush The bush to print */ public void printFlattenedBush(Bush bush) { BushNode curr = bush.head; System.out.print("_ "); while (curr != null) { System.out.print(curr.value + " "); curr = curr.next; } System.out.println("_"); } } [/code]

Pretty swanky, eh?

Well, fine, then. If you've got a better idea, I'd love to hear it!