Выбор сортировки Взаимосвязанный список 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 работает неправильно.Я пытаюсь осуществить сортировку, создав новый список, в который я помещаю Узлы отсортированным способом.И он также не выходит из цикла «В то время как»

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


        }

Он посылает самый большой добавленный элемент, и если я вручную назначу 'последний' для 'самого маленького', он будет работать.

        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 (smalllest.student.name.compareToIgnoreCase (current.student.name)> 0) вы сравниваете имя студента с тем же именем студента. Например, если для узла, для которого установлено наименьшее значение, задано имя студента Джона, то текущая скважина устанавливается на тот же самый узел, поэтому имя студента текущего также является Джоном. Не проблема, если это разные ученики с одинаковыми именами, но в вашем коде они одинаковые ученики и имеют текущий и наименьший указатель на один и тот же узел. По сути, это если оператор всегда будет ложным, и вы никогда не будете выполнять код для перемещения по списку. Именно поэтому, когда вы устанавливаете smalllest = last, метод работает, по крайней мере, некоторое время.

Answer 2

Как сказано выше, попробуйте что-то вроде

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

Не должно быть слишком сложно превратить это в код