在已排序的鏈接列表中查找重複項

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. 的集合，沒有重複是一家集...

3. 基於鏈接列出了一組將是最理想的。例如，插入爲O(N)，而基於樹的實現則爲O(logN)，而基於哈希表的實現（假設其大小適當）則爲O(1)。分別爲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!"); 
} 

這是所有關於使用代碼，你已經寫好。