Java 연결 목록 : Iterator를 사용하여 최대 요소 제거

Question

Java의 연결 목록에서 가장 큰 요소를 제거하려면 어떻게해야합니까? get() 또는 remove() 함수를 사용하여 요소를 검색/제거 할 수 있다는 것을 알고 있습니다. 그러나 나는 그것을 효율적으로 만들고 싶다. iterator를 사용하고 싶다. 어떻게 할 수 있니? 참고로 나는 자신의 연결 목록을 만들고 싶지 않습니다. 나는 심지어 나의 linkedlist를 분류하고 싶지 않다.

선형 검색을 수행 할 수 있습니까? 그렇다면 가장 큰 요소를 가리키는 포인터 (또는 반복자)를 어떻게 추적 할 수 있습니까? 어떤 도움을 주시면 감사하겠습니다.

Answer 1

링크 된 목록 (정렬하지 않는 한) 당신이 다른 옵션이 없기 때문에이 될 것이다 가장 큰 요소

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

을 선형 검색을 제거보다 여기에 무엇을하려고에 가장 적합한 구조가 아니다 O (n), 가장 큰 것을 제거하기 위해 다시 스캔해야 할지라도 java.util.LinkedList가 Entry 클래스를 숨기고 사용자가 포인터를 수정할 수 없기 때문에 자신의 LinkedList를 작성한 경우이 두 번째 스캔을 피할 수 있습니다. 당신이 PriorityQueue 인 클래스가 될 것이라고 자바, 구조 등의 힙을 대신 사용하면 있기 때문에 즉, 최적화 할 수있는 잘못된 방법이 될 것입니다, 당신은 O (로그 (N))를 얻을에 코드를 줄일 수 :

return myPriorityQueue.poll(); 

Answer 2

당신은 큰 요소는

을 list.removeFirstOccurrence (toRemove)를 너무

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

처럼을하거나 사용할 수 있습니다 무엇인지 알고 있지만, LinkedList의 구현을위한 특정 요소를 가리키는 반복자를 복사를 허용하지 않는 경우 나중에 제거