您何时知道何时使用TreeSet或LinkedList？

Question

每个结构有哪些优点？

在我的程序中,我将执行这些步骤,我想知道我应该使用哪个数据结构:

1. 接收未排序的数组并将它们添加到已排序的结构1.
2. 遍历已排序的数据并删除正确的数据
3. 添加数据(从不删除)并将该结构作为数组返回

Answer 1

您何时知道何时使用TreeSet或LinkedList？每个结构有哪些优点？

通常,您根据所需的结构和性能属性决定集合类型.例如,TreeSet是一个Set,因此不允许重复,也不保留元素的插入顺序.相比之下,LinkedList是一个List,因此允许重复并保留插入顺序.在性能方面,TreeSet的给你O(logN)插入和删除,而LinkedList给出O(1)的开头或结尾,并插入O(N)插入在选定的位置或删除.

详细信息都在各自的类和接口javadocs中详细说明,但可以在Java Collections Cheatsheet中找到有用的摘要.

但在实践中,集合类型的选择与算法设计密切相关.这两者需要并行完成.(判断您的算法需要具有属性X,Y和Z的集合,然后发现不存在这样的集合类型是不合适的.)

在您的用例中,看起来TreeSet会更合适.没有有效的方法(即更好O(N^2))对大型LinkedList进行排序,而不涉及将其转换为其他数据结构来进行排序.没有有效的方法(即更好O(N))将元素插入先前排序的LinkedList中的正确位置.第三部分(复制到数组)与LinkedList或TreeSet同样适用; 这O(N)两种情况都是一种操作.

[我假设集合足够大,大O复杂度可以准确预测实际性能......]

Answer 2

如果您想让它保持排序并且主要是追加，那么带有比较器的 TreeSet 是您最好的选择。JVM 必须从头开始遍历 LinkedList 来决定将项目放置在哪里。对于任何操作，LinkedList = O(n)，对于基本操作，TreeSet = O(log(n))。