Cons'ing a List in Java

Question

Say I have a java.util.List list and I want to create a new List by adding an element e to the beginning of list (i.e., I want to cons e and list). For example, if list is

[1,2,3,4]

and e is 5, then cons(e,list) will be

[5,1,2,3,4]

It's OK for the elements of list and cons(e,list) to be shared, but list should not be modified.

What is the simplest and/or most efficient way to implement cons? It's OK for the result to be unmodifiable. Use of the Google Collections Library is allowed.

What if list is a com.google.common.collect.ImmutableList?

Answer 1

public static<T> List<T> cons(List<T> list, T t) {
    ArrayList<T> result = new ArrayList<T>(list);
    result.add(0, t);
    return result;
}

Edited in response to comments: Since the question asked for "the simplest and/or most efficient way to implement cons," I went with "simplest". I wouldn't be surprised to learn there are more efficient ways. Putting the element in before the list is another valid approach, and allocating the correct size initially could probably improve performance. Premature optimization is the root of all evil.

Answer 2

Clojure provides that kind of Lisp-y stuff. While most people think of using Clojure for the language (like I do), the Clojure libraries are all real Java code, and you can use the data structures from Java as just a special library if you'd like. That way you'd get the ability to do cons and such, and you get the immutability that Clojure uses. The Clojure data strcutres implement the equivalent Java types too.

Just a thought from a different direction.