Как эффективно удалить элемент из java LinkedList

Question

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

Например, если я прошел через узлы A -> B -> C -> A -> C, список, который мне нужен в конце, это [B, A, C].

Что я хотел сделать, так это использовать LinkedList, чтобы каждый узел в графе содержал ссылку на его узел в LinkedList. Затем каждый раз, когда я прохожу через узел, я удаляю его соответствующий узел из LinkedList и вставляю его снова в конец LinkedList, а сложность операции будет только O(1).

Однако, когда я начал реализовывать это, я столкнулся с проблемой: по-видимому, класс java LinkedList не позволяет мне видеть его фактические узлы списка. Использование регулярных функций удаления LinkedList для удаления узла списка, содержащего данный узел графа, будет O(n) вместо O(1), что отрицает всю цель использования LinkedList для начала.

Естественно, я могу реализовать LinkedList самостоятельно, но я бы предпочел избежать этого - мне кажется, что если мне нужно реализовать LinkedList в java, я делаю что-то неправильно.

Итак, есть ли способ решить эту проблему без реализации LinkedList самостоятельно? Есть что-то, что мне не хватает?

Answer 1

Как кажется, вы ожидаете встроенного подхода, я не думаю, что есть какая-либо коллекция, которая предоставляет такую ​​функциональность. Вам придется реализовать его самостоятельно, как предлагал @MartijinCourteaux. Или:

• использование отсортированного набора коллекция как TreeSet<E> с поддержкой стоимости O(log n) для операций: add, remove and contains.
• LinkedHashSet<E> Но остерегайтесь в отличие от HashSet<E>, LinkedHashSet может иметь O(1) ожидаемую производительность операций: add, contains, remove но производительность может быть чуть-чуть ниже, чем HashSet, из-за дополнительных расходов на поддержание связанного списка. Но мы можем использовать его без увеличения стоимости, связанной с TreeSet. Тем не менее, порядок вставки не изменяется, если элемент повторно вставлен в набор, поэтому попробуйте удалить первую вставку элемента перед повторной установкой его.

Answer 2

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

Answer 3

Если ваш связанный список большой, просто использование обычного списка массивов даст быструю производительность даже при перетасовке. Вы также должны рассмотреть использование хеш-наборов, если порядок не важен, связанный хеш-набор, если имеет значение порядок вставки, или набор деревьев, если вы хотите, чтобы он отсортировался. Они не позволяют дублировать значения, но имеют хорошую производительность O для вставки, удаления и их добавления.