Преобразование LinkedHashSet в список

Question

• Допустим, список b является LinkedList.
• Допустим, List a также является LinkedList.

Вопрос:

• Как добавить этот список в постоянное время?

Это возможно, потому что LinkedList предположительно является двусвязным списком (в противном случае он не мог бы реализовать интерфейс Deque). А добавление двусвязного списка - это операция 0 (1).

Метод addAll не выполняется в постоянное время.

Вопрос:

• Как преобразовать LinkedHashSet в список за постоянное время?

Это также предположительно возможно, потому что LinkedHashSet "поддерживает двусвязный список, проходящий через все его записи".

Answer 1

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

Аналогично объединение двух связанных списков - я не знаю, знает ли каждый узел, в каком списке он находится, но это, безусловно, возможность, которая помешает вашему добавлению в постоянное время. Даже если они этого не делают, как только вы прикрепляете заголовок одного списка к хвосту другого, вы сталкиваетесь с проблемами - у вас есть два списка, оба ссылаются на одни и те же данные, что может иметь некоторые странные последствия.

Другими словами, обе эти операции осуществимы в компьютерном смысле, и вы можете создать свои собственные реализации для их поддержки, но это не означает, что Java API предоставляет свои внутренние возможности способ, который позволяет эти операции.

Answer 2

Вам нужно будет реализовать свои собственные классы. Класс LinkedList не раскрывает структуру своего внутреннего узла, поэтому вы не можете просто указать его последний узел на первый узел другого LinkedList.

Ответ аналогичен для LinkedHashSet: хотя он поддерживает этот двусвязный список, вы не можете получить к нему доступ.

Answer 3

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

Я посмотрел дальше, и ты прав. Если у вас есть Set<Whatever> whatever = SOME CONSTRUCTOR, вы можете кодировать List<Whatever> list = new LinkedList(whatever);, потому что LinkedList имеет конструктор Collections, а Set имеет интерфейс Collections.