Java: "cons" an item to a list

Question

I have an Item which has a method List<Item> getChildren() (which returns an immutable list) and for each of the items I have, I need to create a list of the item followed by its children.

What's the quickest way to "cons" (in the Lisp/Scheme sense) my item to create a new immutable list? I can certainly do the following, but it seems wrong/wasteful:

public List<Item> getItemAndItsChildren(Item item)
{
    if (item.getChildren.isEmpty())
        return Collections.singletonList(item);
    else
    {
        // would rather just "return cons(item, item.getChildren())"
        // than do the following -- which, although straightforward,
        // seems wrong/wasteful.
        List<Item> items = new ArrayList<Item>();
        items.add(item);
        items.addAll(item.getChildren());
        return Collections.unmodifiableList(items);
    }
}

Answer 1

I'd change my requirements. In most cases, you don't need a List in your interface, an Iterable will do nicely. Here's the method:

public Iterable<Item> getItemWithChildren(Item item)    {
    return Iterables.unmodifiableIterable(
        Iterables.concat(
            Collections.singleton(item),
            item.getChildren()
        )
    );
}

and here's the shortened version (with static imports):

return unmodifiableIterable(concat(singleton(item), item.getChildren()));

Answer 2

The ability to create a new immutable list by concatenating a head element to a tail that may be shared between other lists requires a singly-linked list implementation. Java doesn't provide anything like this out of the box, so your ArrayList solution is as good as anything.

It's also going to be relatively efficient, assuming that these lists are short-lived and you don't have tens of thousands of element in the list. If you do, and if this operation is taking a significant portion of your execution time, then implmenting your own single-linked list might be worthwhile.

My one change to improve your existing efficiency: construct the new list with a capacity (1 + size of old list).