LinkedList : 중복 제거

Question

이 중복 문제는 알고 있지만 내 질문은 다릅니다.
이 코드의 몇 줄을 이해할 수있게 도와주세요.
단일 링크 된 목록에서 중복 노드를 제거합니다.

public class DeleteDuplicates { 

    static void deleteDups(LinkedListNode n) { 
     Hashtable table = new Hashtable(); 
     LinkedListNode previous = null; 
     while(n!=null) { 
      if(table.containsKey(n.data)) { 
       previous.next = n.next; 
      } else { 
       table.put(n.data, true); 
       previous = n; 
      } 
      System.out.println(n.next.data); 
      n = n.next; 
     } 
    } 

    public static void main(String[] args) { 
     LinkedListNode node_1 = new LinkedListNode("first");   
     LinkedListNode node_2 = new LinkedListNode("second"); 
     node_1.next = node_2; 
     LinkedListNode node_3 = new LinkedListNode("third"); 
     node_2.next = node_3; 
     LinkedListNode node_4 = new LinkedListNode("second"); 
     node_3.next = node_4; 

     LinkedListNode current = node_1; 
     deleteDups(current); 
     while (current != null) { 
      System.out.println(current.data); 
      current = current.next; 
     } 

    } 

} 

질문 나는되어있다 : 중복 노드를 건너 뛰는

1. 는 LinkedList의 n을 와서 어떻게? 나는 previous 노드의 사용법과 그것이 중복 노드를 건너 뛰는 것을 돕는 방법을 이해하지 못했습니다.
2. Hashtable의 사용은 얼마나 중요합니까? 다른 컬렉션 (예 : HashSet)을 사용할 수 있습니까?

Answer 1

질문 2에 이미 좋은 답변이 있으니 질문 1에만 집중할 것입니다. (실제로 각 게시물마다 질문 1 개만 물어보십시오.) 이것은 중복 제거가 작동하는 방법입니다.

루프를 통해 반복 할 때마다 previous은 노드 앞에있는 목록의 노드에 대한 참조를 보유합니다. 따라서 n이 node_4으로 설정되면 previous은 node_3으로 설정됩니다. 따라서 previous.next = n.next은 node_3.next = node_4.next과 같습니다. node_4.next의 값을 node_3.next = null과 동일하게 설정하면 node_3이 목록의 마지막 노드가되므로 결과적으로 목록에서 node_4가 제거됩니다.

만약, 대신 node_4가 중복되고, 그것은 n가 node_3 및 node_2.next = node_4 또는 일반 영어로 말을하는 것입니다 node_2.next = node_3.next에 해당 될 만든 변화 될 것이다, 중복 된 node_3는 다음 previous이 node_2 것이었다 "node_2 다음 노드를 node_4"로 설정하면 효과적으로 node_3이 목록에서 제거됩니다.

Answer 2

1) LinkedList는 중복 노드를 건너 뛰지 않고 매핑되며, 다음은 복제 후 항목을 가리 킵니다.
2) LinkedList 중복을 허용 생각하지만, Hashtable하지 않습니다 -> 당신은 중복을 검출 원하는 데이터 구조를 사용하여이

Answer 3

에서 결론을합니다.

구현 관점에서 해시는 특정 요소가 복제본인지 여부를 결정하기 위해 일정 시간을 사용 (상각)하므로 유용합니다.

API의 관점에서 볼 때 중복 항목이 없으므로 Collection.Set 인터페이스가 좋습니다.

따라서 HashSet을 사용하는 것은 매우 직관적 인 것처럼 보입니다. 특히 실제 노드 객체와 상관없이 중복 키에만 관심이 있기 때문에 더욱 그렇습니다.