在Java中从LinkedList中移除重复元素

Question

我一直在做一个任务，让用户可以将对象输入到LinkedList中，同时也可以将它们删除。除了这个麻烦的部分——删除重复项，我的程序已经全部完成。我已经花费了一些时间，希望有人能指点我正确的方向。

下面的代码几乎可以工作……也就是说，它确实删除了重复项……但只有它遇到的第一个元素。那么，我该如何让程序查看第一个项目、删除它的重复项，然后回过头来对列表中的所有其他元素执行同样的操作呢？我应该像“previous”和“current”这样使用节点，尝试以这种方式遍历LinkedList吗？我的教授暗示需要两个while循环，但我尝试过的所有方法都没有正常工作。我应该把什么作为第二个（我想是外部）while循环的参数呢？

非常感谢您的帮助！

public void removeDuplicate() //searches the LinkedList for duplicate elements, and removes them
   {
   ListIterator iter = listIterator();

   Object uniqueO = iter.next();

        while (iter.hasNext())
        {
           String uniqueS = (String) uniqueO;
           Object compareO = iter.next();
           String compareS = (String) compareO;
           int x = uniqueS.compareTo(compareS);
           if (x == 0)
           {
               iter.remove();
           }
        }

} //end removeDuplicate

- Dreiak

Answer 1

这应该是一种固定的方式。

但如果您不想改变原始顺序，可以考虑以下方法：

//在这里，您可以将“set”视为一个不容忍重复数据的数据结构 :)

     public void removeDuplicate() //searches the LinkedList for duplicate elements, and removes them
   {
   ListIterator iter = listIterator();

    HashSet tempSet = new HashSet();


        while (iter.hasNext())
        {

        Object obj = iter.next();
                      if(tempSet.contains(obj))){
                          iter.remove();
                      }else{
                            tempSet.add(obj);
                      }
        }

} //end removeDuplicate

- biaobiaoqi

---

这绝对很有效！我想我不得不使用Set，它比我之前尝试的要容易得多...感谢您的帮助=] - Dreiak

Answer 2

如果空间不是问题，您可以将其复制到一个新列表中，在插入之前验证它是否尚未在新列表中：

public static LinkedList<Object> dedup(LinkedList<Object> original) {
    LinkedList<Object> copy = new LinkedList<Object>();

    for (Object o : original) {
        if (!copy.contains(o)) {
            copy.add(o);
        }
    }

    return copy;
}

您已经说明您已经有一个工作的add函数，并且您可以相对容易地实现一个简单的包含函数，用于您的LinkedList类：

public boolean contains(Object o) {
    ListIterator iter = listIterator();

    while (iter.hasNext()) {
        if (iter.next().equals(o)) {
            return true;
        }
    }

    return false;
}

- Jon Newmuis

---

我喜欢将列表复制到新列表的想法，因为空间绝对不是问题。感谢您的输入！ - Dreiak

Answer 3

private LinkedList<String> removeDups(LinkedList<String> linkedList){
    for(int i=0; i<linkedList.size(); i++){
        for(int j=i+1; j<linkedList.size(); j++){
            if(linkedList.get(i).equals(linkedList.get(j))){
                linkedList.remove(j);
            }
        }
    }
    return linkedList;
}

- Zin Win Htet

---

这简直让我发疯。所以如果你将for循环中的int更改为Integer，上面的代码就无法正常工作，即使它包含重复项也会返回linkedList原样输出。添加一些带有Integer的调试打印信息后，我们使用正确索引进入了if()函数来处理原始和重复项，但是似乎.remove无法正常工作。 - sabujp

我不知道，这个答案好像是很久以前的了。 - Zin Win Htet

哦，这是因为有一个remove(Object)和remove(int)方法。如果你正在使用整数进行迭代，那么你需要使用linkedList.remove((int) j)，然后它就可以工作了。 - sabujp

Answer 4

将其转换为Set，然后再转回List。 只需两行代码。

- user949300

---

请使用维护原始顺序的Set。 - Thilo

我们还没有在我的课程中讨论过集合，虽然我已经查阅了关于集合的资料，并且似乎理解了它在这种情况下的工作原理，但不幸的是，在这里它不是一个可选项... =/ - Dreiak

Answer 5

也许这可以帮助你，
新建一个哈希表，将链表节点的字符串值作为键，并在迭代列表时检查该键是否已经存在于哈希表中，如果是，则将其删除。

- Ivan

Answer 6

import java.util.HashSet;

import java.util.LinkedList; import java.util.Iterator;

public class DeletDuplicateNodeinLinkList {

public static void main(String[] args) {

    LinkedList<Integer> myLL = new LinkedList<Integer>();

    myLL.add(1231);
    myLL.add(12);
    myLL.add(12313);
    myLL.add(123);
    myLL.add(12313);
    myLL.add(1);
    myLL.add(1243242);
    System.out.println(myLL);

    myLL = deleteDups(myLL);
    System.out.println(myLL);
}

private static LinkedList<Integer> deleteDups(LinkedList<Integer> myLL) {
    // TODO Auto-generated method stub

    HashSet<Integer> myHashSet = new HashSet<Integer>();
    Iterator<Integer> itr;
    itr = myLL.iterator();

    while (itr.hasNext()) {
        if (!myHashSet.add(itr.next())) {
            itr.remove();
        }

    }

    return myLL;
}

}

- venkatesh