Когда вы знаете, когда использовать TreeSet или LinkedList?

Question

В чем преимущества каждой структуры?

В моей программе я буду выполнять эти шаги, и мне было интересно, какая структура данных выше, я должен использовать:

1. Taking в несортированному массиве и , добавив их в отсортированном structure1.
2. обхода через отсортированные данные и удаление права один
3. Добавление данных (никогда не снимая) и возвращаю эту структуру в виде массива

Answer 1

Если вы хотите сохранить его сортирует и это добавляет, в основном, TreeSet с Компаратор - ваш лучший выбор. JVM должен будет пересечь LinkedList с самого начала, чтобы решить, где разместить элемент. LinkedList = O (n) для любых операций, TreeSet = O (log (n)) для базового материала.

Answer 2

Когда вы знаете, когда использовать TreeSet или LinkedList? Каковы преимущества каждой структуры?

В общем, вы выбираете тип коллекции, основываясь на структурных и эксплуатационных свойствах, которые вам нужны. Например, TreeSet представляет собой набор и, следовательно, не позволяет дублировать и не сохраняет порядок вставки элементов. Напротив, LinkedList является списком и, следовательно, позволяет дублировать и сохраняет порядок вставки. С точки зрения производительности 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 3

TreeSet:

TreeSet использует красно-черное дерево, лежащее в основе. Таким образом, набор можно рассматривать как dynamic search tree. Когда вам нужна структура, которая часто работает с чтением/записью, а также должна поддерживать порядок, TreeSet является хорошим выбором.

Answer 4

Подлинная сила и преимущество TreeSet лежит в интерфейсе он понимает - NavigableSet

Почему это так мощный и в этом случае?

Судоходная 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 не идет по всем элементам, он находит первый и последний элементы и возвращает новую коллекцию со всеми элементами в диапазоне.