42

是否有一种有效的方法可以从 a 中删除 X 元素的范围（例如尾部）List，例如LinkedList在 Java 中？

显然可以一个一个地删除最后一个元素，这应该会导致 O(X) 级别的性能。至少在LinkedList某些情况下，应该有可能获得 O(1) 性能（通过设置要删除的第一个元素周围的引用并设置头/尾引用）。不幸的是，我没有看到任何方法，也没有List一次LinkedList删除最后一个元素。

目前我正在考虑使用替换列表，List.subList()但我不确定这是否具有相同的性能。至少在代码中会更清楚，另一方面我会失去LinkedList提供的附加功能。

我主要将 List 用作堆栈，这LinkedList似乎是最好的选择，至少在语义方面。

4

2 回答 2

78

subList(list.size() - N, list.size()).clear()是删除最后一个N元素的推荐方法。事实上，Javadoc forsubList 特别推荐这个成语：

这种方法消除了显式范围操作的需要（通常存在于数组中的那种）。通过传递 subList 视图而不是整个列表，任何需要列表的操作都可以用作范围操作。例如，以下习惯用法从列表中删除一系列元素：

 list.subList(from, to).clear();

确实，我怀疑这个习语可能比调用时间更有效（尽管是一个常数因子）removeLast() N，因为一旦它找到N倒数第二个节点，它只需要更新链表中的常数个指针，而不是一次更新每个最后一个N节点的指针。

于 2012-05-29T11:22:28.760 回答
15

请注意，它subList()返回原始列表的视图，这意味着：

  1. 对视图所做的任何修改都将反映在原始列表中
  2. 返回的列表不是- 它是不可序列化LinkedList的内部实现List

无论如何，使用removeFirst()orremoveLast()应该足够有效，因为在 Java 中弹出链表的第一个或最后一个元素是一项O(1)操作 - 在内部，LinkedList保存指向列表两端的指针，删除任何一个就像将指针移动一个位置一样简单.

对于一次删除m元素，您会O(m)遇到 a 的性能LinkedList问题，尽管奇怪的是 anArrayList可能是更好的选择，因为删除 an 末尾的元素ArrayList就像移动索引指针（表示数组的末尾）一样简单位置在其左侧，并且没有垃圾节点像LinkedList. 最佳选择？尝试这两种方法，分析它们并让数字说明一切。

于 2012-05-29T11:14:23.743 回答