如何实现排序的自定义列表类

Question

所以我有一个名为

List

的类和一个名为

SortedList

的类，它继承了 List 类。还有一个类称为节点。我创建了另一个包含打印方法的类。

但是，例如，每次我插入三个名字，并且我调用打印方法时，它只打印我插入的姓氏。所以我的问题是：这段代码是否会生成一个排序列表？如果是这样，为什么它只打印姓氏？

列出班级：

public class List {

    protected Node head;
    protected int length;

    public void list()
    {
        head=null;
        length=0;
    }
    public boolean isEmpty()
    {
        return head==null;
    }
    public Node insert(Item a)
    {
        length++;
        head=new Node(a, head);
        return head;
    }

排序列表类：

public class SortList extends List {

    private Node head;
    public SortList()
    {
        this.head=null;
    }
    public Node getFirst()
    {
        return head;
    }
    public Node Insert(Item newitem)
    {
        Node node = new Node(newitem);
        Node previous = null;
        Node current = head;
        while(current!=null && current.getValue().less(newitem))
        {
            previous=current;
            current=current.getNext();
        }
        if(previous==null)
        {
            head=node;
        }
        else
        {
            previous.setNext(node);
            node.setNext(current);
        }
        return head;
    }
    public void printlist()
{

    Node current = head; //ΑΡΧΗ ΤΗΣ ΛΙΣΤΑΣ.
    while(current!=null)
    {
        current.print();
        current = current.getNext();
    }
}

节点类：

public class Node {

    private Item info;
    private Node next;
    public Node(Item dat)
    {
        info=dat;
    }
    public Node (Item dat, Node b)
    {
        info=dat;
        next=b;
    }
    public Item getValue()
    {
        return info;
    }
    public void setNext(Node a)
    {
        next=a;
    }
    public Node getNext()
    {
        return next;
    }
    public void print()
    {
        info.print();
    }
}

Answer 1

在

List

的实现中，

insert()

方法中有一个重大错误：

public Node insert(Item a)
{
    length++;
    head=new Node(a, head);
    return head;
}

您不会将新元素附加到列表的末尾，而是每次都替换列表的头部，从而丢弃前一个元素。

这可以解释为什么您总是只能看到插入的最后一个元素。

编辑： 事实证明，

insert()

方法确实有效，因为您在节点的构造函数中设置了对下一个节点的引用。

但是，在排序列表中，您有一个未设置下一个节点的插入情况：

if(previous==null)
{
    head=node;

}

在您的排序列表中，您不会在节点的构造函数中设置下一个元素。在所有其他情况下，您可以在

insert()

方法中设置下一个元素，但在本例中则不然。如果您要插入的元素是列表中最小的元素，则

previous

为 null，这是正确的 - 您的新元素是列表中的新

head

。然而，由于您没有设置新元素的后继者，列表中的所有元素现在都消失了。

如果插入到列表中的最后一个元素是最小的，则最后一个元素也将是唯一剩余的元素，并且仅打印出最后一个元素。

尝试设置后继者：

if(previous==null)
{
    head=node;
    head.setNext(current);
}