Удаление всех дубликатов из общего связанного списка

Question

Это код, который у меня до сих пор, и он удаляет все первые экземпляры дубликатов, но если бы я получил повторяющийся элемент несколько раз, он удалит только первый экземпляр и оставьте остальные экземпляры этого элемента в списке.

//remove all duplicate items from list. 
// if list is null or empty leave it unchanged 

public static <T extends Comparable<? super T>> 
     void deleteReps(LinkedList<T> list) 
{ 
    for (int i = 0; i < list.size(); i++) 
    { 
     T item = list.get(i); 
     for(int j = i + 1; j < list.size(); j++) 
     { 
      if(item == null && list.get(j) == item || item != null && item.equals(list.get(j))) 
      { 
       list.remove(j); 
      } 
     } 
    } 
} 

Answer 1

Прежде всего, этот код не является эффективным для LinkedList с, так как get и remove принимают линейное время.

Во-вторых, когда вы удалите j 'го элемента из списка, вы должны уменьшать j, так как j+1 -м станет j «го элемента после удаления, так что без декремента j, ваш цикл будет пропускать некоторые из элементов списка, которые могут привести к тому, что некоторые дубликаты не будут удалены.

Answer 2

Следуя за ответом Эрана, я предлагаю вам перебирать список с помощью Iterator, поскольку он устраняет необходимость в ручных индексах, а также позволяет удалять элементы при повторении списка.

Answer 3

Когда вы удаляете элемент из списка, вы должны помнить, что это уменьшит индекс для каждого элемента после него в списке, а также размер списка.

EDIT

Как sharonbn предложил, вот метод работы с использованием итератора:

public static <T extends Comparable<? super T>> void deleteReps(LinkedList<T> list) 
{ 
    LinkedList<T> noRepsList = new LinkedList<T>(); 
    Iterator<T> itr = list.iterator(); 
    while(itr.hasNext()) 
    { 
     T currentTest = itr.next(); 
     if (!noRepsList.contains(currentTest)) 
      noRepsList.add(currentTest); 
     else 
      itr.remove(); 
    } 
} 

Это не может быть наиболее эффективным способом сделать это, поскольку это создает еще один список для сравнения объектов с но он выполняет свою работу.

Answer 4

С LinkedList вы имеете дело с ссылкой реализация объектов, которые связаны вместе с узлами. Узел содержит объект и ссылку на следующий узел. Вы должны стараться не перебирать LinkedList с помощью индексов, потому что когда вы начинаете удалять или добавляете узлы, индексы меняются. В отличие от массива, который будет содержать пробел, если вы удалите его содержимое, как только вы удалите узел из LinkedList, список уменьшится в размере, поскольку предыдущий узел теперь ссылается на узел, который пришел после того, который вы удалили, и удаленный узел теряется в памяти. Итак, в вашем примере вам нужно учитывать, что индекс изменится после удаления дубликата. По этой причине вы всегда должны пытаться пересечь LinkedList на Java через с ссылкой и не индексировать. В вашем случае это может сработать:

void deleteReps(LinkedList<T> list) 
{ 
    Node prev = head;       // A node to traverse with starts at the head 
    Node temp = head.getNext();    // A second node to traverse with 
    Node current = prev;      // The node in question 

    while(prev.getNext() != null)    // While the node after prev isn't the end 
    {           // of the list 
     T item = current.data;    // The item we are looking for duplicates of 

     while(temp != null)     // While temp isn't at the end of the list 
     { 
      if(temp.data == item)    // If the item in temp is the same as the 
      {         // item we are looking for 

       prev.setNext(temp.getNext()); // Set the next Node of prev to the node 
               // after temp. This "deletes" the Node 
               // at temp 
       prev = temp;     // prev is now temp 
       temp = temp.getNext();  // temp is the next Node 
      } 
      else        // Else if the item is different 
      { 
       prev = temp;     // prev is now temp 
       temp = temp.getNext();  // temp is now the next Node 
      } 
     } // end while 

     current = current.getNext();   // current is now the next Node 
               // so that the 
               // the next item we are looking for 
               // duplicates of is an item still in 
               // the LinkedList 
     prev = current; 
     temp = prev.getNext(); 
    } // end while        
} 

Я дал подробные комментарии, чтобы вы могли следовать логике этого алгоритма. Это учитывает сокращение LinkedList при удалении узлов, поскольку current.getNext() всегда будет узлом, который все еще находится в LinkedList после удаления дубликатов.