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 (кстати, вы должны задать только один вопрос в каждом посте, кстати). Вот как выполняется удаление дубликатов:

На каждой итерации через ваш цикл previous содержит ссылку на узел в списке перед узлом n. Итак, если для 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 является дубликатом, это было node_3, что дублируется, то previous будет node_2, n бы node_3 и изменения, внесенные будет эквивалентно node_2.next = node_3.next, что сказать node_2.next = node_4 или на простом английском языке, «сделать следующий узел после node_2 be node_4», эффективно удаляя node_3 из списка.

Answer 2

1) LinkedList не пропускает дублирующий узел, он отображается на карте - следующий указывает на запись после дубликата.
2) Подумайте LinkedList позволяет дубликаты, но Hashtable не -> сделать свой вывод из этого

Answer 3

Вы можете использовать любую структуру данных, который вы хотите для обнаружения дубликатов.

С точки зрения реализации хеши хорошо, потому что они принимают (амортизируют) постоянное время, чтобы определить, является ли конкретный элемент двойным.

С точки зрения API, интерфейс Collection.Set хорош, потому что он не гарантирует дублирование элементов.

Итак, ваша идея использования HashSet кажется очень интуитивной, особенно потому, что вас интересуют только дублирующие ключи, не обращая внимания на фактический объект узла.