Создание отсортированного связанного списка в Java

#java #sorting #linked-list

#java #сортировка #связанный список

Вопрос:

Итак, я должен сортировать связанный список в Java по алфавитному порядку (узлы — это строки). Мне не разрешено использовать коллекции, поэтому я должен составить свой собственный связанный список и алгоритм сортировки. Я создал метод, который находит самое большое (или самое удаленное по алфавиту) слово в связанном списке, которое работает. Теперь я пытаюсь выполнить сортировку, взяв связанный список, найдя самый большой элемент и вставив его в новый связанный список. Затем он удаляет самый большой и продолжает делать то же самое, пока связанный список не станет пустым. При запуске я получаю пустой список, что не так с моим кодом?

Код, возвращающий самый большой элемент

 public Link isLargest(){

    Link large = first;
    Link temp = null;
    Link current = first;
    Link after = current.next;

    while (after != null){

        if (large.lastName.compareTo(after.lastName) < 0){
            large = after;    
        }

        temp = current;
        current = temp.next;
        after = current.next;

    }
    return large;
}

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

  private static LinkedList linkSort(LinkedList unsorted){

    LinkedList sorted = new LinkedList();

    while (!(unsorted.isEmpty())){
        Link large = unsorted.isLargest();
        sorted.insert(large.name, large.lastName);
        first = large;
        unsorted.removeFront();
    }

    return sorted;
}

1. К вашему сведению, в Java существует соглашение об именовании методов, так что все, что вызывается isFoo() , возвращает логическое значение. Если вы хотите действительно получить значение, вам нужно будет назвать свой метод getFoo() findFoo() или что-то в этом роде, чтобы избежать путаницы.

2. Что касается вашей проблемы, ваш linkSort() метод выглядит так, как будто он должен добавлять что-то sorted , поэтому я бы предположил, что либо несортированный список, который вы передаете, пуст, либо в вашем isEmpty() методе есть ошибка. Пробовали ли вы пошаговое выполнение linkSort() в отладчике или, по крайней мере, вводили некоторые операторы ведения журнала, чтобы убедиться, что ваш цикл while выполняется?

3. Я немного смущен… вам нужно создать сортированный List (как в названии вашего вопроса, и в этом случае вам нужно будет только переопределить add() метод любого типичного LinkedList ), или вам нужно на самом деле отсортировать некоторые List ?

4. Мне нужно отсортировать LinkedList в алфавитном порядке, что я и делаю, создавая новый отсортированный список

Ответ №1:

После того, как вы найдете самую большую ссылку, вы удаляете ссылку в заголовке (removeFront) LinkedList. Это неверно, потому что ссылка в начале не обязательно является самой большой ссылкой. Что вам нужно удалить, так это самую большую ссылку.

1. Как это объясняет, почему возвращаемый отсортированный список пуст? Это должен быть комментарий, и как таковой был бы полезен, но он не отвечает на главный вопрос OPs.

2. Это не так. Это всего лишь одна из проблем, которые я вижу. Нам нужно посмотреть, как выглядит метод insert() .