我有一个类项目,我必须从头开始构建一个基于 ADT 的链表(这意味着我不能使用任何标准的 Java ADT),然后使用它对一堆 State 进行排序
对象(每个对象还包含 Cities
的链接列表)按字母顺序排列。显然,代码的主干是手工制作的 OrderedLinkedList
类,而我在弄清楚如何具体实现迭代的 findOrAdd
方法时遇到了很多麻烦遍历列表,如果传递的参数尚未在列表中,则将其添加到适当的位置(如果元素已存在,则返回该元素)。我读过的关于实现链表的大部分内容都不涉及 ADT,因此很难在我的脑海中转换它并仍然关注它。我的(诚然不完整的)OLL 代码及其附带的迭代器:
import java.util.Iterator;
public class OrderedLinkedList<E extends Comparable<E>> implements Iterable<E>
{
private E first;
private E next;
private E last;
private E current;
private E temp;
private int size;
public OrderedLinkedList()
{
this.first = null;
this.next = null;
this.last = null;
this.current = null;
this.size = 0;
}
public E findOrAdd(E element)
{
E returnVal = null;
Iterator<E> listIter = this.iterator();
if (this.first == null)
{
this.first = element;
this.size++;
}
else
for (int i = 0; i < this.size; i++)
{
if (listIter.next().compareTo(element) == 1 && listIter.hasNext() == false)
{
temp = this.first;
this.first = element;
this.next = temp;
this.size++;
}
else if (listIter.next().compareTo(element) == 1 && listIter.hasNext() == true)
continue;
else if (listIter.next().compareTo(element) == 0)
returnVal = element;
else if (listIter.next().compareTo(element) == -1)
{
temp = this.next;
this.next = element;
}
}
return returnVal;
}
public Iterator<E> iterator()
{
return new OrdListIterator<E>();
}
private class OrdListIterator<E> implements Iterator<E>
{
private E nextNode;
public OrdListIterator()
{
//maybe something needed here
}
public boolean hasNext()
{
return (next != null);
}
public E next()
{
return (E) next;
}
public E first()
{
return (E) first;
}
public void remove()
{
//implement later
}
}
}
我在 State
和 City
类中提供了compareTo()方法,它们覆盖了通常的方法,但仍然以相同的方式工作。我在 findOrAdd
哪里出错了? 我怎么出错了?我并不是在寻找代码的完整更正或任何东西;我大约 99% 确信 else
block 下的所有内容都很糟糕。我只需要朝着正确的方向插入:找到一个立足点。我非常感谢任何建议。
最佳答案
我认为您的问题可能在于,您为每个条件调用 listIter.next()
可能意味着您在每次检查时都会插入迭代器。也许您应该将其存储在循环的开头,然后在比较中使用单个对象...
关于java - 从头开始实现ADT链表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33446204/