如何将项目添加到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.