从列表中删除范围（尾部）(Removing range (tail) from a List)

是否有一个有效的方法来删除一个范围-比如尾- X元素从一个List ，例如LinkedList Java中？

这显然是可以通过一个删除最后一个元素之一，这将导致O（X）级性能。 至少对于LinkedList情况下，它应该是可能的有O（1）的性能（通过将第一元件周围的引用被去除并设置头/尾参考文献）。 不幸的是我没有看到的任何方法List或LinkedList一次全部删除最后一个元素。

目前，我想通过更换名单的List.subList()但我不知道是否有相同的性能。 至少这将是在代码内更加清晰，在另一方面我将松散的附加功能LinkedList提供。

我主要是使用列表作为堆栈，用于其LinkedList似乎是最好的选择，至少对于语义。

Answer 1:

subList(list.size() - N, list.size()).clear()是去除最后的推荐方式N元件。 事实上， 为的Javadoc subList 特别建议这个成语：

这种方法消除了显式范围操作的需要（排序，对于数组中普遍存在的）。 期望一个列表中的任何操作可通过使子列表视图而不是整个列表的被用作范围操作。 例如，下面的语句中删除的范围从一个列表中的元素：

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

事实上，我怀疑这个成语可能是（常数因子虽然） 更有效比调用removeLast() N倍，只是因为它一旦发现N个到最后一个节点，其只需要更新指针的常数在该链接的表，而不是更新每个最后的指针N节点一次一个。

Answer 2:

要知道， subList()返回原始的列表，这意味着的观点 ：

1. 做视图的任何修改都会反映在原始列表
2. 返回的列表不是 LinkedList -这是一个内部实现的List ，这不是序列化

无论如何，使用任一removeFirst()或removeLast()应该足够有效，因为弹出Java中的链表的第一或最后一个元素是一个O(1)的操作-在内部， LinkedList保存指针清单，并除去的两端任一个是作为移动指示器的一个位置一样简单。

为了去除m一次的元素，你不得不拥有O(m)与性能LinkedList ，但奇怪的是一个ArrayList可能是一个更好的选择，因为在结束移除元素ArrayList是移动索引指针（简单表示该阵列的端部）的一个位置，以它的左侧，而没有垃圾节点被留下作为悬空是用的情况下LinkedList 。 最佳选择？ 尝试两种方法，并将它们归档，让数字来说话。

文章来源: Removing range (tail) from a List