Если какой-либо параметр функции получает список<Список> nums , то nums создается экземпляром LinkedList или ArrayList?

ProgramBox

Если какой-либо параметр функции получает список<Список> nums , то nums создается экземпляром LinkedList или ArrayList?

Post author:admin
Запись опубликована:10 января, 2022
Post category:Вопросы по программированию

#java #generics #arraylist #collections #linked-list

Вопрос:

Оба LinkedList и ArrayList построены на интерфейсе списка, однако LinkedList для построения списка используется традиционный метод указателя, а ArrayList для реализации List функциональности используется массив . Итак, что можно утверждать перед использованием nums, будет ли он использоваться ArrayList или LinkedList за экраном?

Как у меня возник этот вопрос?

     public int[] smallestRange(List<List<Integer>> nums) {
        
    }
}

Большая часть вопроса Java с кодом Leetcode имеет такой формат ввода. Без предварительного знания того, как были созданы экземпляры num, как кто-то может использовать nums.get(i) функцию ( list.get(i) является O(1) в списке ArrayList и O(n) в списке ссылок )

1. Ни один из них List не является интерфейсом, и вы не можете (не должны) предполагать внутреннее представление (конечно, вы могли бы проверить во время выполнения, но не должны). Если вам нужна быстрая реализация, создайте свой собственный ограниченный интерфейс/класс или напишите напрямую smallestRange(ArrayList<...> ...) .

2. Это очень веская причина избегать list.get(int) и вместо этого использовать итератор.

Ответ №1:

В 99% случаев это будет an ArrayList , и вы хотите использовать an ArrayList в своем коде. Они используют меньше памяти, быстрее, и код, использующий преимущества LinkedList , обычно может быть переписан для использования двух ArrayLists . Основным недостатком является add() то, что время от времени он работает в O(n) время.

как кто-то может использовать nums.get(i)

Вы не. Вы пользуетесь тем, что список есть Iterable , и делаете такие вещи, как для каждого цикла:

 for (var i : list) {
    ...
}

это выполняется за O(n) время для обоих LinkedList и ArrayList .

Технически, есть интерфейс под названием RandomAccess » вы можете проверить, является ли get() он O(1)». Хотя ты, наверное, этого не хочешь. Используйте итератор.

 if (list instanceof RandomAccess) {
    list.get(...);
}

1. Абсолютно правильно: в принципе нет причин активно использовать LinkedList , даже Джошуа Блох, который написал это , не использует его. И большую часть времени вам должно быть все равно, какая конкретная List реализация используется. Единственное, чего мне не хватает, — это объяснения, когда проверка RandomAccess может оказаться полезной, если вообще когда-либо будет.

2. @JoachimSauer В вашем собственном приложении это самая простая стратегия, которую можно просто избежать LinkedList . Но сам код JDK использует проверки для RandomAccess переключения алгоритмов , что разумно, поскольку он не может предсказать, будет ли использоваться код приложения LinkedList или нет. И LinkedList часто всплывает в вопросах SO, что говорит о том, что, возможно, многие программы все еще используют его. Я боюсь, что есть учителя, которые дают плохие советы начинающим…

3. Что касается «алгоритмов переключения», очевидный случай заключается в том, какую реализацию сортировки использовать. Я думаю, что он сортирует на месте для RandomAccess, но копирует неслучайные списки в список массивов, сортирует на месте, а затем заменяет элементы.

4. @DavidEhrmann реализация по умолчанию sort всегда создает копию. Причина в том, что он поддерживается Arrays.sort(…) , для чего в любом случае требуется массив. Только ArrayList и Vector переопределяют его, чтобы передавать свои внутренние массивы напрямую Arrays.sort(…) . Но в основном все остальные операции ( reverse , shuffle , fill ,, copy , rotate , replaceAll , indexOfSubList , binarySearch ) имеют такой переключатель.

Ответ №2:

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

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

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

В соответствии с платформой проблем кодирования я думаю, что они указывают код, из которого они вызвали этот метод. Вы можете проверить там, но если это не указано, то, скорее всего, они выберут ArrayList — для ограничения по времени. И я думаю, что пользователь не должен беспокоиться о реализации, которую он выбрал. Как я уже говорил, пользователь должен знать, каковы его требования, а затем только выбирать реализации.

Ответ №3:

Это может быть любой из них:

   List<List<Integer>> list1 = new ArrayList<>();
        
  List<List<Integer>> list2 = new LinkedList<>();

  int[] x = smallestRange(list1); //works
  int[] y = smallestRange(list2); //also works

Вам нужно сделать так, чтобы ваш код мог работать с обоими типами