如何将项目添加到Java中的链接列表中?
使用比较器和迭代器,我试图按顺序将对象添加到链接列表中。到目前为止,我有以下几点:如何将项目添加到Java中的链接列表中?
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);
}
}
我不能确定如何使用迭代器结合比较每一个元素添加到链表秩序。有人能帮我理解逻辑吗?
你的比较器是错误的。
比较方的一般合同的一部分是,如果compare(a, b)
为正数,则compare(b, a)
为负数。
如果您传入的比较器不符合比较合同,您将得到未定义的行为。
我不太清楚你的意思,请你详细说明一下。我会很感激它...... – littleK 2009-12-08 04:12:40
从比较接口的文档:“实现者必须确保'sgn(compare(x,y))== -sgn(compare(y,x))'对于所有的x和Y“。您的'比较'不符合该合同。 – 2009-12-08 04:23:09
@ behrk2 - 您的比较方法应为:public int compare(Integer int1,Integer int2){return int1.compareTo(int2); }这将使其符合Comparator和Comparable的合同 – Gennadiy 2009-12-08 04:23:36
我会写这样的:
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。
我们在做你的功课吗?您的问题似乎与比较器接口没有太大关系,因为您清楚地了解您希望它做什么。这听起来对我来说是一个提倡测试驱动开发风格的完美场所。首先编写测试插入到一个空列表中,插入到列表的头部,插入到尾部,插入长度为2的列表的中间。然后编写测试以返回第n个元素和具有给定值。在这些简单的例子工作之后,将很容易在有序列表中找到该元素,该元素是第一个大于要插入的元素的元素,并将该元素添加到较大的元素前面。不要忘记添加重复值的边缘情况,其值小于列表中的任何值,并且值大于列表中的任何值。
如果您实施add
方法按排序顺序(或除列表的末尾以外的任何位置)插入元素,则表明您违反了List
接口的合同。在语义上,它不是List
,并且将它传递给任何期望的代码是不安全的。假装实施List
界面只会导致麻烦。
怎么样使用TreeSet
?代替?
Set<Integer> list = new TreeSet<Integer>();
当然,Set
将不允许重复的元素。
如果你想要的东西,允许重复,但仍允许高效,有序检索,尝试基于堆的集合,如PriorityQueue
.
也有一些是关于这个问题很奇怪。 1)LinkedList是一个类而不是一个接口。 2)为什么要使用ArrayList实现“链表”?它将不具有真正链接列表的计算属性! – 2009-12-08 08:45:54
斯蒂芬C,你会建议我怎么实现它? – littleK 2009-12-08 17:22:43