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

Question

我已经创建了一个排序的链表，现在我正在尝试找出如何删除重复项。我想在我创建的add方法中添加能做到这一点的代码，但我似乎找不到答案。我觉得这应该是相对容易的，但我现在有点脑死亡。

在add方法中，我检查索引以查看要添加项的位置。"Index“是一个int变量，但我想检查" item "，一个可比较的，是否与存储在它之前的项相同。我想使用compareTo方法，但会得到一个类型不匹配的结果。有没有人有更好的办法呢？

下面是我的add方法的代码：

 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. A集合是一个集合...
3. 基于链表的集合将是次优的。例如，对于基于树的实现，插入与O(logN)相比是O(N)，对于基于哈希表的实现，插入是O(1) (假设它的大小合适)。respectively.

的示例是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!");
}

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