Эффективная вставка в связанный список в алфавитном порядке - PullRequest
Новая
       33

Эффективная вставка в связанный список в алфавитном порядке

2 голосов
/ 05 мая 2019

Я вставляю элементы из созданного мною класса в связанный список, но я должен найти правильную точку индекса, чтобы вставить их (чтобы элементы были в алфавитном порядке), прежде чем я добавлю их.

У меня есть некоторый рабочий код, но он смехотворно неэффективен: на полудопорядочной машине требуется 5 минут, чтобы добавить 10000 элементов.Мне было интересно, есть ли более эффективный способ сделать это.

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

В показанном коде я передаю имя (наряду с двумя другими переменными, которые не имеют значенияи уже является частью itemClass) в следующем коде 

if (llist.size() == 0) {
    llist.add(itemClass);
} 
else if (llist.get(0).name.compareTo(name)>0) {
    llist.add(0, itemClass);
} 
else if (llist.get(llist.size() - 1).name.compareTo(name) < 0) {
    llist.add(llist.size(), itemClass);
} 
else {
    int i = 0;
    while (llist.get(i).name.compareTo(name) < 0) {
        i++;
    }
    llist.add(i, itemClass);
}

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

1 Ответ

0 голосов
/ 05 мая 2019

У вас есть связанный список, но вы не используете его действительные «ссылки»

Удалите все вызовы на get

Вместо вызова get вы должны использоватьlistIterator.

Кроме того, вы должны использовать метод listIterator add

...