실제로 연결된 목록 추가 O (N) 또는 O (1)입니까?

Question

Linked List에서 추가 및 삭제가 일정 시간, 즉 O (1)에서 발생하지만 요소의 액세스는 목록의 크기 즉 O (N)에 비례하여 발생한다고합니다. 내 질문은 어떻게 그것을 제거하거나 요소를 추가 할 수 있습니다. 먼저 O (N) 순서의 추가 또는 삭제가 아닌 경우? 어떤 하나 stamps.remove (k)를 수행 그런 경우

    LinkedList stamps = new LinkedList(); 

    stamps.add(new Stamp("Brazil")); 
    stamps.add(new Stamp("Spain")); 
    --- 
    ---- 
    stamps.add(new Stamp("UnitedStates"); //say this is kth element in the list 
    ---- 
    stamps.add(new Stamp("India"); 

, 어떻게이 작업이 일정 시간에 발생할 수 :

우리는이 같은 API를 사용할 때 어떤 일이 발생, 자바의 예를 복용?

Answer 1

링크 된 목록에서 항목을 삭제하면 목록에있는 실제 노드를 가리키는 포인터가있는 경우에만 일정 시간 동안 작동합니다. 가지고있는 유일한 정보가 "n"번째 노드를 삭제하려는 정보라면 어떤 노드인지를 알 수있는 방법이 없습니다.이 경우 먼저 목록을 탐색해야합니다. 물론 O입니다. (엔).

추가는 목록에서 이미 포함 된 요소의 수와 연결되어 있지 않으므로 항상 일정 시간 동안 작동합니다. 제공된 예제에서 add()에 대한 모든 호출은 Stamp 클래스의 생성자를 호출하는 비용을 제외하고 O (1)입니다. 연결된 목록에 추가하는 것은 단순히 다른 요소를 끝에 붙이는 것입니다. 이것은 물론 연결된 목록의 구현이 현재 어떤 노드가 목록의 끝에 있는지 알고 있다고 가정합니다. 그것이 모르는 경우 전체 목록을 순회하는 것이 필요합니다.