选择排序双链表java

Question

我需要使用选择排序排序链表。但是我不会使用集合。我在寻找最小的元素和创建一个新版本的排序列表时遇到了麻烦。谢谢。

    public class LinkedList {
        public Node first;
        public Node last;
        public LinkedList() {
            first = null;
            last = null;
        }
        public boolean isEmpty() {
            return first == null;
        }
        public void addFirst(Student student) {
            Node newNode = new Node(student);
            if (isEmpty())
                last = newNode;
            else
                first.previous = newNode;
            newNode.next = first;
            first = newNode;
        }
        public void addLast(Student student) {
            Node newNode = new Node(student);
            if (isEmpty())
                first = newNode;
            else
                last.next = newNode;
            newNode.previous = last;
            last = newNode;
        }
        public void display() {
            Node current = last;
            while (current != null) {
                System.out.print(current.student.name + "b");
                System.out.print(current.student.surname + "b");
                System.out.println(current.student.educationType);
                current = current.previous;
            }
        }

由于findSmallest方法不工作，Sort方法不能正常工作。我尝试通过创建一个新的列表来实现排序，其中我以排序的方式放置节点。它也不会跳出While循环

        public void Sort() {
            LinkedList list = new LinkedList();
            Node toStart = last;
            while (toStart!=null){
                list.addLast(findSmallest(toStart).student);
                toStart = toStart.previous;
            }

        }

它会发送添加的最大元素，如果我手动将'last'赋值给'smallest'，它就会工作。

        public Node findSmallest(Node toStartFrom) {
            Node current = toStartFrom;
            Node smallest = toStartFrom; //if i put here `last` it will work correctly
            while(current != null) {
                if (smallest.student.name.compareToIgnoreCase(current.student.name) > 0) smallest = current;
                current = current.previous;
            }
            return smallest;
        }
    }
  public class Node {
        public Student student;
        public Node next;
        public Node previous;
        public Node(Student student) {
            this.student = student;
        }
    }

    public class Student {
        public String name;
        public String surname;
        public String educationType;
        static public Student createStudent() {
         ....
            return student;
        }
    }

Answer 1

不使用双链表可能会有所帮助，因为这样您需要维护的链接就会减少。此外，您可能会遇到findSmallest()方法的麻烦，因为您最初将当前和最小设置为同一节点，因此当执行if(smallest.student.name. comparetoignorecase (current.student.name)> 0)语句时，您将学生的姓名与学生的姓名进行比较。例如，如果最小的节点被设置为有一个学生的名字是John，那么current也被设置为相同的节点，所以current的学生名字也是John。不是一个问题，如果他们是不同的学生有相同的名字，但在你的代码中，他们是相同的学生，当前和最小的点到同一节点。实际上，这个if语句总是为假，并且您永远不会执行沿着列表移动当前的代码。这也是为什么当您设置了smallest = last时，该方法至少在某些时候是有效的。

Answer 2

如上所述，请尝试使用

smallest = startnode
next =startnode.next
while(next != null)
compare next with smallest, and assign accordingly
next = next.next

转换成代码应该不难