从通用链接列表中删除所有重复项

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

根据Eran的回答，我建议您应该使用Iterator迭代列表，因为它消除了手动索引的需要，并且在迭代列表时还允许删除项目。

Answer 2

当您从列表中删除元素时，您必须记住，这将减少列表中每个项目之后的索引以及列表的大小。

编辑

正如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 3

使用LinkedList，您将处理与节点链接在一起的对象的基于引用的实现。一个节点只包含一个对象和对下一个节点的引用。您应该尽量不要使用索引遍历LinkedList，因为当您开始删除或添加节点时，索引会发生变化。与数组不同，如果删除其内容，数组将保持空格为空，一旦从LinkedList中删除节点，列表的大小就会减小，因为上一个节点现在引用了删除的节点之后的节点，并且删除的节点在内存中丢失。因此，在您的示例中，您需要考虑删除重复项后索引会发生变化。因此，您应该始终尝试通过引用遍历Java中的LinkedList，而不是索引。在您的情况下，这可能会起作用：

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中的节点。