1

これは重複した問題であることは知っていますが、私の質問は異なります。
このコードの数行を理解するのを手伝ってください。
単一のリンクされたリストから重複するノードを削除します。

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. LinkedListnが重複ノードをスキップするのはなぜですか? previousノードの使用と、ノードの重複をスキップするのにどのように役立つかを理解していませんでした。
  2. の使用はどのくらい重要Hashtableですか? たとえば、他のコレクションを使用できますHashSetか?
4

3 に答える 3

0

重複を検出するために、任意のデータ構造を使用できます。

実装の観点からは、特定の要素が重複しているかどうかを判断するのに (償却された) 一定の時間がかかるため、ハッシュは優れています。

API の観点から見ると、Collection.Setアイテムが重複しないことが保証されているため、インターフェイスは優れています。

特に、実際のノードオブジェクトに関係なく、重複キーのみに関心があるため、 a を使用するというあなたの考えはHashSet非常に直感的です。

于 2013-10-14T23:33:13.617 に答える