Какой самый быстрый способ получить самый длинный LinkedList в LinkedList из LinkedList?

#java #list #linked-list

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

Вопрос:

Моя структура данных представляет собой список списков, точно, LinkedList<LinkedList<String>>

Поскольку у меня есть несколько списков, я просто хочу найти список, который имеет больший размер. Какой самый быстрый способ?

1. Почему бы не выполнить итерацию списка и найти самый большой ListItem.size() быстрее всего?

2. Я предполагаю, что самый большой означает наибольшее количество элементов (наибольшее количество строк), а не наибольшую объединенную длину строк или что-то в этом роде?

Ответ №1:

LinkedList Класс в Java содержит операции, которые обычно отсутствуют в типичном связанном списке. Одним из случаев является возможность вызова size() для LinkedList объекта. Это потому, что класс наследуется от AbstractCollection интерфейса. Поэтому вы можете просто сделать что-то вроде этого, чтобы найти самый большой список:

 int largest = -1;
LinkedList<String> largestLinkedList = null;
for (LinkedList<String> ll : listOfLinkedLists) {
    if (ll.size() > largest) {
        largestLinkedList = ll;
        largest = ll.size();
    }
}

1. Вы должны инициализировать largest = -1 , чтобы, если ваш список списков содержит только пустые списки, вы фактически получили один из пустых списков вместо null .

2. Я не знал, что такая операция, как size , не является типичной для реализаций связанных списков на другом языке.

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

Ответ №2:

Чтобы вычислить это:

 int maxSize = listOfLists.stream().map(Collection::size).max(Integer::compare).orElse(0);

(Или получение самого списка)

 List<String> max = listOfLists.stream().max((l1, l2) -> Integer.compare(l1.size(), l2.size())).orElse(null);

Если вы хотите, вы могли бы сохранить этот результат и просто обновлять его всякий раз, когда вы добавляете / удаляете список. Имейте в виду, что это немного более хрупко, если списки изменчивы.

1. Возвращает не то, какой список является самым длинным, а то, какова длина самого длинного списка. Не совсем то, что задал вопрос.

2. Закрыть, но max( ) возвращает Optional<List<String>> . Добавьте .orElse(null) или аналогичный, чтобы заставить его скомпилироваться.

3. Есть много способов, которыми вы можете это сделать, но это гораздо более семантично, и на этом этапе суть идеи зависит от OP.

4. @erickson Не удалось отредактировать … прошло более 5 минут. NoSuchElementException::new

5. @erickson Конечно, это лучше. В конце концов, это то, что .get() делает … возвращает, Optional если присутствует, и выдает NoSuchElementException в противном случае. (Ладонь лица)