由于某种原因，我对双链表的冒泡排序切断了列表的第一个节点

Question

这是方法

public void sortStudentsAlphabeticallyByFirstName()
{
    StudentNode unsorted = tail;
    StudentNode current = header;
    while(unsorted.prevNode() != null)
    {
        while(current != unsorted)
        {
            int result = (current.getFirstName()).compareToIgnoreCase(current.nextNode().getFirstName());
            if(result > 0) //If in wrong order lexicographically
            {
                StudentNode temp = current;
                StudentNode next = current.nextNode();
                StudentNode previous = current.prevNode();
                StudentNode nextNext = next.nextNode();
                if (numberOfStudents() == 2) 
                {
                    current = current.nextNode();
                    current.setNext(temp);
                    temp.setPrev(current);
                    temp.setNext(null);
                    current.setPrev(null);
                    unsorted = temp;
                }
                else if(nextNext == null) //If at penultimate student therefore last comparison
                {
                    current = current.nextNode();
                    current.setNext(temp);
                    temp.setPrev(current);
                    temp.setNext(null);
                    previous.setNext(current);
                    current.setPrev(previous);
                    unsorted = temp;
                }
                else if(previous == null) //if at beginning of student list
                {
                    if(current.nextNode() == unsorted)
                    {
                        current = current.nextNode();
                        current.setNext(temp);
                        temp.setPrev(current);
                        temp.setNext(nextNext);
                        nextNext.setPrev(temp);  
                        current.setPrev(null); 
                        unsorted = temp; //swap unsorted back to correct position
                    }
                    else
                    {
                        current = current.nextNode();
                        current.setNext(temp);
                        temp.setPrev(current);
                        temp.setNext(nextNext);
                        nextNext.setPrev(temp);  
                        current.setPrev(null);
                    }
                }
                else  //else if in the middle of the list
                {
                    if(current.nextNode() == unsorted)
                    {
                        current = current.nextNode();
                        current.setNext(temp);
                        temp.setPrev(current);
                        temp.setNext(nextNext);
                        nextNext.setPrev(temp);  
                        previous.setNext(current);
                        current.setPrev(previous); 
                        unsorted = temp;
                    }
                    else
                    {
                        current = current.nextNode();
                        current.setNext(temp);
                        temp.setPrev(current);
                        temp.setNext(nextNext);
                        nextNext.setPrev(temp);  
                        previous.setNext(current);
                        current.setPrev(previous); 
                    }
                }
            }
            current = current.nextNode();
        }
        current = header;
        unsorted = unsorted.prevNode();
    }
}

有人能明白为什么当我尝试再次迭代列表时它会切断列表的开头吗？我已经使用了调试器，它似乎运行正常，但我无法弄清楚它为什么这样做。

如果有帮助的话，这也是迭代列表方法

public void itterateList()
{
    StudentNode u = header;
    while(u != null)
    {
        System.out.println(u.getFirstName()+" "+u.getSurname());
        u = u.nextNode();
    }
}

Answer 1

您的代码的主要问题是 header 和 tail 从未更新。

尝试以下更简单的代码：

public void sortStudentsAlphabeticallyByFirstName()
{
    StudentNode unsorted = tail;
    StudentNode current = header;
    while(unsorted.prevNode() != null)
    {
        while(current != unsorted)
        {
            StudentNode next = current.nextNode();
            int result = (current.getFirstName()).compareToIgnoreCase(next.getFirstName());
            if (result>0) // current is greater than next
            {
                // need to exchange : next will be before current
                //   HEADER (before) CURRENT NEXT (after) TAIL
                //   HEADER (before) NEXT CURRENT (after) TAIL

                // 1 - Before current
                if (current.prevNode() != null)
                    current.prevNode().setNext(next);
                else header = next;

                // 2 - After next
                if (next.nextNode() != null)
                    next.nextNode().setPrev(current);
                else tail = current;

                // 3 - current <-> next
                current.setNext(next.nextNode());
                next.setPrev(current.prevNode());
                current.setPrev(next);
                next.setNext(current);

                // Don't need to update current which is
                // already pointing to the greatest element
            }
            // next is greater than current -> update current
            else current = current.nextNode();
        }
        current = header;
        unsorted = unsorted.prevNode();
    }
}