Метод сортировки двусвязного списка

Пытаюсь понять, как отсортировать мой двусвязный список. Здесь я получаю исключение с нулевым указателем:

while (temp.getNext()!=null){

Есть ли лучший подход или какой-либо совет, чтобы все шло правильно?

public void sort() {
    //bubble sort!
    boolean swapped = (head != null);
    while (swapped) {
        swapped = false;

        EntryNode temp = head;

        //can't swap something with nothing
        while (temp.getNext()!=null){
            if (temp.getLastName().compareTo(temp.getNext().getLastName()) > 0) {
                swapped = true;

                //special case for two nodes
                if (size == 2) {
                    //reassign head and tail
                    tail = temp;
                    head = temp.getNext();
                    tail.setPrev(head);
                    head.setNext(tail);
                    tail.setNext(null);
                    head.setNext(null);
                }
                //if swapping is at head
                else {

                    if (temp == head) {
                        head = temp.getNext();
                        temp.setNext(head.getNext());
                        head.getNext().setPrev(temp);
                        head.setPrev(null);
                        head.setNext(temp);
                        temp.setPrev(head);
                    }

                    else {
                        temp.setNext(temp.getNext().getNext());
                        temp.setPrev(temp.getNext());
                        temp.getNext().setNext(temp);
                        temp.getNext().setPrev(temp.getPrev());
                    }
                }
            }
            //loop through list
            temp = temp.getNext();
        }
    }
}

person jackie    schedule 14.03.2012    source источник
comment
Это должно быть домашнее задание. Вы не сортируете связанные списки в реальном мире.   -  person user207421    schedule 14.03.2012
comment
@EJP В языках на основе LISP вы все время сортируете связанные списки   -  person Óscar López    schedule 14.03.2012


Ответы (3)


Используйте алгоритм сортировки слиянием, часто это лучший выбор для сортировки (одно- или двусвязного) списка. Уже есть сообщение, в котором обсуждаются соответствующие вопросы реализации.

person Óscar López    schedule 14.03.2012

Я думаю, вам стоит проверить:

while(temp != null)

потому что вы уже назначаете

temp = temp.getNext()

в конце while цикла.

person torrential coding    schedule 14.03.2012

Простой подход состоит в том, чтобы поместить содержимое списка в массив, использовать Arrays.sort для сортировки массива и, наконец, перестроить список из отсортированного массива.

person Stephen C    schedule 14.03.2012
comment
Для этого подхода потребуется два обхода списка, в идеале вы должны отсортировать двусвязный список за один обход или за O (nlg n) (при использовании рекурсии) - person Shankhoneer Chakrovarty; 14.03.2012
comment
@ShankhoneerChakrovarty - Это неверно. OP выполняет пузырьковую сортировку, что требует N обходов списка. Добавление еще двух обходов не повлияет на сложность. Доказано, что невозможно отсортировать список произвольных сопоставимых объектов лучше, чем O(NlogN) сравнениями ... что примерно равно O(logN) обходам. Еще раз, добавление константы еще 2 обхода не меняет сложности. (Сортировки лучше, чем O(NlogN), зависят от специальных свойств домена сортируемых значений.) - person Stephen C; 14.03.2012