Java и коллекции: когда использовать связанный список массивов?

Question

В чем преимущество использования связанного списка массивов?

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

Или, по крайней мере, я не понял.

Так какой же выигрыш в использовании linked list of arrays и когда?

Answer 1

С помощью связанного списка массивов вы можете легко объединить преимущества связанных списков и статических массивов.

Отметьте этот вопрос.

Answer 2

Подумайте об этой проблеме:

Представьте (буквальную) стопку пластин. Если стопка становится слишком высокой, Поэтому в реальной жизни мы, скорее всего, начнем стек, когда предыдущий стек превышает некоторый порог. Внедрить данные структура SetOfStacks, которая имитирует этот SetOf-Stacks должна быть состоит из нескольких стеков и должен создать новый предыдущий превышает емкость (Интервью по взлому технических кодов)

Answer 3

Когда вам потребуется быстрое получение объекта из коллекции, и вы не будете уверены, что у вас достаточно памяти для выделения «целого» массива (реализация ArrayList), вы можете написать собственную реализацию, которая использует список массивов для быстрогобыстро найти объект, который вы ищете.

Но для этого подхода есть определенно лучшие структуры данных.

Answer 4

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

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

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

P.S. Кроме того, если скорость действительно важна для вас, сначала я бы провел небольшое исследование со сравнением существующей реальной реализации структур данных (ArrayList, LinkedList, массивы и т. Д.).

Answer 5

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

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