Блог

Главная - Вопросы по программированию - Сортировка LinkedList без очевидного доступа к узлам?

Сортировка LinkedList без очевидного доступа к узлам?

#java #sorting #linked-list

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

Вопрос:

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

 private LinkedList<T> list;

// constructor
public SortedLinkedList(LinkedList<T> in){
}

Теперь, я думаю, у меня есть логика (я мог бы использовать простую сортировку слиянием), но я не вижу способа получить доступ к самим узлам. Что-то, что приходит на ум, — это также небольшая вариация быстрой сортировки, т. Е. Используйте head в качестве опоры и сортируйте linkedlist на два меньших, повторяя, а затем объединяя… но я хотел знать, могу ли я сделать это другим способом. Однако, поскольку мы не можем получить доступ ни к одному из частных узлов, у меня нет хороших идей.

Нам не разрешено использовать коллекции или массивы для сортировки по понятным причинам. Нам разрешено использовать только Java LinkedList и единственное личное поле.

Спасибо за любой вклад.

Редактировать: я бы предпочел избегать использования toArray, если смогу помочь.

Ответ №1:

Поскольку вам не разрешено использовать другие классы, я бы рекомендовал вам использовать пузырьковую сортировку. Это проще, а производительность не так уж и плоха. Вот как это использовать:

 public SortedLinkedList(LinkedList<T> in) {
    bubbleSort(in);
}

private void bubbleSort(LinkedList<T> in) {
    // Convert the LinkedList into an array called arr. You should know how to do this..
    // This code assumes that your resulting array is of type int. For others, adjust
    // the code appropriately.

    for(int i = arr.length - 1; i > 0; i--) {
        for(int j = 0; j < i; j  ) {
            if(arr[j] > arr[j   1])
                swap(array, j, j 1);
        }
    }
}

private void swap(int[] array, int i, int j) {
    int temp = 0;

    temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

Комментарии:

1. На самом деле, это было не совсем то, что я искал. Я должен был указать на это в начале, но я пытаюсь стремиться к чему-то более эффективному. Моим единственным мозгом было (есть), как получить доступ к ссылкам / данным узла без использования toArray. Я не могу использовать итератор, так как это вызвало бы у меня приятное ConcurrentModificationException .

2. Затем вы можете попробовать использовать сортировку по вставке, поскольку она сортирует элементы во время их вставки. Так что это должно быть более эффективно. Подробнее об алгоритме читайте в статье Википедии.

3. Я бы так и сделал, но суть кода не в этом. Предполагается, что он возьмет существующий LinkedList и отсортирует его.

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

Ответ №2:

Все в порядке, вам не нужен никакой частный доступ. Используйте список как просто список — у вас есть методы get и set.

Однако очень важно учитывать, что связанный список имеет медленный произвольный доступ! Итак, вам нужно найти сортировку, которая работает с узлами, расположенными рядом друг с другом.

Что-то вроде сортировки пузырьков на самом деле может сработать лучше всего в этом случае. Не пузырь . . Название было другим, вам нужно cmp и поменять местами соседние ячейки. Может быть, поменять местами?

Метки: