java - 添加到单链表时自动按字段对对象进行排序？

Question

我正在编写一个单链表，它能够在对象输入到列表中时按特定字段对对象进行排序。它不是添加所有内容，然后排序，而是在实际添加之前检查将添加的位置。这样，我为三种不同类型的排序列表开发了一个正则表达式。我的问题具体是关于在添加对象时按变量自动对对象进行排序。

private void addDescending(E item)
{
     if(head == null)
     {
          head = new Node<E>(item, null);
          size++;
     }
     else
     {
          Node<E> p = head;
          while(p.next != null)
          {
               if(p.data.compareTo(item) > 0)
               {
                    Node<E> n = findPrev(p);
                    if(n == null)
                    {
                         Node<E> p1 = head;
                         head = new Node<E>(item, p1);
                         size++;
                         break;
                    }
                    n.next = new Node<E>(item, p);
                    size++;
                    break;
               }
          }
     }
}

public int compareTo(Object o)
{
     if(init == ((Person)(o)).getAge())
     {
          return 0;
     }
     else if(init > ((Person)(o)).getAge())
     {
          return 1;
     }
     else
     {
          return -1;
     }
}

compareTo(Object o)方法在Person内类(class)。 findPrev(Node<E> currentNode)类似于 node.previous在双链表中。对于我的项目，单链表更容易实现。

该访问在类中是私有(private)的，但有一个 public add(E item) 。 首先，它检查头部是否为空，如果不存在则创建一个。如果头部存在，则与头部进行比较。比较代码位于 Person类。

它检查 p.data检查为 Person获取它并将其与 Person 进行比较正在添加的对象的年龄。如果它更大，它就在前面。如果它更小，它就会追随。如果介于两者之间，则它位于较大数字之前和较小数字之前。这意味着头部可能小于添加的数字，因此新头部成为更大的数字，旧头部成为下一个。

在我的主要内容中，我添加了四个 Person对象。他们的测试年龄为 3 岁、10 岁、9 岁和 6 岁。由于名称并不重要，因此它们只是 Test1 到 Test4。由于某种原因，它只添加第一个对象。有几次，我让它添加了四个对象，但四个对象是同一对象，即使这四个对象都不同。为什么它会重复添加相同的对象或仅添加单个对象？

编辑:我刚刚重做并更新了代码。这是addDescending(E item)现在的方法。

private boolean addDescending(E item)
{
    if(head == null)
    {
        head = new Node<E>(item, null);
        size++;
    }
    else
    {
        Node<E> p = head;       
        if(head.next == null && p.data.compareTo(item) > 0)
        {
            p.next = new Node<E>(item, null);
            head = p;
            size++;
            return true;
        }
        else if(head.next == null && p.data.compareTo(item) < 0)
        {
            head.next = new Node<E>(item, null);
            size++;
            return true;
        }

        while(p.next != null && p.data.compareTo(item) < 0)
        {                                       
            if(p.data.compareTo(item) > 0)
            {
                Node<E> n = findPrev(p);
                Node<E> p1 = p.next;
                p.next = new Node<E>(item, p1);
                size++;
                return true;
            }
        p = p.next;
        }
    }
    return false;
}

此代码根据输入年龄检查每个节点的对象年龄。如果当前节点对象年龄大于输入，则转到下一个节点，直到找到小于它的节点。然后它获取上一个和下一个节点，创建一个新节点并将其自身放置在这两个节点之间。

但是，我的输入仍然是四个 Person 对象。我按顺序添加 3、10、9 和 6 岁。

预期的结果是最初创建一个带有对象的 age 的头。如3，那么加10的时候，10大于3，所以会加在head之前，成为新的head。将添加 6，检查 10，并且由于 10 大于 6，因此移动到下一个节点。下一个节点 3 小于 6，因此它将在 10 和 3 之间添加自己。与 9 类似，但在 10 和 6 之间。

这个问题我不太确定。正如我所说，我有四个输入。我现在得到两个对象，但它们都是相同的。带有 name = "Test1"; 的对象和age = 3; 。除了这两个之外，我没有看到任何其他对象，并且我可以保证它们每个只输入一次。

Edit2:这是创建 Person 对象、列表构造函数的正则表达式、get、get 结果和输出的代码。

构造函数和正则表达式:

public LList(String regex) throws IllegalArgumentException
{
    size = 0;
    this.regex = regex;
    head = null;
    if(!(regex.equals("A") || regex.equals("D") || regex.equals("U")))
    {
        throw new IllegalArgumentException("Unexpected Regex");
    }
}

public void add(E item)
{
    if(regex.equals("D"))
    {
        addDescending(item);
    }
    else if(regex.equals("A"))
    {
        addAscending(item);
    }
    else if(regex.equals("U"))
    {
        addUnsorted(item);
    }
}

获取:

public E get(int index)
{
    int i = 0;
    Node<E> p = head;
    if(index == 0 && head != null)
    {
        return head.data;
    }
    else
    {
        while(p.next != null)
        {
            if(i == index)
            {
                return p.data;
            }
            p = p.next;
            i++;
        }
    }
    return null;
}

主要:

Person ch0 = new Person("Test1", 3);
Person ch1 = new Person("Test2", 10);
Person ch2 = new Person("Test3", 9);
Person ch3 = new Person("Test4", 6);

// Create Descending Order List
System.out.printf("Descending List%n%n");
System.out.printf("%-10s %-4s%n", "Name", "Age");
System.out.printf("%-10s %-4s%n", "----------", "---");

LList<Person> dList = new LList<Person>("D");
dList.add(ch0);
dList.add(ch1);
dList.add(ch2);
dList.add(ch3);


dList.get(0).print();
dList.get(1).print();
dList.get(2).print();
dList.get(3).print();

人物打印方法:

System.out.printf("%-10s %-4d%n", name, age);

感谢您的帮助!

Answer 1

我的 2 克拉:

private boolean addDescending(E item){
    if(head == null){ //case new list
        head = new Node<E>(item, null);
        size++;
        return true;
    } else if(head.data.compareTo(item)>0){ // case insert befor head
        head = new Node<E>(item, head);
        size++;
        return true; 
    } else {
        Node<E> p; 
        for(p = head;p.next!=null; p=p.next){//compare all except head
           if(p.next.data.compareTo(item) > 0){
              p.next = new Node<E>(item, p.next);
              size++;
              return true;
           }
         }
         //not found: insert at the end
         p.next = new Node<E>(item, null);
         size++;
         return true;
     }
}