LinkedList из Java не предоставил тип Node (который является private static внутренним классом) .
Так что вы не можете удалить его вв O(1), поскольку требуется последовательное сканирование.
Чтобы получить O(1), вам необходимо иметь доступ к типу Node, чтобы можно было удалить его без сканирования.
Вы должны написать это самостоятельно.К счастью, doubly linked list относительно легко написать, и это довольно полезная и забавная задача.
Как удалить с данным Node?
См.этот ответ: https://stackoverflow.com/a/54593530
Метод LinkedList.java -> removeNode() удалить данный узел без последовательного сканирования.
Код в этом ответе предназначен для односвязного списка,remove для двусвязного списка в некоторых случаях еще проще.
Советы:
- Если данный узел является конечным узлом в связанном списке,тогда вам также нужен предыдущий узел.
Но это для singly linked list, для doubly linked node сам узел содержит предыдущий узел, поэтому вам не нужно передавать предыдущий узел в метод removeNode().
Кстати
- Почему это выгодно?
linked list является самой базовой структурой (кроме arrayи bits) , на котором могут основываться некоторые другие очень простые структуры.
Например, queue и stack могут быть легко реализованы с помощью linked list. - Параллельный доступ
java.util.LinkedList не является поточно-ориентированным, вашему LRU может потребоваться некоторый параллельный контроль, но я не уверен.
Если нужно, тогда java.util.concurrent.ConcurrentLinkedDeque - хороший пример для ссылки.
@ Обновление LinkedHashMap
java.util.LinkedHashMap, представляет собой комбинацию хэш-таблицы и двусвязного списка.
Механизм:
- Расширяется
HashMap, чтобы получить сложность O(1) для обычных операций. - И использовать
doubly linked list для отслеживания порядка вставки.
headэто самый старый элемент, а tail это самый новый элемент.
Он может использоваться для указания некоторого типа кэша, хотя я не уверен, будет ли он полностью удовлетворять вашим требованиям.