21

如何通过 jdk1.6、google 或 apache commons 集合或其他方式将 O(1) 中的两个链表与 Java 连接起来？例如，在 jdk 中只有 addAll 方法是 O(n)。

我想念的另一个功能是连接两个列表，其中每个列表都可以按相反的顺序排列。为了说明这一点，假设两个列表 a->b->c 和 e->f->g 可以合并到

  1. a->b->c->e->f->g
  2. a->b->c->g->f->e
  3. c->b->a->e->f->g
  4. c->b->a->g->f->e

你知道这样的列表实现还是我必须实现自己的链表？了解如何调整现有解决方案也很有帮助（例如 jdk LinkedList 只有很多私有方法）。这些功能在我看来非常明显，希望我不会错过一些愚蠢的东西。

正如 MicSim 指出的问题，在 Java 中以恒定时间合并两个列表是相关的，但不是真正的重复！现在的问题是：

  1. 其他集合库可以吗？
  2. 如何连接逆？
4

6 回答 6

6

如果你愿意接受 Iterable 结果，你可以使用 google-collections Iterables.concat 和 Iterables.reverse

http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Iterables.html

public static <T> Iterable<T> concat(Iterable<? extends T> a,
                                 Iterable<? extends T> b)

public static <T> Iterable<T> concat(Iterable<? extends T> a,
                                 Iterable<? extends T> b,
                                 Iterable<? extends T> c)

public static <T> Iterable<T> concat(Iterable<? extends T> a,
                                 Iterable<? extends T> b,
                                 Iterable<? extends T> c,
                                 Iterable<? extends T> d)

public static <T> Iterable<T> concat(Iterable<? extends T>... inputs)

public static <T> Iterable<T> concat(Iterable<? extends Iterable<? extends T>> inputs)
于 2010-03-22T17:52:46.557 回答
2

我目前看到的唯一解决方案是实现 List，创建一个构造函数，如：

public EnhancedList (List l1, List l2)

并覆盖所有方法。在这样的解决方案中，是否要连接 LinkedLists 或任何其他列表实际上并不重要。

于 2010-03-22T16:49:46.543 回答
0

I'd think this wouldn't be too difficult to write with any kind of base list construct since insertion in the middle or the end of a list in a Linked list is O(1).

于 2010-03-22T16:58:44.037 回答
0

在以下情况下，调整 LinkedList 以在 jdk 中获得 O(1) concat 将起作用：

  1. 方法 entry() 和变量 header 和 size 以及内部类 Entry 将受到保护

  2. addAll 会检测 LinkedList 然后做某事。喜欢：

    JdkLinkedList secondList = (JdkLinkedList) secondColl;
int numNew = secondList.size();
if (numNew == 0)  return false;
modCount++;
Entry<E> successor = (index == size ? header : entry(index));
Entry<E> predecessor = successor.previous;
// TODO LATER if reverse

// connect the last element of this list with the first element of the second list
// linked list is implemented as a 'cycle' => header.next == first element of second list
Entry<E> first = secondList.header.next;
predecessor.next = first;
first.previous = predecessor;

// append the last element of the second list with the rest of this list
Entry<E> last = secondList.header;
successor.previous = last;
last.next = successor;
于 2010-03-22T18:49:02.833 回答
0

对于 concat，我建议您执行以下操作：

  • 确保所有参数/变量都声明为 List<...> 而不是 LinkedList<...>
  • 更改新的 LinkedList<...>(); 到新的 ArrayList<...>();
  • 分析应用程序
  • 将新的 ArrayList<...> 更改为 new LinkedList<...>();
  • 分析应用程序

根据您的使用情况，ArrayList 可能比 LinkedList 快得多。还可以查看配置文件数据，您可以看到使用 addAll 对性能的影响有多大——如果不是那么大，请不要费心“修复”它。

对于某些事情，您使用其他语言的经验将不成立。您可能会发现 addAll 符合您在 Java 中的要求。

如果您要编写自己的可连接列表，请确保它符合 List 接口，然后更改您的代码并重新配置它并确保它更快。如果不是，则将其丢弃并坚持使用标准 List 类型。

于 2010-03-22T18:58:52.583 回答
0

来自 javolution 的 FastList不是开箱即用的解决方案，但 tail() 和 head() 非常接近我的最爱。

我认为trove是解决方案，尽管在 O(1) 中不存在用于反转或 addAll 的便捷方法。

于 2010-03-22T20:45:25.187 回答