LinkedList, вставка элементов в порядке возрастания по размеру

Question

В Java я хочу хранить элементы в порядке возрастания по размеру.Перед вставкой мне нужно обработать все мелкие элементы.Поэтому я начинаю перечислять список, относящийся к меньшим элементам, и когда я встречаю более крупный элемент, я хочу вставить новый узел перед этим более крупным элементом.Какая структура данных будет хорошим выбором?ArrayList не может быть хорошим выбором, поскольку при вставке в середине элементы сдвигаются вправо.Я посмотрел на API LinkedList, но я не нахожу методов для вставки до / после данного узла в списке.Существует метод add, который «вставляет указанный элемент в указанную позицию в этом списке», но для него требуется позиция в виде целого числа.Значит ли это, что реализация Java обходит список с самого начала, пока не найдет указанную позицию?Это кажется довольно дорогим.У меня есть позиция (узел), куда я хочу вставить, только некоторые ссылки должны быть изменены правильно, чтобы включить новый узел в список.Любые предложения?

Спасибо,

Джабба

Обновление: Спасибо всем за ответы, я мог решить проблему с LinkedList с помощью ListIterator.Затем я провел сравнительный тест и получил удивительные результаты.Итак, цель состоит в том, чтобы поддерживать элементы в списке / массиве отсортированным образом.Для этого я сравнил четыре варианта: (1) Vector, (2) ArrayList, (3) LinkedList и (4) MyLinkedList, это моя собственная реализация (очень простая).Для теста я создал массив из 1000 элементов и заполнил его случайными целыми числами от 1 до 100. Затем я добавил эти элементы в каждый контейнер в цикле.При добавлении этого массива 30 раз: MyLinkedList (2,7 с), LinkedList (6,6 с), ArrayList (6,9 с), Vector (7,5 с).Добавление массива 100 раз: MyLinkedList (80,7 с), ArrayList (82,5 с), Vector (92,7 с), LinkedList (176,3 с).Добавление массива 200 раз: ArrayList (304,3 с), Vector (332,7 с), MyLinkedList (381,2 с), LinkedList (610,4 с). Вывод: ArrayList всегда быстрее, чем Vector.Поскольку это не синхронизировано, это не очень удивительно.Хотя разница не слишком значительна.Если список не слишком велик (до 100 000 элементов в моем случае), я получил лучшую производительность с собственной реализацией.Удивительно, но LinkedList работает довольно плохо.По мере роста размера списка LinkedList становится все хуже и хуже.Окончательный вывод: если список не слишком большой, вы можете добиться лучшей производительности с собственной реализацией.Если размер списка очень большой, используйте ArrayList.Этот результат удивляет меня, потому что ArrayList должен перемещать много элементов, в то время как связанный список должен только изменить некоторые ссылки.Но поскольку ArrayList основан на массиве, несмотря на большое количество сдвигов, он может превзойти связанный список.

Дополнительная информация: Во всех четырех случаях при вставке нового элемента я перечисляюсписок с начала, пока я не найду элемент большего размера, затем я вставлю новый узел перед ним.Я делаю это, потому что приложение должно обрабатывать меньшие элементы.Вот почему я не выполняю бинарный поиск в Vector и ArrayList.

Answer 1

Я посмотрел на API LinkedList, но Я не нахожу методы для вставки до / после данного узла в списке.

Он существует, но он скрыт в интерфейсе ListIterator, возвращаемом методом LinkedList.listIterator().

Это сделано для того, чтобы не показывать сами узлы списка.

Answer 2

Вы можете рассмотреть TreeSet, если в вашем списке нет повторяющихся элементов. TreeSet хранит элементы в отсортированном порядке для вас. Это гарантирует log (n) время для добавления, удаления и т. Д.

Answer 3

Вы смотрели на TreeMap? Он будет автоматически отсортирован, как только вы введете новое значение.

Я также посмотрел на деревья (как в DefaultMutableTreeNode) и Документы (как в XML и DOM), которые я видел там, где они оба позволяют узлу иметь несколько дочерних элементов, в то время как мое понимание чистого LinkedList таково каждый узел имеет только одного родителя и одного потомка.

Надеюсь, это более полезно, чем мой последний пост ...

Answer 4

Какой тип обработки необходимо выполнить для меньших элементов перед вставкой нового элемента?

В Java я хочу хранить элементы в порядке возрастания по размеру. Перед вставкой мне нужно обработать все мелкие элементы. Поэтому я начинаю перечислять список, относящийся к меньшим элементам , и когда я встречаю более крупный элемент, я хочу вставить новый узел перед этим более крупным элементом. Какая структура данных будет хорошим выбором?

Я не совсем понимаю, что вам нужно делать, но вы можете взглянуть на структуру данных heap , которая реализована как java.util.PriorityQueue в Джава. Тем не менее, примите во внимание, что java.util.PriorityQueue обеспечивает отсортированное удаление элементов, но без отсортированной итерации элементов. См. Пример Java: как использовать PriorityQueue? .

Answer 5

Я смотрю на Java API, и в Java нет класса SortedList.Вы можете использовать утилиты Collections из java.util, такие как Collections.sort(listToSort, comparator) [ 1 ], чтобы получить желаемый порядок.

Вам придется либо использовать TreeSet, либо создать свой собственный класс SortedList, который обернет существующий интерфейс List и будет сортировать по add.

Answer 6

Ну, во-первых, вы можете использовать SortedList, который немедленно решит проблему для вас.

(За исключением, durn, SortedList был в моем воображении. Какой-то другой язык.)

Может помочь сортировка ArrayList #.

В противном случае вы хотите реализацию List, которая реализует [метод добавления двух параметров] [1].

[1]: http://download.oracle.com/javase/1.4.2/docs/api/java/util/List.html#add(int, java.lang.Object)