按升序对双向链表进行排序

Question

我需要根据 ID 的升序对包含 ID、姓名、年龄和 GPA 的学生列表进行排序。我的方法 insertAscending 正试图这样做，但由于某种原因无法正常工作。我的私人内部节点 class 也包括在内。任何帮助将不胜感激。

public class StudentInfo
{
    //Node class (inner class)
    private class Node
    {
        private int id;
        private String name;
        private int age;
        private double gpa;
        private Node next;
        private Node prev;


        //constructor of Node
        private Node(int id, String name, int age, double gpa, Node prev, Node next)
        {
            this.id = id;
            this.name = name;
            this.age = age;
            this.gpa = gpa;
            this.prev = prev;
            this.next = next;

        }
    }
   /*******************************************************************/

   private Node head;
   private Node tail;
   int size;
   //constructor of list
   public StudentInfo()
   {
       head = null;
       tail = null;
   }
   /*********************************************************************/

   public void insertAscending(int id, String name, int age, double gpa)
   {



     if (head == null)
     { 
         head = tail = new Node(id, name, age, gpa, null, null );
         size ++;

     }

     //insert at beginning
     else if( id < head.id)
     {

         head = new Node(id, name, age, gpa, null, head);
         size ++;

     }


     //insert at end
     else if(id > tail.id)
     {
         tail = new Node(id, name, age, gpa, tail, null);
         size++;
     }

     //insert at other positions 
     else 
     {
         for(Node temp = head; temp.next != null; temp = temp.next)
         {
             if (id > temp.id && id < temp.next.id)
             {
                 temp.next = new Node(id, name, age, gpa, temp, temp.next);
                 temp.next.next.prev = temp.next;
                 size++;
                 break;
             }
         }
     }

   }
}

Answer 1

这是作业的一部分吗？你必须为此使用双向链表吗？

保持 LinkedList 有序排列会抵消 LinkedList 的很多好处，即在头部和尾部插入 O(1)。通常这对我来说听起来像是 TreeMap 的工作，其中键是学生 ID，值是学生 object。这将使您按学生 ID 顺序迭代并加快查找速度。

至于您使用此代码的实际问题，我认为您忘记更新列表中已有节点（不是您要插入的节点）的某些 heads/tails。例如，我认为你的 else/if 梯子添加新尾巴的部分应该是这样的：

else if(id > tail.id)
{
     Node newTail = new Node(id, name, age, gpa, tail, null);
     tail.next = newTail;
     tail = newTail;
     size++;
}

之前你没有更新旧尾巴的next指针。同样，我认为您设置新头部的代码应如下所示：

else if( id < head.id)
{
     Node newHead = new Node(id, name, age, gpa, null, head);
     head.prev = newHead;
     head = newHead;
     size ++;
}

您没有设置旧磁头的 prev 指针，因为添加了新磁头。

其他快速想法：

您应该在构造函数中明确地将 size 初始化为 0

除了纠正任何其他错误之外，我认为这里更大的问题是：您如何测试它？通过运行一些快速测试，我开始很容易地发现其中的一些错误。我向 class 添加了几个方便的方法（只是为了测试......有更好的方法来做迭代器）：

public void print()
{
   for(Node temp = head; temp != null; temp = temp.next)
   {
       System.out.println(temp.name);
   }
}

public void printReverse()
{
   for(Node temp = tail; temp != null; temp = temp.prev)
   {
       System.out.println(temp.name);
   }
}

然后我添加了一个简单的 main 方法，如下所示：

public static void main(final String[] args)
{
   StudentInfo si = new StudentInfo();
   si.insertAscending(2, "Brent", 23, 2.2);
   //si.insertAscending(3, "Steve", 23, 2.2);
   //si.insertAscending(5, "Joe", 23, 2.2);
   //si.insertAscending(4, "Pat", 23, 2.2);
   //si.insertAscending(1, "Mike", 23, 2.2);
   si.print();
   System.out.println("==========");
   si.printReverse();
}

即使不使用调试器或任何东西，也很容易看出问题所在。一旦我确定 one-element 案例有效，我就取消了下一个 insertAscending 调用和 so-on 的注释，直到一切正常。

代码中可能存在也可能不存在我未在此处提及的其他错误。我认为真正重要的是你了解我是如何发现这些错误的，并且你想出了一个更好的方法来测试你的代码并说服自己它可以正常工作。

按升序对双向链表进行排序

sorting doubly linked lists by ascending order

java

doubly-linked-list