从零开始实现一个ADT链表

Question

我有一个 class 项目，我必须从头开始构建一个基于 ADT 的链表（这意味着我不能使用任何标准 Java ADT）然后用它来按字母顺序对一堆 State 对象（每个对象还包含 Cities 的链表）进行排序。代码的 backbone 显然是手工制作的 OrderedLinkedList class，我在弄清楚如何实施时遇到了很多麻烦，特别是 findOrAdd 方法遍历列表，如果传递的参数不在列表中，则将其添加到适当的位置（如果元素已经存在，则添加 returns 元素）。我读过的关于实现链表的大部分内容都与 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 class 中有 compareTo() 方法，它们覆盖了通常的方法，但仍然以相同的方式运行。 findOrAdd 我哪里出错了？怎么我哪里出错了？我不是在寻找对代码或任何东西的完全修正；我大约 99% 确定 else 块下的所有内容都很糟糕。我只需要朝着正确的方向推动：找个立足点。如果有任何建议，我将不胜感激。

Answer 1

我认为您的问题可能在于您为每个条件调用 listIter.next() 可能意味着您在每次检查时都在推动迭代器。可能您应该在循环开始时存储它，然后在比较中使用单个对象...

从零开始实现一个ADT链表

Implementing an ADT linked list from scratch

java

linked-list

add