java - 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

You already have good answers to your question 2, so I'll just concentrate on question 1 (really you should only ask 1 question in each post, by the way). This is how the removal of the duplicate works:

In each iteration through your loop, previous holds a reference to the node in the list before the node n. So, when n is set to your node_4, previous is set to node_3. Therefore, previous.next = n.next is equivalent to node_3.next = node_4.next, which because you don't set a value for node_4.next is equivalent to node_3.next = null, which has the effect of making node_3 the last node in the list, thus removing node_4 from the list.

If, instead of node_4 being the duplicate, it was node_3 that was duplicated, then previous would be node_2, n would be node_3 and the change made would be equivalent to node_2.next = node_3.next, which is to say node_2.next = node_4 or in plain English, "make the next node after node_2 be node_4", effectively removing node_3 from the list.

Answer 2

1) LinkedList 没有跳过重复节点，它正在被映射出来 - next 指向重复之后的条目。
2）认为LinkedList允许重复，但Hashtable不允许 -> 从中得出结论

Answer 3

您可以使用任何您喜欢的数据结构来检测重复项。

从实现的角度来看，散列很好，因为它们需要（摊销的）恒定时间来确定特定元素是否是重复的。

从 API 的角度来看，该Collection.Set接口很好，因为它保证没有重复项。

因此，您使用 a 的想法HashSet似乎非常直观，尤其是因为您只对重复键感兴趣，而不考虑实际的节点对象。