Получить ссылку на последний добавленный узел в java LinkedList

Question

Моя цель - удалить узел где-то в середине Java LinkedList объекта за O (1) время.

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

Как я могу получить ссылку на последний узел в объекте Java LinkedList? Затем я сохраню эти ссылки на карте для последующего использования.

Примечание: я знаю, что это выполнимо, если я реализую свой собственный LinkedList, но есть ли способ сделать это с помощью класса Java LinkedList?

Answer 1

Ближайшая вещь, которую вы можете получить по прямой ссылке, - это Iterator, которая указывает на конкретную c точку.

Если вы звоните remove() на такой Iterator it должно работать в O (1):

LinkedList<Object> linkedList = ...;
Iterator<Object> it = linkedList.iterator();
while (it.hasNext()) {
  if (matchesSomeCondition(it.next()) {
    it.remove();
  }
}

Обратите внимание, что этот пример кода определенно не работает в O (1), это конкретно просто вызов remove(), который может иметь такую ​​эффективность. Если вы еще не определили узел каким-либо образом (например, поместили Iterator в этом месте), то вы не сможете удалить элемент из LinkedList за O (1) раз.

Редактировать , и поскольку вы упомянули элемент "последний добавленный", то, возможно, вам стоит использовать ListIterator, поскольку он имеет метод add(). Если вы можете эффективно реализовать все ваши добавления / удаления, используя ListIterator, то вы можете свести операции обхода к LinkedList к минимуму. Фактически, если вы всегда используете индексы для добавления / удаления объектов из вашего LinkedList, тогда вы теряете большую часть его эффективности (поскольку каждый вызов add / remove должен сначала найти затронутый элемент посредством обхода).

Answer 2

Я бы предложил изменить структуру данных на LinkedHashSet вместо LinkedList. Причина этого в том, что LinkedHashSet#get() и remove() могут искать или удалять любой элемент по ключу за O(1) время. Кроме того, LinkedHashSet реализован со связанным списком, проходящим через записи. Порядок записей при повторении списка определяется порядком вставки, поэтому он ведет себя аналогично LinkedList в этом отношении.