如何將項目添加到Java中的鏈接列表中？

Question

使用比較器和迭代器，我試圖按順序將對象添加到鏈接列表中。到目前爲止，我有以下幾點：

public class ComparatorClass implements Comparator<Integer> { 
    public int compare(Integer int1, Integer int2) { 
     return int1.compareTo(int2); 
    } 
} 

和：

import java.util.ArrayList; 
import java.util.Comparator; 
import java.util.Iterator; 

public class OrderedListInheritance implements LinkedList { 

    ArrayList<Object> myList = new ArrayList<Object>(); 

    Comparator comp = new ComparatorClass(); 

    OrderedListInheritance(Comparator c) { 
     this.comp = c; 
    } 

    @Override 
    public void add(Object o) { 
     addLast(o); 
    } 

    @Override 
    public void addAtIndex(int index, Object o) { 
     Iterator it = getIterator(); 
     while (it.hasNext()) { 
      Object element = it.next(); 
      if (comp.compare(element, o) < 0) { 

     }else if (comp.compare(element, o) == 0) { 

     }else{ 
      myList.add(o); 
     } 
     } 
    } 

    @Override 
    public void addFirst(Object o) { 
     addAtIndex(0, o); 
    } 

    @Override 
    public void addLast(Object o) { 
     addAtIndex(myList.size(), o); 
    } 

    @Override 
    public Object get(int index) { 
     return myList.get(index); 
    } 

    @Override 
    public Iterator getIterator() { 
     Iterator iter = myList.iterator(); 
     return iter; 
    } 

    @Override 
    public int indexOf(Object o) { 
     return myList.indexOf(o); 
    } 

} 

我不能確定如何使用迭代器結合比較每一個元素添加到鏈表秩序。有人能幫我理解邏輯嗎？

Answer 1

你的比較器是錯誤的。

比較方的一般合同的一部分是，如果compare(a, b)爲正數，則compare(b, a)爲負數。

如果您傳入的比較器不符合比較合同，您將得到未定義的行爲。

Answer 2

是否有任何理由不能僅僅使用正常的ArrayList然後致電Collections.sort(list)或Collections.sort(list, comparator)？

Answer 3

我會寫這樣的：

public class IntegerComparator 
    implements Comparator<Integer> 
{ 
    public int compare(final Integer a, final Integer b) 
    { 
     return (a.compareTo(b)); 
    } 
} 

我要評論更多的代碼...但你給什麼都不行......你聲明一個ArrayList但後來想使用一個比較器，你不會鑄造...所以不會編譯。

另一個問題是，你不應該使用== 1，你應該使用< 0和> 0，因爲比較器可能不會返回1，0，-1而是其他數字。你也沒有處理所有的情況下，一個< b，a == b和a> b。

Answer 4

我們在做你的功課嗎？您的問題似乎與比較器接口沒有太大關係，因爲您清楚地瞭解您希望它做什麼。這聽起來對我來說是一個提倡測試驅動開發風格的完美場所。首先編寫測試插入到一個空列表中，插入到列表的頭部，插入到尾部，插入長度爲2的列表的中間。然後編寫測試以返回第n個元素和具有給定值。在這些簡單的例子工作之後，將很容易在有序列表中找到該元素，該元素是第一個大於要插入的元素的元素，並將該元素添加到較大的元素前面。不要忘記添加重複值的邊緣情況，其值小於列表中的任何值，並且值大於列表中的任何值。

Answer 5

如果您實施add方法按排序順序（或除列表的末尾以外的任何位置）插入元素，則表明您違反了List接口的合同。在語義上，它不是List，並且將它傳遞給任何期望的代碼是不安全的。假裝實施List界面只會導致麻煩。

怎麼樣使用TreeSet？代替？

Set<Integer> list = new TreeSet<Integer>(); 

當然，Set將不允許重複的元素。

如果你想要的東西，允許重複，但仍允許高效，有序檢索，嘗試基於堆的集合，如PriorityQueue.