Java связанный список, который поддерживает быстрое удаление любых узлов?

Question

java.util.LinkedList не позволяет вам быстро удалить данный объект из списка. Метод remove (object) выполняет линейный поиск, чтобы найти объект в списке и удалить его. Поскольку это двойной связанный список, было бы неплохо удалить его, просто обновив указатели (node.prev и node.next).

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

ПРИМЕЧАНИЕ 1. Я не хочу удалять во время итерации. Я знаю, что это быстро, но я в первую очередь не перебираю свои элементы.

ПРИМЕЧАНИЕ 2. Для простоты: учитывая, что объект O, о котором я знаю, находится в двойном связанном списке, я хочу быстро удалить O из этого списка (путем обновления указателей) без необходимости линейного поиска в список, как делает java.util.LinkedList.

Answer 1

Вам следует взглянуть на класс LinkedHashSet .По сути, это HashSet, который поддерживает двусвязный список среди своих записей.Он поддерживает поиск (и, следовательно, также удаление) элемента в O (1) (надеюсь).Проверьте ссылку на спецификацию о том, как он обрабатывает порядок элементов в случае повторной вставки записи, и другие детали.

РЕДАКТИРОВАТЬ:

Если вам нужно хранить дубликатыВы можете взглянуть на Guava LinkedHashMultiset (до сих пор не использовался).Руководство пользователя Guava для Multiset: здесь .

Answer 2

Могу поспорить, что реализация LinkedList#remove() действительно удаляет ее, обновляя указатели на предыдущий и следующий элементы - проблема в том, что она должна перебирать все объекты, пока не найдет подходящий для удаления.

Если вы хотите, чтобы коллекция удалялась быстрее, без перебора всех объектов, используйте Set или Map.

Answer 3

Я в основном программист на Си, изучающий Java.Я нашел этот поток, потому что мне также было интересно, почему не было реализации связанного списка, где вы могли бы просто удалить объект напрямую, не ища его.Линейный поиск невероятно неэффективен.Список, поддерживаемый хеш-таблицей, лучше, но вы не знаете, как будет работать хеш-таблица.

Причина, по которой вы можете легко сделать это в C, состоит в том, что обычно сам объект элемента списка содержитследующий и предыдущий указатели, поэтому, учитывая объект, просто манипулировать парой указателей, чтобы удалить элемент из списка, поэтому это операция O (1).В Java у вас есть объект, но у вас нет прямого доступа к указателям, потому что они хранятся отдельно в списке.Таким образом, вы должны искать объект либо линейно, либо с помощью хеш-таблицы.

Кажется, что эту проблему можно решить, создав реализацию связанного списка, в которой каждый тип объекта, добавленный в список, должен будет реализоватьИнтерфейс LinkedListElement, который будет поддерживать получение и установку следующих и предыдущих указателей.Вам нужно будет добавить следующий и предыдущий указатели в ваш класс и реализовать функции для их получения и установки.Тогда класс списка ссылок сможет легко удалить объект, поскольку сам объект содержит указатели.

Answer 4

Похоже, вам нужен составной объект. Создайте класс, содержащий ваш список, и в то же время сохраняйте индекс в этом списке.

Таким образом, когда вы хотите выполнить быстрое удаление, вы выполняете поиск индекса с постоянным временем, чтобы получить ссылку на элемент списка, который вы хотите удалить, после чего следует удаление с постоянным временем.

Answer 5

Возможно, карта будет уместной.Это дает ожидаемое O (1) время удаления.Но опять же, вы не указали, что означает fast .

Список, поддерживаемый BST, также может работать.Это дало бы log (n) время удаления.

Для решений, перечисленных здесь, я предполагал что-то более быстрое, чем итерация по списку, поэтому что-нибудь быстрее, чем O (n);

Answer 6

Как правило, вы хотите работать, используя ListIterator, где это возможно. Это remove будет постоянным временем.

Стандартная библиотека Java не имеет отдельной структуры узлов связанного списка, поэтому я думаю, ListIterator - лучший вариант.