在排序的链表中查找重复项

Question

我已经创建了一个排序的链接列表，现在我正在尝试找出如何删除重复项。我想在我创建的 Add 方法中添加执行此操作的代码，但我似乎无法弄清楚。我觉得这应该相对容易，但我现在有点脑死亡。

在我的添加方法中，我检查索引以查看要添加项目的位置。 “Index”是一个 int 变量，但我想检查“item”（可比较的）是否是之前存储的相同项目。我想使用compareTo方法，但我会得到类型不匹配的结果。有谁知道更好的方法来做到这一点？

这是我的添加方法的代码：

 package sortedListReferenceBased;

     public class SortedListReferenceBasedIterativeNoDuplicates
     implements SortedListInterface {

     // reference to linked list of items
     private Node head; 
     private int numItems; // number of items in list

     public SortedListReferenceBasedIterativeNoDuplicates() {
     numItems = 0;
     head = null;
     }  // end default constructor

      public boolean sortedIsEmpty() {
        return numItems == 0;
      //TODO
     }  // end sortedIsEmpty

     public int sortedSize() {
  return numItems;
      //TODO
     }  // end sortedSize

      private Node find(int index) {
     // --------------------------------------------------
     // Locates a specified node in a linked list.
     // Precondition: index is the number of the desired
    // node. Assumes that 1 <= index <= numItems+1
    // Postcondition: Returns a reference to the desired 
   // node.
  // --------------------------------------------------
  Node curr = head;
  for (int skip = 1; skip < index; skip++) {
   curr = curr.getNext();
} // end for
return curr;
  } // end find


  public Comparable sortedGet(int index) 
                throws ListIndexOutOfBoundsException {
      if (index >= 1 && index <= numItems){
          Node curr = find(index);
          Object dataItem = curr.getItem();
          return (Comparable) dataItem;
      }
      else {
          throw new ListIndexOutOfBoundsException("List index out of bounds on   get.");
  }
    //TODO
  } // end sortedGet()


  public void sortedAdd(Comparable item) throws ListException{ 
   int index = locateIndex(item); //to find location where item should be added
   if( index >=1 && index <= numItems+1){
       //if adding an item to the very beginning of list
       if (index == 1){
           Node newNode = new Node(item,head);
           head = newNode;
       }
       if (item.compareTo(something something?)== 0){ //if item is a duplicate of previous item do nothing
           System.out.println("No duplicates!");
       }

       //advances 
       else {
           Node prev = find(index-1); //finds out where previous node is
           Node newNode = new Node(item, prev.getNext()); //creates Node with item you wish to add
           prev.setNext(newNode); //links new node with previous node
          }
          numItems++;  
      }//end main if statement
      else {
           throw new ListIndexOutOfBoundsException("List index out of bounds on add.");
      }
    //TODO
  }  // end sortedAdd()


  public void sortedRemove(Comparable item) throws ListException {
      int index = locateIndex(item);
      if (index >= 1 && index <= numItems){ //if the index is greater than 1 (meaning list not empty) and
                                              //index doesn't exceed list size do the following:
      //if index is value of one then delete first node in this special way
      if (index == 1) {
          head = head.getNext();
      }
    //if there is only one item in the list then set head to nothing so index out of bounds error won't occur
      if (numItems == 1){
          head = null;
      }
      else { //if none of these things occur go ahead and delete item, allocating Nodes accordingly
          Node prev = find(index-1);
          Node curr = prev.getNext();
          prev.setNext(curr.getNext());
      }
      numItems--;//must account for one less item
      }
  if (!sortedIsEmpty()){
      System.out.println("Item does not exist!");
  }
  else { //if index doesn't meet if statement requirements 
      throw new ListIndexOutOfBoundsException("List index out of bounds on remove.");
  }

//TODO
 } // end sortedRemove


 public void sortedRemoveAll() {
   // setting head to null causes list to be
   // unreachable and thus marked for garbage 
   // collection
   head = null;
   numItems = 0;
 } // end sortedRemoveAll


 //Returns the position where item belongs or exists in a sorted list;
 //item and the list are unchanged.
 public int locateIndex(Comparable item) {
     Node curr = head;
     for (int i = 1; i <= sortedSize(); i++){
         if (item.compareTo(curr.getItem())<= 0){
            return i;
        }//end if

         else {
             curr = curr.getNext();
         }//end else
     }//end for
     return sortedSize()+1; 
    //TODO
 } //end locateIndex()




} // end ListReferenceBased

对于奇怪的格式，我深表歉意。现在情况相当艰难。如果这个问题真的很明显，我也很抱歉！哈哈

Answer 1

初步要点：

1. 我不明白为什么你似乎试图在 Java 中实现链表......鉴于已经有一个以 java.util.LinkedList 形式的完美实现 >.

2. 没有重复项的集合是一个集合...

3. 基于链表的集合将是次优的。例如，与基于树的实现的 O(logN) 和哈希表的 O(1) 相比，插入的时间为 O(N)基于实现（假设其大小适当）。 java.util.TreeSet 和 java.util.HashSet 分别是示例。

话虽如此，假设您实际上想要洞察/提示...

如果您有一个预先排序的链表，那么删除重复项的方法是逐步遍历节点，比较 node.value与node.next.value。如果值相等，则您发现了重复项，您可以通过将 node.next 更改为 node.next.next 来删除它。您的代码还需要应对各种“边缘情况”；例如包含 0 或 1 个元素的列表等。

Answer 2

您决定使用链接列表吗？使用内置的 TreeSet 似乎更自然地适合这个。

Answer 3

尝试

if (locateIndex(item) != (sortedSize() + 1)) { //locateIndex returns sortedSize() + 1 if it didn't find the item, so we check that

    System.out.println("No duplicates!");
}

这一切都是关于使用您已经编写的代码。