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

Could you use a CompositeCollection?

public Collection cons(Collection c1, Collection c2)
{
    CompositeCollection cons = new CompositeCollection();
    cons.addComposited(c1);
    cons.addComposited(c2);
    return cons;
}

This would not be affected by whether or not one of the parameters is immutable and is still backed by the original collections c1 and c2.

If you need a List I would probably do the following:

public List cons(Collection c1, Collection c2)
{
    ArrayList cons = new ArrayList(c1.size() + c2.size());
    cons.addAll(c1);
    cons.addAll(c2);
    return cons;
}

Answer 2

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 3

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.

Answer 4

I'm going to throw my 2 cents in, then see if anybody comes up with anything more elegant. In the general case:

<E> List<E> cons(E e, List<E> list) {
    List<E> res = Lists.newArrayListWithCapacity(list.size() + 1);
    res.add(e);
    res.addAll(list);
    return res;
}

With an ImmutableList (don't know how efficient this is):

<E> ImmutableList<E> cons(E e, ImmutableList<E> list) {
    return ImmutableList.<E>builder()
                        .add(e)
                        .addAll(list)
                        .build();
}

Answer 5

Surely a LinkedList would be the most efficient way of inserting an item at the head of a list?

Just use the LinkedList class that comes with Java

Answer 6

Because you mention the cons function, I will assume that you're approaching this problem with the conceptual model of linked lists composed of cons cells. Specifically, I assume that you're thinking of each list having a car (the first element) and a cdr (the sublist containing all following elements).

Java supports linked lists as java.util.LinkedList. These are good for linear traversal and can have elements inserted very efficiently. These are most similar to the linked lists I mentioned above.

Java also offers java.util.ArrayList. Lists of this kind are good for random access, but can be slow when inserting elements. In fact, they are slowest when inserting an element at the beginning of the list. Because ArrayLists are implemented as arrays behind the scenes, every element must be copied one position forward in the list to make room for the new first element. Now, if you also happen to need a bigger array, the ArrayList will allocate a new array, copy all the elements over, and so on.

(Google's ImmutableList is cited as "random-access", so it is likely more similar to the latter.)

If you plan to use your cons method often, I recommend using it with linked lists. A cons operation is essentially adding an element at the beginning of a list. This makes little sense with linear structures such as arrays. I recommend against using array lists for this reason: that they're conceptually wrong for the job.

For the very picky: because a new list is returned each time cons is called, copying must occur whether the list is a LinkedList or an ArrayList. However, the entire principal of a cons operation is that it is operating on a linked list.

public <E> LinkedList<E> cons(E car, List<E> cdr) {
    LinkedList<E> destination = new LinkedList<E>(cdr);
    destination.addFirst(car);
    return destination;
}

Note that the above code was written after reading the above answers, so I apologize for any accidental plagiarism. Let me know if you see it and I'll properly acknowledge.

Assuming you're happy with returning a LinkedList, you can use ImmutableList as the cdr in this example.

Answer 7

Another variation if you have only Iterable.

public static <E> List<E> cons(E e, Iterable<E> iter) {
   List<E> list = new ArrayList<E>();
   list.add(e);
   for(E e2: iter) list.add(e2);
   return list;
}

public static <E> List<E> cons(Iterable<E>... iters) {
   List<E> list = new ArrayList<E>();
   for(Iterable<E> iter: iters) for(E e1: iter1) list.add(e1);
   return list;
}

Answer 8

I believe the answer you're really looking for is this:

http://functionaljava.googlecode.com/svn/artifacts/2.20/javadoc/fj/data/List.html

The method is even called cons.

I have no experience with this library. Just heard of it the other day. I hope it's good!

Answer 9

An efficient solution would be to create your own List implementation, lazily delegating. If unmodifiable, it wouldn't be too much trouble. If created through a factory method, then you could even use one of two different underlying implementations depending on whether the argument List implements RandomAccess or not.

For the simplest case (haven't checked to see whether this compiles, no sanity checks, etc.):

class ConsList<E> extends AbstractList<E>
{
    private final E first;
    private final List<E> rest;

    ConsList( E first, List<E> rest )
    {
        this.first = first;
        this.rest = rest;
    }

    public int get( int index )
    {
        return (index == 0) ? first : rest.get( index - 1 );
    }

    public int size()
    {
        return rest.size() + 1;
    }
}

I'm sure a few of the other methods could be made more efficient, and the sequential case would be better served by extending AbstractSequentialList instead.