每个结构有哪些优点?
在我的程序中,我将执行这些步骤,我想知道我应该使用哪个数据结构:
您何时知道何时使用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复杂度可以准确预测实际性能......]
TreeSet的真正力量和优势在于它实现的界面 - NavigableSet
为什么它如此强大,在哪种情况下呢?
Navigable Set界面添加了例如这3个不错的方法:
headSet(E toElement, boolean inclusive)
tailSet(E fromElement, boolean inclusive)
subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)
这些方法允许组织有效的搜索算法(非常快)。
示例:我们需要找到以Milla开头并以Wladimir结尾的所有名称:
TreeSet<String> authors = new TreeSet<String>();
authors.add("Andreas Gryphius");
authors.add("Fjodor Michailowitsch Dostojewski");
authors.add("Alexander Puschkin");
authors.add("Ruslana Lyzhichko");
authors.add("Wladimir Klitschko");
authors.add("Andrij Schewtschenko");
authors.add("Wayne Gretzky");
authors.add("Johann Jakob Christoffel");
authors.add("Milla Jovovich");
authors.add("Taras Schewtschenko");
System.out.println(authors.subSet("Milla", "Wladimir"));
输出:
[Milla Jovovich, Ruslana Lyzhichko, Taras Schewtschenko, Wayne Gretzky]
TreeSet不会覆盖所有元素,它会找到第一个和最后一个元素,并返回一个包含该范围内所有元素的新Collection。
如果你想保持它的排序并且它是附加的 - 大多数情况下,带有比较器的TreeSet是你最好的选择。 JVM必须从头开始遍历LinkedList以决定放置项目的位置。 LinkedList = O(n)用于任何操作,TreeSet = O(log(n))用于基本内容。
TreeSet中:
TreeSet
使用红黑树。所以这套可以被认为是一个dynamic search tree
。当您需要一个经常读/写操作并且应该保持顺序的结构时,TreeSet是一个不错的选择。
选择数据结构时最重要的一点是其固有的局限性。例如,如果使用TreeSet存储对象,并且在运行期间,算法会更改这些对象的属性,这些对象会影响相等的比较,而对象是集合的元素,请为一些奇怪的错误做好准备。
Java Doc for Set接口声明:
注意:如果将可变对象用作set元素,则必须非常小心。如果在对象是集合中的元素的同时以影响等于比较的方式更改对象的值,则不指定集合的行为。这种禁令的一个特例是,不允许集合将自身作为一个要素包含在内。