Связанный список Java: удаление самого большого элемента с помощью итератора

Question

как я могу удалить самый большой элемент из связанного списка в Java?Я знаю, что могу использовать функции get () или remove () для извлечения / удаления элементов.Но я хочу сделать это эффективно.Я хочу использовать итератор.У вас есть идеи, как я могу это сделать?Обратите внимание, что я не хочу создавать свой собственный список ссылок.Я даже не хочу сортировать свой связанный список.

Можно ли выполнить линейный поиск для этого?Если так, как я могу отслеживать указатель (или итератор), который указывает на самый большой элемент.Любая помощь будет оценена.

Answer 1

Связанный список (если не отсортирован) не является лучшей структурой для того, что вы пытаетесь сделать здесь, так как у вас нет другого выбора, кроме как выполнить линейный поиск и удалить самый большой элемент

Integer biggest = Integer.MIN_VALUE;
for(Integer e : myList){
   if(biggest < e)
        biggest = e;
}
myList.remove(biggest);

это будет O (n), даже если вам придется сканировать снова, чтобы удалить самое большое, этого второго сканирования можно было бы избежать, если бы вы сделали свой собственный LinkedList, потому что java.util.LinkedList скрывает свой класс Entry и не позволяет Вы можете изменить указатели; но это был бы неправильный способ оптимизации, потому что если вместо этого вы используете структуру, подобную куче, в java, которая будет классом PriorityQueue, вы можете получить O (log (n)) и уменьшить код до:

return myPriorityQueue.poll();

Answer 2

если вы знаете, какой элемент самый большой, вы можете сделать это так

Iterator<Integer> it = list.iterator();
Integer toRemove;
while(it.hasNext()){
    if(toRemove.compareTo(it.next()==0){
       it.remove();
       break;
    }
}

или используйте list.removeFirstOccurrence (toRemove)

но реализации LinkedList не позволяют копировать итераторы для указания на конкретные элементы для последующего удаления