5

假设我有一个java.util.List list并且我想通过在开头List添加一个元素来创建一个新的（即，我想要cons和）。例如，如果是elist elistlist

[1,2,3,4]

并且e是5, 那么cons(e,list)将是

[5,1,2,3,4]

list和的元素cons(e,list)可以共享，但list不能修改。

什么是最简单和/或最有效的实施方式cons？结果不可修改是可以的。允许使用 Google 收藏库。

如果list是 acom.google.common.collect.ImmutableList怎么办？

4

10 回答 10

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

针对评论进行编辑：由于问题要求“实现缺点的最简单和/或最有效的方法”，我选择了“最简单”。得知有更有效的方法，我不会感到惊讶。将元素放在列表之前是另一种有效的方法，最初分配正确的大小可能会提高性能。过早的优化是万恶之源。

于 2009-05-05T18:35:48.663 回答
7

Clojure提供了那种 Lisp-y 的东西。虽然大多数人都认为将 Clojure 用于该语言（就像我一样），但 Clojure 库都是真正的 Java 代码，如果您愿意，您可以将 Java 中的数据结构用作一个特殊的库。这样，您将获得执行 cons 等操作的能力，并且获得 Clojure 使用的不变性。Clojure 数据结构也实现了等效的 Java 类型。

只是一个不同方向的想法。

于 2009-05-05T18:45:20.513 回答
4

我相信您真正想要的答案是：

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

该方法甚至被调用cons。

我对这个图书馆没有经验。前几天刚听说。我希望它是好的！

于 2009-11-06T10:11:05.630 回答
4

一个有效的解决方案是创建自己的 List 实现，懒惰地委托。如果不可修改，那也不会太麻烦。如果通过工厂方法创建，那么您甚至可以使用两种不同的底层实现之一，具体取决于参数 List 是否实现 RandomAccess。

对于最简单的情况（尚未检查是否编译，没有完整性检查等）：

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;
    }
}

我确信其他一些方法可以提高效率，并且通过扩展 AbstractSequentialList 可以更好地服务于顺序情况。

于 2010-04-14T02:03:53.447 回答
3

因为您提到了该cons函数，所以我假设您正在使用由单元格组成的链表的概念模型来解决这个问题cons。具体来说，我假设您正在考虑每个列表都有一个car（第一个元素）和一个cdr（包含所有后续元素的子列表）。

Java 支持链表作为java.util.LinkedList. 这些对于线性遍历很有用，并且可以非常有效地插入元素。这些与我上面提到的链表最相似。

Java 还提供java.util.ArrayList. 这种列表适合随机访问，但在插入元素时可能会很慢。事实上，在列表开头插入元素时，它们的速度最慢。因为ArrayLists 在幕后实现为数组，所以每个元素都必须在列表中向前复制一个位置，以便为新的第一个元素腾出空间。现在，如果您还碰巧需要一个更大的数组，ArrayList则将分配一个新数组，将所有元素复制过来，依此类推。

（谷歌ImmutableList被称为“随机访问”，因此它可能更类似于后者。）

如果您打算cons经常使用您的方法，我建议将它与链表一起使用。cons操作本质上是在列表的开头添加一个元素。这对于诸如数组之类的线性结构几乎没有意义。出于这个原因，我建议不要使用数组列表：它们在概念上不适合这项工作。

对于非常挑剔的人：因为每次调用都会返回一个新列表，所以无论列表是 a还是 ancons都必须进行复制。但是，操作的全部原理是它在链表上进行操作。LinkedListArrayListcons

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

请注意，上述代码是在阅读上述答案后编写的，因此对于任何意外抄袭，我深表歉意。如果你看到它，请告诉我，我会正确承认。

假设您对返回 a 感到满意LinkedList，您可以在本例中使用ImmutableListas 。cdr

于 2009-05-05T23:19:44.253 回答
3

这并不为人所知，但 Sun javac 编译器 API 包含一个不可变的 List 实现，它使用append()和之类的方法返回新的不可变列表prepend()。要使用它，您需要tools.jar在类路径上，以及这个 import 语句：

import com.sun.tools.javac.util.List;

示例代码：

final List<Integer> list = List.of(6, 7);
System.out.println(list);

final List<Integer> newList =
    list.prepend(5)                       // this is a new List
        .prependList(List.of(1, 2, 3, 4)) // and another new List
        .append(8)                        // and another
        .reverse();                       // and yet another
System.out.println(newList);

System.out.println(list == newList);

System.out.println(list.getClass());
System.out.println(newList.getClass());

输出：

6,7
8,7,6,5,4,3,2,1
false
class com.sun.tools.javac.util.List
class com.sun.tools.javac.util.List

我知道这是一个内部 API，不应该在生产中使用，但它非常有趣（最后是一个感觉正确的 java 集合）。

注意：显然，来自Collection和List接口的所有标准可变方法（如add() addAll()） throw 。UnsupportedOperationException

参考：

于 2011-02-15T16:29:46.847 回答
2

我将投入我的 2 美分，然后看看是否有人想出更优雅的东西。在一般情况下：

<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;
}

有一个ImmutableList（不知道这有多有效）：

<E> ImmutableList<E> cons(E e, ImmutableList<E> list) {
    return ImmutableList.<E>builder()
                        .add(e)
                        .addAll(list)
                        .build();
}
于 2009-05-05T19:10:29.393 回答
2

你可以使用CompositeCollection吗？

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

这不会受到参数之一是否不可变并且仍然由原始集合 c1 和 c2 支持的影响。

如果您需要，List我可能会执行以下操作：

public List cons(Collection c1, Collection c2)
{
    ArrayList cons = new ArrayList(c1.size() + c2.size());
    cons.addAll(c1);
    cons.addAll(c2);
    return cons;
}
于 2009-05-05T18:26:36.470 回答
2

LinkedList 肯定是在列表开头插入项目的最有效方式吗？

只需使用 Java 自带的LinkedList类

于 2009-05-05T22:20:48.467 回答
0

如果您只有 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;
}
于 2009-05-07T19:57:11.167 回答